0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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<m^2/L$ 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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.