Newton's Method — The Saddle Point Problem

Background

The double-well function

$$f(x_1, x_2) = (x_1^2 - 1)^2 + \frac{1}{2}x_2^2$$

This function has two global minima at $\mathbf{x}^* = (\pm 1,\,0)$ with $f = 0$, and a saddle point at the origin $(0,0)$ with $f = 1$. It serves as a minimal, transparent example where pure Newton's method does not converge to a minimum.

Gradient and Hessian

$$\nabla f = \begin{pmatrix}4x_1(x_1^2-1)\\x_2\end{pmatrix}, \qquad \mathbf{H}(x_1,x_2) = \begin{pmatrix}12x_1^2-4 & 0\\0 & 1\end{pmatrix}$$

At the saddle: $\mathbf{H}(0,0) = \text{diag}(-4,\;1)$. One eigenvalue is negative — the Hessian is indefinite. The quadratic Taylor model $q(\mathbf{x}) = f + \nabla f^\top \delta + \frac{1}{2}\delta^\top\mathbf{H}\delta$ is then unbounded below: it has no global minimizer.

Non-convex regions (checkbox 1)

The smaller Hessian eigenvalue $12x_1^2 - 4$ is negative wherever $$|x_1| < \frac{1}{\sqrt{3}} \approx 0.577.$$ Inside this vertical strip the function is locally non-convex. Enable the first checkbox to highlight the non-convex part of the surface in orange.

Why Newton converges to the saddle

Newton's update $\mathbf{x}_{n+1} = \mathbf{x}_n - \mathbf{H}^{-1}\nabla f$ minimizes the local quadratic model. When the Hessian is indefinite, the "minimizer" of that unbounded model can be a saddle point of $f$. Starting near $(0.10,\;1.00)$: the Hessian at that point is $\mathbf{H} \approx \text{diag}(-3.88,\;1)$, and the Newton step lands almost exactly on the saddle $(0,0)$ in one iteration. Once there, $\nabla f = \mathbf{0}$ and the method stalls — at a point that is not a local minimum.

Projected Newton — eigenvalue clamping (checkbox 2)

One standard remedy is to replace $\mathbf{H}$ by a positive-definite surrogate $\mathbf{H}_\varepsilon$ obtained by clamping all eigenvalues from below: $$\mathbf{H}_\varepsilon = \mathbf{V}\,\text{diag}\!\bigl(\max(\lambda_1,\varepsilon),\; \max(\lambda_2,\varepsilon)\bigr)\,\mathbf{V}^\top, \qquad \varepsilon > 0,$$ where $\mathbf{H} = \mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^\top$ is the eigendecomposition. Because $\mathbf{H}_\varepsilon \succ 0$, the modified step $\mathbf{x}_{n+1} = \mathbf{x}_n - \mathbf{H}_\varepsilon^{-1}\nabla f$ is always a descent direction ($\nabla f^\top \mathbf{H}_\varepsilon^{-1} \nabla f > 0$). A backtracking line search (Armijo condition) is applied to control the step length and guarantee a sufficient decrease in $f$.

Use the slider to vary $\varepsilon$ and observe the trade-off: large $\varepsilon$ strongly deflects the step away from the saddle but slows convergence (it resembles gradient descent when $\varepsilon \gg \|\mathbf{H}\|$); small $\varepsilon$ keeps close to the original Newton step and converges faster once the iterates leave the non-convex region.

In practice, eigenvalue clamping is combined with a line search or trust-region strategy.