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