Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>