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>
• 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

>>>
>>> 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
>>>
>>>
>>>
>>
>>
>>
>>
>
>
>
>

```

• Prev by Date: Re: Plotting a contour plot with cylindrical co-ordinates
• Next by Date: Re: GUIKit FileDialog Widget