Mostrar que Lipschitz $\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$ es implícita por $f(y) \leq f(x) + \nabla f(x)^T(y-x) + \dfrac{L}{2}\|y-x\|^2$

Question

Pagina 12 - 14 http://www.seas.ucla.edu/~vandenbe/C 236/conferencias/degradado.pdf

Def: $C^1$ convexa de la función $f$ es de Lipschitz suave si $\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}

Reclamo: Un $C^1$ convexa de la función $f$ que satisface $$f(y) \leq f(x) + \nabla f(x)^T(y-x) + \dfrac{L}{2}\|y-x\|^2$$ es de Lipschitz Suave

(Nota: 1. la implicación inversa se conoce como la "ecuación cuadrática límite superior de la propiedad" 2. Uno de los carteles sugiere utilizar dualidad de fenchel para mostrar este Lipschitz Suavidad, Fuerte Convexidad y el de Hesse)

Prueba de intento:

Parece que el enfoque directo es a través de la re-organizar y combinar, lo que da: $$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$$

Con CS-desigualdad en la anterior $(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$ le da:

$$(\nabla f(y)-\nabla f(x))^T(y-x) \leq \|\nabla f(y)-\nabla f(x)\|\|y-x\|$$ Ahora tengo:

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

¿Cómo llego a la conclusión de $\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$?

---

Answer 1

Co-coercitividad de la gradiente (clase 1, diapositivas 15-16 en Vandenberghe del c 236 notas) nos dice que $$ \frac{1}{L} \| \nabla f(y) - \nabla f(x) \|^2 \leq (\nabla f(y) - \nabla f(x))^T (y - x) $$ para todos los $x,y$. Ahora combine esto con la ecuación 1) a la conclusión de que $$ \| \nabla f(y) - \nabla f(x) \| \leq L \| y - x \| $$ para todos los $x,y$.