4
$\begingroup$

I am trying to find the minimum of the so called Beale’s function given by

$f(x_1,x_2) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2$

Using Newton iteration

$x^{(k+1)} = x^{(k)} - \alpha^{(k)} \eta^{(k)} $ with $ \eta^{(k)} = \left( \frac{\partial ^2f}{\partial x^2}(x^{(k)}) \right)^{-1}\frac{\partial f}{\partial x}(x^{(k)})$

at point $x = [4 \ \ 1]^T$ with $\alpha = 0.5$. The result is $x_{num} = [0 \ \ 1]^T$, while the real minimum is at $x_{min} = [3 \ \ 0.5]^T$.

I found out the problem is, that $\eta$ is pointing in the wrong direction. It is not showing “downhill” like the gradient would. My question is, how is this possible? Why does the newton iteration is failing here?

EDIT: By the way, I get the some result if I start at $x = [4 \ \ 0.9]^T$. First happens some weird stuff and $x^{(k)}$ is jumping around but then it ends again in $x= [0 \ \ 1]^T$.

$\endgroup$
2
$\begingroup$

For unconstrained optimization problems, deterministic optimization methods converge to stationary points. Stationary points are points at which the gradient of the objective function is zero. These points are not necessarily optima, unless other conditions are met. For minimization problems, if the Hessian evaluated at a stationary point is positive semidefinite, then that stationary point is a local minimum. If the objective function is convex (equivalently, for twice continuously differentiable objective functions, the Hessian is positive semidefinite everywhere) then a stationary point is a global minimum.

The problem you're running into is that the objective function you are trying to minimize is nonconvex. As ChristianClason points out, you converge to a stationary point, but that stationary point is a saddle point, implying that your objective function is not convex, and thus, convergence to a global minimum is not assured.

$\endgroup$
3
$\begingroup$

Newton's method is a fixed point iteration for solving a nonlinear equation. In the context of optimizing a function $f(x)$, you apply this method to find a solution of the necessary optimality conditions $f'(x) = 0$. However, this condition characterizes all stationary points such as maximizers or saddle points, so the method is just as happy to give you one of those if they exist. Furthermore, Newton's method is only locally convergent, so it will give you the closest local minimizer (or maximizer) to your starting point (if it converges at all).

Beale's function has indeed a saddle point at $(0,1)$, since $\partial_x f(0,1) = \partial_y f(0,1) = 0$, but the Hessian $$ \begin{pmatrix} \partial_{xx} f(0,1) & \partial_{xy} f(0,1) \\ \partial_{xy} f(0,1) & \partial_{yy} f(0,1)\end{pmatrix} = \frac{111}{4}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$ has the eigenvalues $\pm 111/4$.

In fact, Beale's method is a popular torture test to illustrate why global minimizers are difficult to compute...

EDIT: Gradient methods with an appropriate line search have an additional mechanism that tries to enforce (sufficient) function value decrease and thus will avoid maximizers in most cases. They also tend to avoid saddle points (at least compared to Newton's method), but as Geoff Oxberry points out, there's no guarantee.

$\endgroup$
  • $\begingroup$ But $f(x,1) = \frac{909}{64}$ for all $x$. So starting at $[4 \ \ 1]$ means that $\eta$ is running on the same level curve. I don’t understand why $\eta$ does this. When I use only the Gradient and not Newton with a nonfixed $\alpha$ than the Gradient easily finds the minimum at $[3 \ \ 0.5]$. $\endgroup$ – solid Oct 28 '14 at 14:15
  • $\begingroup$ But the Hessian is invertebal here. $\endgroup$ – solid Oct 28 '14 at 14:35
  • $\begingroup$ @ChristianClason: I don't see why gradient methods couldn't return saddle points, since the accumulation points of the sequence of gradient descent iterates are stationary points. In practice, that tends not to be the case (they tend to converge to local minima), but it's not impossible. An example would be starting gradient descent at $(1,1)$ for the function $f(x,y) = xy$; the gradient is $(1,1)$, and a line search along that direction for a minimal value will yield a step of length $\sqrt{2}$, so the next iterate is $(0, 0)$, which is a saddle point. $\endgroup$ – Geoff Oxberry Oct 28 '14 at 20:29
  • $\begingroup$ @GeoffOxberry: You're right, of course, they will only avoid local maximizers. Whether the line search will steer you away from a saddle point or not depends very much on the local configuration. I'll edit that remark. $\endgroup$ – Christian Clason Oct 28 '14 at 22:25
  • $\begingroup$ (Unless you start in a maximizer, of course.) $\endgroup$ – Christian Clason Oct 28 '14 at 22:32
1
$\begingroup$

Others have already suggested solutions. My recommendation is to take a look at the book of Nocedal and Wright, "Numerical Optimization". The book has a whole section on "Hessian modification" for exactly the sort of problem you are observing. It is really very readable and lays out the problem and its solution in easy steps.

$\endgroup$
  • 1
    $\begingroup$ Modifying the Hessian to ensure positive definiteness will ensure that a Newton step is a descent direction. The algorithm still converges to stationary points, and thus may still converge to a saddle point or to a suboptimal local minimum in nonconvex problems. There's been some work on inertia-revealing factorizations for interior point methods that have a limited ability to overcome nonconvexity, but in general, nonconvexity still causes these methods to "break" and return local minima or saddle points. $\endgroup$ – Geoff Oxberry Oct 29 '14 at 18:50
  • $\begingroup$ Correct. All you get from most of these techniques is a stationary point. The question was that the OP was confused how it is possible that his Newton method doesn't produce a descent direction. My answer tries to point out a location where an answer and remedy to this aspect of the problem can be found. $\endgroup$ – Wolfgang Bangerth Oct 30 '14 at 2:48

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.