Context

Consider the unconstrained optimization problem of the following one dimensional function $$f(x) : \mathbb{R} \mapsto \mathbb{R}$$ : \begin{align} minimize\ f(x) = x^4-1 \end{align} With : \begin{align} f'(x) &= 4x^3 \\ f''(x) &= 12x^2 \end{align} Clearly this is a convex function albeit not a strongly convex function with an optimal cost $$x^* = 0$$. To solve this optimization problem, I apply pure Newton's method (stepsize 1) : \begin{align} x_{k+1} &= x_k + \alpha_k d_k \\ \alpha_k &= 1 \\ d_k &= -\nabla_{xx}^2f(x_k)^{-1} \nabla_x f(x_k) \end{align} In this case : \begin{align} x_{k+1} &= x_k - \frac{4x_k^3}{12x_k^2} \\ x_{k+1} &= x_k - \frac{1}{3}x_k \end{align}

Since it is an unconstrained optimization problem, every $$x$$ is feasible. As an illustration, I provide three iterations starting with $$x_0 = 4$$ : \begin{align} x_1 &= 4 - \frac{4}{3} = \frac{8}{3} \\ x_2 &= \frac{8}{3}-\frac{8}{9} = \frac{16}{9} \\ x_3 &= \frac{16}{9}-\frac{16}{27} = \frac{32}{27} \end{align}

Question

The rate of convergence to the optimal cost $$x^* = 0$$ is linear : \begin{align} \frac{x_{k+1}-x^*}{x_k-x^*} = \frac{x_k-\frac{1}{3}x_k}{x_k} = \frac{2}{3} \end{align} Contrarily to what would be expected for Newton's method, the rate of convergence is merely linear and not quadratic.

I suspect that the reason for this sub-optimal rate of convergence is that the objective function is not strongly convex ($$\nabla_{xx}^2f(0)=0$$) but I would like an explanation of what is precisely going on.

• This drop in the convergence rate happens because the zero of the derivative of your objective function is a multiple root, i.e. not only the derivative $g = f'$, but higher derivatives of $g$ up to order $n$ also vanish. In that case the convergence is known to drop to linear, specifically the ratio in your last equation approaches $\frac{n}{n+1}$ as $x_k \to x^\ast$. Here, $n = 2$. For a detailed discussion, consider this post math.stackexchange.com/questions/389368/… or any other source on Newton's method. Jan 11, 2022 at 15:00

Note that even if $$f$$ is strongly convex, Newton' method with stepsize 1 can still fail to converge if it is initialized too far away.

A standard example to that effect is: $$f(x) = \frac{1}{10}x^2 + \sqrt{1 + x^2}$$.

Then, $$f'(x) = \left( \frac{1}{5} + \frac{1}{\sqrt{1 + x^2}} \right) x$$

and $$f''(x) = \frac{1}{5} + \frac{1}{\sqrt{1 + x^2}^3}$$.

This function is indeed strongly convex since $$f''(x) \geq 1/5$$ for all $$x$$. We can even say that its first derivative is Lipschitz continuous since $$f''(x) \leq 6/5$$ for all $$x$$.

Newton's method with unit stepsize results in the following iteration: $$x_{k+1} = F(x_k)$$, where

$$F(x) = x - \frac{f'(x)}{f''(x)}.$$

You can check that Newton's method can "converge" to a cycle that oscillates between $$+4.3956$$ and $$-4.3956$$ (roughly). To confirm that, you can plot $$G(x) = F(F(x))$$ and see that $$G(x) = x$$ for $$x \approx 4.3956$$ (so it's a fixed point of the double iteration), and that $$|G'(x)| < 1$$ for that value of $$x$$ (so the fixed point is stable).