2
$\begingroup$

Which numerical methods would be optimal to find an extremum of a function with an almost flat "valley" (but a single minimum in the middle of the valley)? In this context optimal means the least number of function evaluations.

For simplicity's sake, assume that it's a two-dimensional problem. Also, of importance may be that I am more interested not in the coordinates of the extremum, but the value of the function in it.

For reference, the Rosenbrock function is $$f(x,y) = (1-x)^2 + 100(y-x^2)^2$$

I am using the term "'Rosenbrock'-like", because I have not yet defined the function itself. The problem I am solving is that of nonlinear equality constraint optimization, which I believe I have reduced to a global optimization of a function with a "valley" along the constraint.

$\endgroup$
  • $\begingroup$ Is the objective function actually a sum of squares? Is objective function at least twice continously differentiable? $\endgroup$ – Brian Borchers Jun 2 '14 at 19:52
  • $\begingroup$ @BrianBorchers It is not a sum of squares... but I do think it can be assumed to be sufficiently smooth. $\endgroup$ – Aahz Jun 2 '14 at 20:07
  • $\begingroup$ Can you compute the gradient of the objective function reasonably efficiently? What about the Hessian? $\endgroup$ – Brian Borchers Jun 2 '14 at 20:31
  • $\begingroup$ @BrianBorchers Well, as I have said, I am yet to define the precise function... But in general - I think we can compute the gradient (and the Hessian). $\endgroup$ – Aahz Jun 3 '14 at 5:04
2
$\begingroup$

If you have an easy access to the Hessian (as would be possible with the Rosenbrock function), then you should use a second-order method, such as the Newton Raphson method. It is both easy to implement and quadratically convergent for a sufficiently "nice" function (see the conditions here)

$\endgroup$
  • $\begingroup$ First of all, Newton-Raphson is for finding roots, not minima, so I suppose you suggest using it on the "derivative" of my function. The problem with that is that the valley is very flat (as with the rosenbrock case), and the derivative there essentially vanishes, which makes the gradient based methods lose efficiency. $\endgroup$ – Aahz Aug 17 '14 at 12:22
  • $\begingroup$ The link I used point to Newton Raphson's method in optimization, which explain that you should use it on the derivative of the function you want to optimize... And yes, the valley is very flat, which makes gradient based method unefficient. This is why you could associate it with a line search in order to reduce the number of iterations necessary. $\endgroup$ – Etienne Pellegrini Aug 17 '14 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.