Prove that if $f$ is convex, $f(z) < f(x) $, $g ∈ ∂f(x)$, then for small $t > 0 $: $$‖x − tg − z\|^2 ≤ ‖x − z‖^2.$$


It's equivalent to show $\Vert x − tg − z\Vert_2^2 ≤ \Vert x − z\Vert_2^2$,

That is to show $x^Tx+z^Tz+tg^Ttg-2x^Tz-2x^Ttg+2z^Ttg\le x^Tx+z^Tz-2x^Tz$

That is to show $tg^T(tg+2(z-x))\le 0$.

since $t>0$, that is to show $tg^Tg+2g^T(z-x)\le 0$ (1).

By the definition of subgradient, $\forall y, f(y)\ge f(x)+g^T(y-x)$.

So $f(z)\ge f(x)+g^T(z-x) \Rightarrow 0>f(z)-f(x)\ge g^T(z-x)$

Go back to (1) , since $2g^T(z-x)<0$, one can always find a small $t$ such that (1) is satisfied.


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