Convexité et continuité Lipschitz

Question

C'est probablement une question facile, mais d'une manière ou d'une autre, je suis coincé.

Question L'affirmation suivante est-elle vraie? Si oui, comment le prouver?

Supposer que $f\in C^1(\mathbb{R}^n)$ est convexe et $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ pour certains $L>0$ et tout $x,y\in\mathbb{R}^n$. S'ensuit-il que$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ pour tous $x,y\in\mathbb{R}^n$?

Answer 1

C'est un résultat standard dans l'optimisation convexe. Par exemple, le théorème 2.1.5 des «Conférences d'introduction à l'optimisation convexe» de Nesterov déclare que les éléments suivants sont équivalents:

• $f$ est $C^1$, convexe et le dégradé $\nabla f$ est $L$-Lipschitz
• pour tous $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
• pour tous $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
• pour tous $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(Au cas où vous seriez intéressé: la preuve existe directement pour $C^1$ et aucune dérivée secondaire n'est utilisée aux étapes intermédiaires.)

Answer 2

Oui

Considérons d'abord le cas où $f\in{\cal C}^2$. Puis$$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ Il suit $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ Maintenant, l'hypothèse vous dit que $\|{\rm D}^2f(x+t(y-x))\|\le L$, d'où le résultat.

Maintenant, le cas général peut être obtenu par un argument de densité. Soit une fonction convexe$f$satisfaire votre hypothèse. Pour$\epsilon>0$, et nous définissons une fonction convexe lisse $f_\epsilon$ par inf-convolution: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Appliquer le résultat à $f_\epsilon$, puis passez à la limite comme $\epsilon\rightarrow0$.

Answer 3

Cette réponse est une petite modification de la réponse de Denis Serre. J'ai ajouté pour la commodité du lecteur: (1) le résultat est légèrement plus général; (2) la réponse contient beaucoup plus de détails; (3) J'utilise une convolution par approximation de mollification au lieu d'une inf-convolution.

Puisque les fonctions convexes satisfont $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ il suffit de prouver le résultat plus général suivant.

Théorème. Laisser$f\in C^1(\mathbb{R}^n)$ et laissez $L>0$.Ensuite, les conditions suivantes sont équivalentes: \ begin {equation} (1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ langle \ nabla f (x) - \ nabla f (y), xy \ rangle | \ leq L | xy | ^ 2 \ quad \ text {pour tous$x,y\in\mathbb{R}^n$.} \ end {équation} \ begin {équation} (2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ nabla f (x) - \ nabla f (y) | \ leq L | xy | \ quad \ text {pour tous$x,y\in\mathbb{R}^n$.} \ end {équation}

Preuve. Bien que l'implication (2) à (1) soit évidente, l'autre ne l'est pas, nous allons donc prouver l'implication de (2) à (1) maintenant. Supposons d'abord que$f\in C^\infty(\mathbb{R}^n)$. Pour$|u|=1$, (1) donne, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ passant ainsi à la limite comme $t\to 0$ donne $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ Depuis $D^2 f(x)$ est une matrice symétrique, le théorème spectral implique que l'opérateur norme de la matrice $D^2f(x)$ satisfait $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$Cette estimation implique cependant facilement le résultat \ begin {équation} \ 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 {split} \ end {equation} Ceci complète la preuve quand$f\in C^\infty$. Supposons maintenant que$f\in C^1$ et laissez $f_\epsilon=f*\varphi_\epsilon$être une approximation standard par convolution. Rappeler que$f_\epsilon\in C^\infty$ et $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. Nous avons \ begin {équation} \ 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 {equation} où la dernière inégalité est une conséquence de (1) et$\int_{\mathbb{R}^n}\varphi_\epsilon=1$. Depuis$f_\epsilon\in C^\infty$, la première partie de la preuve donne $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ et le résultat suit en passant à la limite comme $\epsilon\to 0$.

Answer 4

Une réponse partielle: si vous êtes prêt à renforcer votre hypothèse et à supposer $f\in C^2(\mathbb{R}^n)$, alors oui. Sinon, je ne suis pas sûr.

---

Des fonctions qui satisfont - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ sont appelées "L-semi-concaves", et les fonctions qui satisfont - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ sont appelés "L-smooth".

Si $f\in C^2(\mathbb{R}^n)$ est à la fois au moins L-semi-convexe (en particulier, convexe) et au moins L-semi-convave - alors il est en effet L-lisse.

On peut le prouver en considérant le Hessian $\nabla^2f$ de $f$: la convexité implique qu'elle est semi-définie positive, et la semi-concavité implique que $\nabla^2f-\frac{1}{2}\mathrm{Id}$est semi-défini négatif. Par conséquent, l'opérateur-norme de$\nabla^2f$ doit être borné, ce qui signifie que $\nabla f$ est Lipschitz (ie $f$ est L-lisse).

Je ne sais pas si cela tient toujours sous l'hypothèse la plus faible $f\in C^1(\mathbb{R}^n)$.