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

FindMinimum and the minimum-radius circle

• To: mathgroup at smc.vnet.net
• Subject: [mg50141] FindMinimum and the minimum-radius circle
• From: Thomas E Burton <tburton at brahea.com>
• Date: Tue, 17 Aug 2004 05:01:19 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

(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 a 
global method?". Indeed, a contour plot of the function radius[x,y] 
shows exactly one minimum. Because the smallest circle in most cases 
touches three points, the contours surrounding the minimum are 
triangular. FindMinimum as implemented by Bobby (with two starting 
values for each coordinate) gets stuck at the first acute corner it 
hits. (And maybe some obtuse corners as well--I have not thought this 
through.)

Though frequently maligned in this group for being too brief, the 
Implementation Notes do shed light on this issue: When two starting 
values are given for each variable, FindMinimum defaults to Brent's 
principal axis method. If you specify Method->"QuasiNewton", or simply 
provide only one starting value for each coordinate instead of two, 
then FindMinimum does a respectable job in a small fraction of the time 
needed for NMinimize. On the other hand, if you follow Bobby's track 
and reduce the field of points to its convex hull, chances are that you 
an easily afford either method.

Tom Burton