Re: Re: FindMinimum and the minimum-radius circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50179] Re: [mg50170] Re: FindMinimum and the minimum-radius circle
- From: DrBob <drbob at bigfoot.com>
- Date: Thu, 19 Aug 2004 06:28:09 -0400 (EDT)
- References: <cfuq6g$653$1@smc.vnet.net> <200408180834.EAA08732@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
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
>>
>> 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
>>
>>
>>
>
>
>
>
--
DrBob at bigfoot.com
www.eclecticdreams.net
- References:
- Re: FindMinimum and the minimum-radius circle
- From: Thomas Burton <tburton@brahea.com>
- Re: FindMinimum and the minimum-radius circle