MathGroup Archive 2004

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

Search the Archive

Re: FindMinimum and the minimum-radius circle

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 

Tom Burton

On Tue, 17 Aug 2004 19:41:36 -1000, DrBob wrote
(in article <cfuq6g$653$1 at>):

> 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> wrote in message 
> news:<cfsi5h$9st$1 at>...
>> (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: General expression of this definite integral ?
  • Next by Date: Label of Max[list]
  • Previous by thread: FindMinimum and the minimum-radius circle
  • Next by thread: Re: Re: FindMinimum and the minimum-radius circle