# Why is this inequality true in the proof of the convergence of Newton's method?

From Convex Optimization by Boyd & Vandenberghe:

Let $$f$$ be a twice continuously differentiable convex function that is strongly convex with constant $$m$$, i.e., $$\nabla^2 f(x) \succeq m I$$ for $$x \in S = \{x : f(x) \le f(x^{(0)})\}$$ for some starting point $$x^{(0)}$$ where $$S$$ is a closed set. Assume $$\|\nabla^2 f(x) - \nabla^2 f(y) \|_2 \le L \|x-y\|_2$$ for all $$x, y \in S$$.

The goal is to prove that there are numbers $$\eta$$ and $$\gamma$$ with $$0 \lt \eta \le m^2/L$$ and $$\gamma \gt 0$$ such that

If $$\|\nabla f(x^{(k)})\|_2 \lt \eta$$, then the backtracking line search selects $$t^{(k)} = 1$$ and $$(L/2m^2)\|\nabla f(x^{(k+1)})\|_2 \le ((L/2m^2)\|\nabla f(x^{(k)})\|_2)^2$$

Suppose it is satisfied for iteration $$k$$, i.e., $$||\nabla f(x^{(k)})||_2 \lt \eta.$$ Since $$\eta \le m^2 / L$$, we have $$||\nabla f(x^{(k+1)})||_2 \lt \eta$$.

Can someone explain how this last line is true? I've tried to prove it but I can't see any reason why $$\eta \le m^2/L \Rightarrow ||\nabla f(x^{(k+1)})||_2 \lt \eta$$.

## 1 Answer

In the last displayed inequality, notice that the RHS is squared. Rewrite the inequality: $$\|\nabla f(x^{(k+1)})\|_2\le\frac L{2m^2}\|\nabla f(x^{(k)})\|_2^2.\tag1$$ If $$\|\nabla f(x^{(k)})\|_2$$ is less than $$\eta$$, then its square is less than $$\eta^2$$. But $$\eta so the RHS of (1) is less than $$\frac L{2m^2}\eta\eta<\frac L{2m^2}\eta\frac{m^2}L=\frac12\eta<\eta.$$