Non-pathological example where Newton's method converges to a saddle point or local maximum

98 Views Asked by At

It is well known that Newton's method (with full step size) may converge to a saddle point or local maximum for some initial values (assuming it converges to something), but I have trouble visualizing it. I am always under the impression that such initial values have measure zero in the domain, because if you perturb the solution a little bit, it will have a non-zero gradient and can thus escape to somewhere with a lower value.

Can someone provide a non-pathological example where Newton's method does not converge to a local minimum, where "pathological" means the set of initial values leading to a saddle point or local maximum (i.e. basin of attraction) has measure zero? Preferably the example should also be simple so that it's easier to visualize it.

1

There are 1 best solutions below

0
On BEST ANSWER

For converging to a maximum, Nick Alger provided an answer in their comment

Just take any function that Newton's method would converge to a minimum, and flip it upside down. Now Newton's method will converge to a maximum. Negative eigenvalues of the hessian flip the direction of the gradient.

For converging to a saddle point, consider $f(x) = x^3$ and any initial value. The update is

\begin{equation} x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} = x_k - \frac{3x_k^2}{6x_k} = \frac{1}{2} x_k \end{equation}

As a result, the algorithm will converge to the saddle point $x = 0$ regardless of the initialization.