Re: Re: FindMinimum and the minimum-radius circle

*To*: mathgroup at smc.vnet.net*Subject*: [mg50193] Re: Re: FindMinimum and the minimum-radius circle*From*: Thomas Burton <tburton at brahea.com>*Date*: Fri, 20 Aug 2004 04:57:27 -0400 (EDT)*Organization*: Brahea Consulting*References*: <cfuq6g$653$1@smc.vnet.net> <200408180834.EAA08732@smc.vnet.net> <cg204q$msq$1@smc.vnet.net>*Reply-to*: tburton at brahea.com*Sender*: owner-wri-mathgroup at wolfram.com

On Thu, 19 Aug 2004 00:41:30 -1000, DrBob wrote (in article <cg204q$msq$1 at smc.vnet.net>): > Unfortunately, changing the objective function that way means solving the > wrong problem. > > Bobby > > On Wed, 18 Aug 2004 04:34:05 -0400 (EDT), Thomas Burton <tburton at brahea.com> > wrote: > >> Well, you're right. I jumped to my conclusion. All methods of FindMinimum >> can >> get stuck at corners. Because NMinimize seems like overkill to me, I'm going >> to try again. Tweak the radius function to slightly round the corners of the >> Reuleaux polygons: >> >> radius3 [n_Integer?Positive] [x_?NumericQ, y_?NumericQ] = >> Total[sqDiff /@ hull^n]^ (1/n) >> >> FindMinimum seems to perform well with a judicious choice of n. In my >> tests, >> about as well as NMinimize with MachinePrecision and n=1,000,000. Despite >> the >> more complex calculation of radius, FindMinimum is still much faster in my >> tests. >> >> Tom Burton >> >> On Tue, 17 Aug 2004 19:41:36 -1000, DrBob wrote >> (in article <cfuq6g$653$1 at smc.vnet.net>): >> >>> As you say, a global method shouldn't be necessary; but FindMinimum >>> evidently >> >>> can't do the job. >>> >>> Reducing the number of starting values for each variable to one AND >>> specifying Method->QuasiNewton fails miserably in my tests, even though I'm >>> using the convex hull and even with only three data points. I always get a >>> FindMinimum::lstol error message (totally spurious, I think), and I often >>> get >> >>> a circle that can't be optimum. >>> >>> I tried specifying all the available methods, and they're all equally bad. >>> >>> Needs["Statistics`"] >>> Needs["Graphics`"] >>> Needs["DiscreteMath`ComputationalGeometry`"] >>> sq = #1 . #1 & ; >>> sqDiff[x_, y_] = sq[{x, y} - #1] & ; >>> sqDiff[{x_, y_}] = sq[{x, y} - #1] & ; >>> diff = Abs[(#1 - #2)/(#1 + #2)] < 0.0001 & ; >>> circleFinder[n_Integer] := >>> Module[{data, hull, r, pt, x2, y2, radius}, >>> data = RandomArray[NormalDistribution[0, 1], >>> {n, 2}]; hull = data[[ConvexHull[data]]]; >>> radius[x_, y_] = Max[sqDiff[x, y] /@ hull]; >>> {x2, y2} = Median[hull]; {r, pt} = >>> FindMinimum[radius[x, y], {{x, x2}, {y, y2}}, >>> Method -> ConjugateGradient]; r = Sqrt[r]; >>> pt = {x, y} /. pt; {data, hull, r, pt, >>> Length[hull] + 1 - Length[ >>> Union[sqDiff[pt] /@ hull, SameTest -> diff]]}] >>> plotter[n_] := Module[{data, hull, r, pt, count}, >>> {data, hull, r, pt, count} = circleFinder[n]; >>> Print[count]; Show[Graphics[{PointSize[0.02], >>> Point /@ data, Red, Point[pt], Circle[pt, r], >>> Blue, Line[Join[hull, {First[hull]}]], >>> Point /@ hull}], AspectRatio -> Automatic]] >>> counter[n_] := Last[circleFinder[n]] >>> >>> circleFinder[3] >>> >>> NMinimize with constraints is the clear winner so far. >>> >>> Bobby If you had found an exact answer, I would be more sympathetic to your complaint about mine. >>> >>> Thomas E Burton <tburton at brahea.com> wrote in message >>> news:<cfsi5h$9st$1 at smc.vnet.net>... >>>> (See thread "Smalest enclosing circle".) >>>> When I read Bobby's updated message changing FindMinimum to NMinimize,I >>>> thought, "There must be only one local minimum. Why do we need aglobal >>>> method?". Indeed, a contour plot of the function radius[x,y]shows exactly >>>> one minimum. Because the smallest circle in most casestouches three >>>> points, >>>> the contours surrounding the minimum aretriangular. FindMinimum as >>>> implemented by Bobby (with two startingvalues for each coordinate) gets >>>> stuck at the first acute corner ithits. (And maybe some obtuse corners as >>>> well--I have not thought thisthrough.) >>>> Though frequently maligned in this group for being too brief, >>>> theImplementation Notes do shed light on this issue: When two >>>> startingvalues are given for each variable, FindMinimum defaults to >>>> Brent'sprincipal axis method. If you specify Method->"QuasiNewton", or >>>> simplyprovide only one starting value for each coordinate instead of >>>> two,then FindMinimum does a respectable job in a small fraction of the >>>> timeneeded for NMinimize. On the other hand, if you follow Bobby's >>>> trackand >>>> reduce the field of points to its convex hull, chances are that youan >>>> easily afford either method. >>>> Tom Burton >>> >>> >>> >> >> >> >> > > > >

**Follow-Ups**:**Re: Re: Re: FindMinimum and the minimum-radius circle***From:*"Janos D. Pinter" <jdpinter@hfx.eastlink.ca>

**References**:**Re: FindMinimum and the minimum-radius circle***From:*Thomas Burton <tburton@brahea.com>