2

Let $f$ be convex and twice differentiable. I can't prove that $$ \nabla^2f(x)\preceq LI \implies ||\nabla f(x)-\nabla f(y)||_2\leq L||x-y||_2 $$ I only established the converse.

edit:

There exists a $z\in\text{conv}\{x,y\}$ such that $$ \nabla f(y) = \nabla f(x) + \nabla^2 f(z)(y-x) $$ By multiplying on the left by $(y-x)^T$ we get $$ \begin{align} (y-x)^T \nabla f(y) &= (y-x)^T \nabla f(x) + (y-x)^T \nabla^2 f(z)(y-x)\\ &\leq (y-x)^T \nabla f(x) + L||y-x||_2^2 \end{align} $$ Now how do we prove that $$ (\nabla f(y) - \nabla f(x))^T (y-x) \leq L||y-x||_2^2 \implies \nabla f\text{ is }L\text{-lipschitz continuous}? $$ I think I'm missing something very easy.

Kiuhnm
  • 746

2 Answers2

4

Let $g(t) = \nabla f(y + t(x-y))$ and note $g'(t) = [\nabla^2 f(y + t(x-y))] (x-y)$. By the fundamental theorem of calculus, \begin{align} \|\nabla f(y) - \nabla f(x)\| &= \|g(1) - g(0)\| \\ &= \left\| \int_0^1 g'(t) \mathop{dt}\right\| \\ &\le \int_0^1 \|g'(t)\| \mathop{dt} \\ &= \int_0^1 \|[\nabla^2 f(y + t(x-y))] (x-y)\| \mathop{dt} \\ &\le \int_0^1 L \|x-y\| \mathop{dt} \\ &= L\|x-y\|. \end{align}

angryavian
  • 89,882
2

It would be convienient to directly call upon the so called "multivariable mean value theorem", which can be stated as following:

Let $F=(f_1,...,f_n)$ be a $C^1$ map from $\mathbb{R}^n \to\mathbb{R}^m $ on an open set in $\mathbb{R}^n$ that contains points $x, x+h$ and the line segment $x+th$ for $0\leq t\leq 1$. Then there exists numbers $\theta_1,...,\theta_n$, with $0\leq \theta_i\leq 1$ s.t. $$F(x+h) - F(x) = Mh,$$ where $M$ is the $m\times n$ matrix whose $i$-th row is $\nabla f_i(x+\theta_ih)$.

Applying the theorem to this problem gives us $$\|\nabla f(x)-\nabla f(y) \|_2 = \|M(x-y)\|_2 \leq \|M\|_{op}\|x-y\|_2 \leq L\|x-y\|_2.$$

Note that the converse can also be established with this line.

Bihu Duo
  • 568