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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is the objective function actually a sum of squares? Is objective function at least twice continously differentiable? $\endgroup$
    – Brian Borchers
    Jun 2, 2014 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, 2014 at 20:07
  • $\begingroup$ Can you compute the gradient of the objective function reasonably efficiently? What about the Hessian? $\endgroup$
    – Brian Borchers
    Jun 2, 2014 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, 2014 at 5:04

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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