Multivariable Calculus – Lipschitz Condition and Convex Function

convex optimizationconvex-analysisinequalitymultivariable-calculusproof-writing

Pg 12 – 14 http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf

Def: A $C^1$ convex function $f$ is Lipschitz smooth if $\exists L > 0$ s.t. $\forall x, y\in \mathbb{R}^n$
\begin{equation}
\|\nabla f(x) – \nabla f(y)\| \leq L\|x – y\|
\end{equation}

Claim: A $C^1$ convex function $f$ that satisfies $$f(y) \leq f(x) + \nabla f(x)^T(y-x) + \dfrac{L}{2}\|y-x\|^2$$ is Lipschitz Smooth

(Note: 1. the reverse implication is referred to as the "quadratic upper bound property" 2. One poster suggested to use fenchel duality to show this Lipschitz Smoothness, Strong Convexity and the Hessian)

Proof attempt:

It seems that the direct approach is through re-arrange and combine, which gives:
$$0 \leq (\nabla f(x)-\nabla f(y))^T(y-x) + L\|y-x\|^2$$
$$(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$$

Using CS-inequality on the above $(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$ gives:

$$(\nabla f(y)-\nabla f(x))^T(y-x) \leq \|\nabla f(y)-\nabla f(x)\|\|y-x\|$$
Now I have:

  1. $$(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$$

  2. $$(\nabla f(y)-\nabla f(x))^T(y-x) \leq \|\nabla f(y)-\nabla
    f(x)\|\|y-x\|$$

How do I conclude $\|\nabla f(x) – \nabla f(y)\| \leq L\|x – y\|$?

Best Answer

Co-coercivity of the gradient (Lecture 1, slides 15-16 in Vandenberghe's 236c notes) tells us that $$ \frac{1}{L} \| \nabla f(y) - \nabla f(x) \|^2 \leq (\nabla f(y) - \nabla f(x))^T (y - x) $$ for all $x,y$. Now combine this with your equation 1) to conclude that $$ \| \nabla f(y) - \nabla f(x) \| \leq L \| y - x \| $$ for all $x,y$.

Related Question