Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Re: Re: FindMinimum and the minimum-radius circle

• To: mathgroup at smc.vnet.net
• Subject: [mg50213] Re: [mg50193] Re: Re: FindMinimum and the minimum-radius circle
• From: "Janos D. Pinter" <jdpinter at hfx.eastlink.ca>
• Date: Sat, 21 Aug 2004 03:04:13 -0400 (EDT)
• References: <cfuq6g$653$1@smc.vnet.net> <200408180834.EAA08732@smc.vnet.net> <cg204q$msq$1@smc.vnet.net> <200408200857.EAA12448@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Hello mathgroup,

as stated in previous messages, the minimum-radius circle problem is 
convex, but constrained: hence, an unconstrained optimization approach may 
or may not work... Using the convex hull as a constraint set will work, of 
course. NMInimize and other constrained optimizers should then also work, 
even in local search mode if they have that option.

Instead of further philosophical discussions on the subject, why don't we 
solve a standardized test model(s), using the same numerical example. (I 
assume here that SeedRandom is platform and version independent... as it 
should be.)

Here is a simple model-instance, for your perusal and experiments.

SeedRandom[1];
points = Partition[Table[Random[], {1000}], 2];
constraints = (#[[1]] - x0)^2 + (#[[2]] - y0)^2 <= r^2 & /@ points;
soln = NMinimize[{r, constraints}, {x0, y0, {r, 0, 10}}]
{0.6628150350002375, {r -> 0.6628150350002375, x0 -> 0.48684175822621106, 
y0 -> 0.46146943870460916}}

timedsoln = NMinimize[{r, constraints}, {x0, y0, {r, 0, 10}}] // AbsoluteTiming
{30.694136`8.938600406559628*Second, {0.6628150350002375,
  {r -> 0.6628150350002375, x0 -> 0.48684175822621106, y0 -> 
0.46146943870460916}}}

That is (on a P4 1.6 WinXP machine) it takes about 30 seconds to generate 
this solution.

Next, I solve the same model using the MathOptimizer Professional package, 
in local search mode:

Needs["MathOptimizerPro`callLGO`"]
callLGO[r, constraints, {{x0, 0, 1}, {y0, 0, 1}, {r, 0, 1}}, Method -> LS] 
// AbsoluteTiming
{6.158856`8.24104504348061*Second,
  {0.662815036, {x0 -> 0.4868417589, y0 -> 0.4614694394, r -> 0.662815036},
   4.770200900949817*^-11}}

The two solutions are fairly close (the solution methods are different). 
The MathOptimizer Professional (LGO) solver time is ~ 6 seconds. The result 
also shows that the max. constraint error of this solution is ~ 
4.770200900949817*^-11. (This error could be reduced, if necessary by 
changing the model and some LGO options.)

Obviously, one could use also more sophisticated models and other point 
sets etc., as long as we all use the same one(s), for objective 
comparisons. (The proof of the pudding principle.)

Regards,
Janos
_________________________________________________

Janos D. Pinter, PhD, DSc
President & Research Scientist, PCS Inc.
Adjunct Professor, Dalhousie University

129 Glenforest Drive, Halifax, NS, Canada B3M 1J2
Telephone: +1-(902)-443-5910
Fax: +1-(902)-431-5100; +1-(902)-443-5910
E-mail: jdpinter at hfx.eastlink.ca
Web: www.pinterconsulting.com     www.dal.ca/~jdpinter
Software products: http://www.pinterconsulting.com/Software_Sum_Info.pdf


• Follow-Ups:
  • Re: Re: Re: Re: FindMinimum and the minimum-radius circle
    • From: Daniel Lichtblau <danl@wolfram.com>

• References:
  • Re: FindMinimum and the minimum-radius circle
    • From: Thomas Burton <tburton@brahea.com>
  • Re: Re: FindMinimum and the minimum-radius circle
    • From: Thomas Burton <tburton@brahea.com>