Hi Richard,
Your convergence criterion is an x tolerance that you set to 1e-11.
The problem is that this tolerance is too small to achieve given the
limits of machine precision. In minimizing any function f(x), the
achievable tolerance in f is proportional to machine precision (albeit
possibly multiplied by a big constant factor depending on the
condition number of f), whereas the achievable tolerance in x is
actually only proportional to the square root of machine precision.
See, for example, section 10.1 in Numerical Recipes for a simple
discussion of this (you can see it from the Taylor expansion).
In your case, if you print out what the optimization is doing, it is
getting stuck around the local minimum with x oscillating by small
increments of 1e-9 or so, and roundoff errors make it literally
impossible for it to localize the minimum to the accuracy you requested.
In principle, it would be nice to have the MMA code detect this
situation and return an NLOPT_ROUNDOFF_LIMITED error code, rather than
looping forever (assuming I can find a reliable way to detect this
situation). But in any case I would recommend setting an achievable x
tolerance (e.g. 1e-7), or setting additional stopping criteria like an
f tolerance or a maximum iteration count.
Steven
On Feb 25, 2011, at 3:09 PM, Richard Luczak wrote:
I downloaded NLopt package from website:
http://ab-initio.mit.edu/wiki/index.php/NLopt
and installed it on my Suse Linux machine with gcc compiler.
I'm evaluating NLopt using 2-dimensional optimization problem
defined as follows:
max f(x,y)
where the objective function
f(x,y) = exp(sin(5 * pi * x)) + sin(3 * pi * y) + x + y
is defined over hypercube [0,1]^2.
It is easy to show that this function has six local maxima
and 2 local minima.
The code with implementation of the optimization problem in C
(file t1.c) as well as a graph of the objective function over
[0,0.2]x[0.8,1] (file t1.jpg) are attached. As an initial
guess I used
double x[] = {0.11822221293100121375, 0.86177726642352392439};
and set tolerance to
nlopt_set_xtol_rel (opt, 1.0e-11);
The code hangs and does not produce any results.
In another experiment I changed the initial guess to:
double x[] = {0.1, 0.8};
and tolerance to:
nlopt_set_xtol_rel (opt, 1.0e-15);
and I got correct results.
The code hanging in the first experiment is quite surprising
as the objective function is free of any singularities and
it is smooth (more precisely, it is infinitely differentiable).
I would appreciate your comments on the algorithm implemented
in NLopt as related to the problem described above.
Best regards,
Richard Luczak, PhD
[email protected]
<t1.c><t1.jpg>
_______________________________________________
NLopt-discuss mailing list
[email protected]
http://ab-initio.mit.edu/cgi-bin/mailman/listinfo/nlopt-discuss
