2
$\begingroup$

I am reading Numerical Optimization by Nocedal & Wright, and I am having trouble understanding some aspects of the proof of Theorem $3.7$. I have been stuck on this theorem for many hours, so any help is greatly appreciated.

There are two things I don't understand:

  1. The theorem is an iff statement. The author proves one direction, but I don't see how to prove the reverse.

  2. The author seems to use the assumption that the Hessian is Lipschitz, but this is not an explicit assumption of the theorem. Is this a mistake from the author? (I checked the errata and this wasn't on there)

The following are several lines the author references in the proof. The theorem and the proof follows.

$$\|x_k + p_k^N - x^*\| \le L\|x_k - x^*\|^2 \tag{3.33}$$ (The above is where my point #2 comes from. This inequality was derived in the proof of an earlier theorem about quadratic convergence of Newton's Method and in that theorem we had a hypothesis that the Hessian is Lipschitz, which was used to prove the above inequality.) $$p_k = -B_k^{-1} \nabla f_k \hspace{1cm} \tag{3.34}$$ where $B_k$ is symmetric and pos. def., $$\lim_{k \to \infty} \frac{\|(B_k - H_f(x^*))p_k\|}{\|p_k\|} = 0 \tag{3.36}$$

Theorem $\textbf{3.7}$: Suppose that $f:\mathbb{R}^n \to \mathbb{R}$ is twice continuously differentiable. Consider the iteration $x_{k+1} = x_k + p_k$ (that is, the step length $\alpha_k$ is uniformly $1$) and that $p_k$ is given by $(3.34)$. Let us assume also that $(x_k)$ converges to a point $x^*$ such that $\nabla f(x^*) = 0$ and $H_f(x^*)$ is positive definite. Then $(x_k)$ converges superlinearly if and only if $(3.36)$ holds.

Proof: We first show that $(3.36)$ is equivalent to $$p_k - p_k^N = o(\|p_k\|) \tag{3.37}$$ where $p_k^N = - H_f(x_k)^{-1} \nabla f_k$ is the Newton step. Assuming $(3.36)$ holds, we have that \begin{align*} p_k - p_k^N & = H_{f}(x_k)^{-1}(H_f(x_k)p_k + \nabla f_k)\\ &= H_{f}(x_k)^{-1}(H_{f}(x_k) - B_k)p_k\\ &= O(\|(H_f(x_k) - B_k)p_k\|)\\ &= o(\|p_k\|) \end{align*} where we have used the fact that $\|H_f(x_k)^{-1}\|$ is bounded above for $x_k$ sufficiently close to $x^*$, since the limiting Hessian $H_f(x_*)$ is positive definite. The converse follows readily of we multiply both sides of $(3.37)$ by $H_f(x_k)$ and recall $(3.34)$.

By combining $(3.33)$ and $(3.37)$, we obtain that $$\|x_k+p_k-x^*\| \le\|x_k+p_k^N-x^*\|+\|p_k-p_k^N\|=O(\|x_{k}-x^*\|^2)+o(\|p_k\|).$$ A simple manipulation of this inequality reveals that $\|p_k\| = O(\|x_k - x^*\|),$ so we obtain $$\|x_k+p_k-x^*\| \le o(\|x_k-x^*\|),$$ giving the superlinear convergence result.

$\endgroup$

1 Answer 1

4
+500
$\begingroup$

The proof of this theorem does have a few places to be patched up. For Question 2, the proof uses (3.33) but it only needs a weaker form:\begin{gather*} x_k + p^N_k - x^* = o(\|x_k - x^*\|) \quad (k → ∞),\tag{3.33$'$} \end{gather*} In fact, by the Taylor expansion,$$ ∇f(x) = ∇f(x^*) + Hf(x^*) (x - x^*) + o(\|x - x^*\|) \quad (x → x^*). $$ Note that $∇f(x^*) = \boldsymbol{0}$, $p^N_k = -(Hf(x_k))^{-1} ∇f(x_k)$, and $\|(Hf(x))^{-1}\|$ is bounded in the neighborhood of $x^*$. Because $(Hf(x))^{-1} Hf(x^*) → I$ as $x → x^*$, so\begin{align*} &\mathrel{\phantom{=}}{} x_k + p^N_k - x^* = (x_k - x^*) - (Hf(x_k))^{-1} ∇f(x_k)\\ &= (x_k - x^*) - (Hf(x_k))^{-1} Hf(x^*) (x_k - x^*) + o(\|x_k - x^*\|)\\ &= (I - (Hf(x_k))^{-1} Hf(x^*)) (x_k - x^*) + o(\|x_k - x^*\|)\\ &= o(\|x_k - x^*\|) \quad (k → ∞). \end{align*}

Now for question 1, since (3.36) and (3.37) are equivalent, it suffices to prove that$$ x_k + p_k - x^* = o(\|x _k- x^*\|) \ (k → ∞) \Longleftrightarrow p_k - p^N_k = o(\|p_k\|) \ (k → ∞). $$ On the one hand, if $p_k - p^N_k = o(\|p_k\|)$ ($k → ∞$), then$$ \|p_k\| - \|p_k - p^N_k\| \leqslant \|p^N_k\| \leqslant \|p_k\| + \|p_k - p^N_k\| $$ implies that $\|p^N_k\| \sim \|p_k\|$ ($k → ∞$), so\begin{gather*} p_k - p^N_k = o(\|p_k\|) = o(\|p^N_k\|)\\ = o(\|(Hf(x_k))^{-1} (x_k - x^*)\|) = o(\|x_k - x^*\|) \quad (k → ∞). \end{gather*} Combining with $\|x_k + p_k - x^*\| \leqslant \| x_k + p^N_k - x^*\| + \|p_k - p^N_k\|$ and (3.33$'$) yields$$ x_k + p_k - x^* = o(\|x_k - x^*\|) \quad (k → ∞). $$ On the other hand, if $x_k + p_k - x^* = o(\|x _k- x^*\|)$ ($k → ∞$), then$$ \|p_k - p^N_k\| \leqslant \|x_k + p_k - x^*\| + \| x_k + p^N_k - x^*\| $$ and (3.33$'$) imply that$$ \|p_k - p^N_k\| = o(\|x_k - x^*\|) = o(\|p^N_k\|) \quad (k → ∞). $$ Combining with$$ \|p^N_k\| - \|p_k - p^N_k\| \leqslant \|p_k\| \leqslant \|p^N_k\| + \|p_k - p^N_k\| $$ yields $\|p_k\| \sim \|p^N_k\|$ ($k → ∞$) and$$ \|p_k - p^N_k\| = o(\|p^N_k\|) = o(\|p_k\|) \quad (k → ∞). $$

$\endgroup$
1
  • $\begingroup$ Thank you so much for the answer! I'll have to read it thoroughly later when I have more time. It's increadible, I've never seen an author leave this much work to the reader. $\endgroup$
    – Blue
    Commented May 25, 2020 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .