Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

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

Search the Archive

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


  • Prev by Date: Re: GUIKit: Color?
  • Next by Date: Re: Label of Max[list]
  • Previous by thread: Re: FindMinimum and the minimum-radius circle
  • Next by thread: Re: Re: FindMinimum and the minimum-radius circle