Convexidad y continuidad de Lipschitz

Question

Probablemente sea una pregunta fácil, pero de alguna manera estoy estancado.

Pregunta ¿Es verdadera la siguiente afirmación? Si es así, ¿cómo probarlo?

Suponer que $f\in C^1(\mathbb{R}^n)$ es convexo y $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ para algunos $L>0$ y todo $x,y\in\mathbb{R}^n$. ¿Sigue eso?$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ para todos $x,y\in\mathbb{R}^n$?

Answer 1

Ese es un resultado estándar en la optimización convexa. Por ejemplo, el teorema 2.1.5 de las "Conferencias introductorias sobre optimización convexa" de Nesterov establece que lo siguiente son equivalentes:

• $f$ es $C^1$, convexo y el gradiente $\nabla f$ es $L$-Lipschitz
• para todos $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
• para todos $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
• para todos $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(En caso de que esté interesado: la prueba que hay directamente es para $C^1$ funciones y no se utilizan segundas derivadas en los pasos intermedios).

Answer 2

sí

Considere primero el caso donde $f\in{\cal C}^2$. Luego$$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ A continuación sigue $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ Ahora, la suposición te dice que $\|{\rm D}^2f(x+t(y-x))\|\le L$, de ahí el resultado.

Ahora, el caso general se puede obtener mediante un argumento de densidad. Sea una función convexa$f$satisfaga su suposición. Para$\epsilon>0$, definamos una función convexa suave $f_\epsilon$ por inf-convolution: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Aplicar el resultado a $f_\epsilon$, luego pase al límite como $\epsilon\rightarrow0$.

Answer 3

Esta respuesta es una pequeña modificación de la respuesta de Denis Serre. Agregué para comodidad del lector: (1) el resultado es un poco más general; (2) la respuesta contiene muchos más detalles; (3) Estoy usando una convolución por aproximación de suavización en lugar de inf-convolución.

Dado que las funciones convexas satisfacen $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ basta para probar el siguiente resultado más general.

Teorema. Dejar$f\in C^1(\mathbb{R}^n)$ y deja $L>0$Entonces las siguientes condiciones son equivalentes: \ begin {ecuación} (1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ langle \ nabla f (x) - \ nabla f (y), xy \ rangle | \ leq L | xy | ^ 2 \ quad \ text {para todos$x,y\in\mathbb{R}^n$.} \ end {ecuación} \ begin {ecuación} (2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ nabla f (x) - \ nabla f (y) | \ leq L | xy | \ quad \ text {para todos$x,y\in\mathbb{R}^n$.} \ end {ecuación}

Prueba. Si bien la implicación (2) a (1) es obvia, la otra no lo es, así que probaremos la implicación de (2) a (1) ahora. Suponga primero que$f\in C^\infty(\mathbb{R}^n)$. Para$|u|=1$, (1) rendimientos, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ así que pasando al límite como $t\to 0$ da $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ Desde $D^2 f(x)$ es una matriz simétrica, el teorema espectral implica que la norma del operador de la matriz $D^2f(x)$ satisface $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$Sin embargo, esta estimación implica fácilmente el resultado \ begin {ecuación} \ begin {split} & | \ nabla f (x) - \ nabla f (y) | = \ left | \ int_0 ^ 1 \ frac {d} {dt} \ nabla f (y + t (xy)) \, dt \ right | \\ & \ leq | xy | \ int_0 ^ 1 \ Vert D ^ 2f (y + t (xy)) \ Vert \, dt \ leq L | xy |. \ end {dividir} \ end {ecuación} Esto completa la prueba cuando$f\in C^\infty$. Asume ahora que$f\in C^1$ y deja $f_\epsilon=f*\varphi_\epsilon$ser una aproximación estándar por convolución. Recordar que$f_\epsilon\in C^\infty$ y $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. Tenemos \ begin {ecuación} \ begin {split} & | \ langle \ nabla f_ \ epsilon (x) - \ nabla f_ \ epsilon (y), xy \ rangle | = \ Big | \ Big \ langle \ int _ {\ mathbb {R} ^ n} (\ nabla f (xz) - \ nabla f (yz)) \ varphi_ \ epsilon (z) \, dz, xy \ Big \ rangle \ Big | \\ & \ leq \ int _ {\ mathbb {R} ^ n} \ big | \ big \ langle \ nabla f (xz) - \ nabla f (yz)), (xz) - (yz) \ big \ rangle \ big | \, \ varphi_ \ epsilon ( z) \, dz \ leq L | xy | ^ 2, \ end {split} \ end {ecuación} donde la última desigualdad es una consecuencia de (1) y$\int_{\mathbb{R}^n}\varphi_\epsilon=1$. Desde$f_\epsilon\in C^\infty$, la primera parte de la prueba arroja $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ y el resultado sigue al pasar al límite como $\epsilon\to 0$.

Answer 4

Una respuesta parcial: si está dispuesto a fortalecer su suposición y suponer $f\in C^2(\mathbb{R}^n)$, entonces sí. De lo contrario, no estoy seguro.

---

Funciones que satisfacen - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ se llaman "L-semi-cóncava", y las funciones que satisfacen - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ se llaman "L-liso".

Si $f\in C^2(\mathbb{R}^n)$ es al menos L-semiconvexo (en particular, convexo) y al menos L-semiconvavo; entonces, de hecho, es L-suave.

Uno puede probarlo considerando la arpillera $\nabla^2f$ de $f$: la convexidad implica que es semidefinida positiva, y la semiconcavidad implica que $\nabla^2f-\frac{1}{2}\mathrm{Id}$es semidefinido negativo. Por tanto, el operador-norma de$\nabla^2f$ debe estar acotado, lo que significa que $\nabla f$ es Lipschitz (es decir $f$ es L-suave).

No estoy seguro de si todavía se mantiene bajo la suposición más débil $f\in C^1(\mathbb{R}^n)$.