# Boyd & Vandenberghe, page 488 — convergence analysis of Newton's method

On page 487 of Boyd & Vandenberghe's Convex Optimization, the convergenge analysis of Newton's method (Algorithm 9.5) is based on the backtracking line search. My questions are around (9.33) on Page 488. The assumption is $$\eta \leq m^2/L$$ where $$m$$ is the constant of strongly convexity, and $$L$$ is the Lipschitz constant for the Hessian of $$f$$, i.e., $$\nabla^2f(x)$$.

1. In the paragraph under (9.33), it says that if $$\left\|\nabla f\left(x^{(k)}\right)\right\|_{2}<\eta$$, then $$\left\|\nabla f\left(x^{(k+1)}\right)\right\|_{2}<\eta$$ because of $$\eta\leq m^2/L$$. Why is this? How can we get this result for the iteration $$k+1$$? That is to say, $$\left\|\nabla f\left(x^{(l)}\right)\right\|_{2}<\eta$$ holds for all $$l\geq k$$.

2. Also, in the end of that paragraph, it says that '' Therefore for all $$l\geq k$$, the algorithm takes a full Newton step $$t=1$$''. Why is $$t^{(k)}=1$$ once $$\left\|\nabla f\left(x^{(k)}\right)\right\|_{2}<\eta$$, not a number less than $$1$$?

• Listed Commented Oct 25, 2021 at 16:18

## 2 Answers

For the first question, let $$g(t)=\|\nabla f(x+t\Delta x_{nt})\|_2^2$$ with $$t\ge 0$$, then since $$\Delta x_{nt}=-\nabla^2f(x)^{-1}\nabla f(x)$$ we have

\begin{aligned} g'(t) &= 2\nabla f(x+t\Delta x_{nt})^T \nabla^2 f(x+t\Delta x_{nt})\Delta x_{nt} \end{aligned} \begin{aligned} g'(0) &= 2\nabla f(x)^T\nabla^2 f(x)\Delta x_{nt}\\ &=2\nabla f(x)^T\nabla^2 f(x)(-\nabla^2f(x)^{-1}\nabla f(x))\\ &=-2\nabla f(x)^T\nabla f(x)\\ &<0 \end{aligned} Since $$g'(t)$$ is continuous, there exists $$t>0$$ such that $$g(t), i.e., $$\|\nabla f(x^{(k)}+t\Delta x^{(k)}_{nt})\|_2^2=\|\nabla f(x^{(k+1)})\|_2^2<\|\nabla f(x^{(k)})\|_2^2$$. But this has nothing to do with $$\eta\le m^2/L$$(we didn't use this condition in the above derivation) and only answers the first question, why is $$t=1$$ for all $$l\geq k$$?

The idea very briefly: Newton's method is (with obvious notations $$\nabla f_k=\nabla f(x_k)$$ etc) $$(x_{k+1}-x_k=)\quad\Delta x_k=-\nabla^2f_k^{-1}\nabla f_k\qquad\Leftrightarrow\qquad \nabla f_k+\nabla^2f_k\Delta x_k=0.$$

1. Taylor: $$\nabla f_{k+1}=\nabla f_k+\nabla^2f(\xi)\Delta x_k$$.
2. Estimate (use 1. + triangle inequality + Lipschitz) $$\nabla f_{k+1}=\nabla f_{k+1}-0=\nabla f_{k+1}-(\nabla f_k+\nabla^2f_k\Delta x_k)= (\nabla^2f(\xi)-\nabla^2f_k)\Delta x_k.$$
3. Estimate (triangle inequality + $$\nabla^2 f\ge m I$$) $$\Delta x_k=-\nabla^2f_k^{-1}\nabla f_k.$$ The result will read $$\|\nabla f_{k+1}\|\le\frac{L}{m^2}\eta^2.$$ The rest should be obvious by now.

For the extra $$1/2$$: use the integral form of the remainder

1. Taylor: $$\nabla f_{k+1}=\nabla f_k+\int_0^1\nabla^2f(x_k+t\Delta x_k)\Delta x_k\,dt$$
2. Estimate: \begin{align} \|\nabla f_{k+1}\|&=\|\nabla f_{k+1}-(\nabla f_k+\nabla^2f_k\Delta x_k)\|\\ &=\left\|\int_0^1(\nabla^2f(x_k+t\Delta x_k)-\nabla^2f_k)\Delta x_k\,dt\right\|\\ &\le\int_0^1\|\nabla^2f(x_k+t\Delta x_k)-\nabla^2f(x_k)\|\cdot\|\Delta x_k\|\,dt.\\ &\le L\int_0^1 t\|\Delta x_k\|^2 dt\\ &= \frac{L}{2}\|\Delta x_k\|^2\\ &=\frac{L}{2}\|\nabla^2f_k^{-1}\nabla f_k\|^2\\ &\le \frac{L}{2m^2}\|\nabla f_k\|^2 \end{align}
• Your derivation is weaker. There is a 1/2, i.e. $\frac{L}{m^2}$, in (9.33) on Page 488. Your answer is helpful. Commented Oct 19, 2021 at 4:01
• @suineg Just to prevent misunderstanding: it is the proof of the statement 1 in your question, there is no $1/2$ in it. I am not proving (9.33).
– A.Γ.
Commented Oct 19, 2021 at 8:16
• @suineg if you need extra $1/2$ you should take the integral form of the remainder. I will update the question.
– A.Γ.
Commented Oct 19, 2021 at 8:48
• The integral form has been shown on Page 491 in B & V's book. Commented Oct 19, 2021 at 15:17
• @suineg Good. I see that you have got it.
– A.Γ.
Commented Oct 19, 2021 at 15:40