Convessità e continuità di Lipschitz

Question

Probabilmente è una domanda facile, ma in qualche modo sono bloccato.

Domanda La seguente affermazione è vera? Se sì, come dimostrarlo?

Supporre che $f\in C^1(\mathbb{R}^n)$ è convesso e $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ per alcuni $L>0$ e tutto $x,y\in\mathbb{R}^n$. Ne segue che$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ per tutti $x,y\in\mathbb{R}^n$?

Answer 1

Questo è un risultato standard nell'ottimizzazione convessa. Ad esempio il Teorema 2.1.5 nelle "Conferenze introduttive sull'ottimizzazione convessa" di Nesterov afferma che quanto segue sono equivalenti:

• $f$ è $C^1$, convesso e il gradiente $\nabla f$ è $L$-Lipschitz
• per tutti $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
• per tutti $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
• per tutti $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(Nel caso tu sia interessato: la prova che c'è direttamente per $C^1$ funzioni e nessuna derivata seconda viene utilizzata nei passaggi intermedi.)

Answer 2

sì

Considera prima il caso in cui $f\in{\cal C}^2$. Poi$$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ Segue $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ Ora, il presupposto te lo dice $\|{\rm D}^2f(x+t(y-x))\|\le L$, da cui il risultato.

Ora il caso generale può essere ottenuto da un argomento di densità. Sia una funzione convessa$f$soddisfare la tua ipotesi. Per$\epsilon>0$, e definiamo una funzione convessa liscia $f_\epsilon$ per inf-convolution: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Applica il risultato a $f_\epsilon$, quindi passa al limite come $\epsilon\rightarrow0$.

Answer 3

Questa risposta è una piccola modifica della risposta di Denis Serre. Ho aggiunto per comodità del lettore: (1) il risultato è leggermente più generale; (2) la risposta contiene molti più dettagli; (3) Sto usando un'approssimazione di convoluzione per mollificazione invece di inf-convoluzione.

Poiché le funzioni convesse soddisfano $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ è sufficiente provare il seguente risultato più generale.

Teorema. Permettere$f\in C^1(\mathbb{R}^n)$ e lascia $L>0$.Quindi le seguenti condizioni sono equivalenti: \ begin {equation} (1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ langle \ nabla f (x) - \ nabla f (y), xy \ rangle | \ leq L | xy | ^ 2 \ quad \ text {per tutti$x,y\in\mathbb{R}^n$.} \ end {equation} \ begin {equation} (2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ nabla f (x) - \ nabla f (y) | \ leq L | xy | \ quad \ text {per tutti$x,y\in\mathbb{R}^n$.} \ end {equation}

Prova. Mentre l'implicazione da (2) a (1) è ovvia, l'altra non lo è, quindi dimostreremo l'implicazione da (2) a (1) ora. Assumilo prima$f\in C^\infty(\mathbb{R}^n)$. Per$|u|=1$, (1) restituisce, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ passando così al limite come $t\to 0$ dà $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ Da $D^2 f(x)$ è una matrice simmetrica, il teorema spettrale implica che la norma dell'operatore della matrice $D^2f(x)$ soddisfa $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$Questa stima, tuttavia, implica facilmente il risultato \ begin {equation} \ 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} Questo completa la dimostrazione quando$f\in C^\infty$. Supponiamo ora che$f\in C^1$ e lascia $f_\epsilon=f*\varphi_\epsilon$essere un'approssimazione standard per convoluzione. Richiama questo$f_\epsilon\in C^\infty$ e $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. Abbiamo \ begin {equation} \ 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} dove l'ultima disuguaglianza è una conseguenza di (1) e$\int_{\mathbb{R}^n}\varphi_\epsilon=1$. Da$f_\epsilon\in C^\infty$, la prima parte della dimostrazione produce $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ e il risultato segue al passaggio al limite come $\epsilon\to 0$.

Answer 4

Una risposta parziale: se sei disposto a rafforzare la tua ipotesi e supporre $f\in C^2(\mathbb{R}^n)$, allora si. Altrimenti, non sono sicuro.

---

Funzioni che soddisfano - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ sono chiamate "L-semi-concave" e le funzioni che soddisfano - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ sono chiamati "L-smooth".

Se $f\in C^2(\mathbb{R}^n)$ è sia almeno L-semi-convesso (in particolare, convesso) che almeno L-semi-convesso - quindi è effettivamente L-liscio.

Si può provarlo considerando l'Assia $\nabla^2f$ di $f$: la convessità implica che è semidefinito positivo, e la semiconcavità lo implica $\nabla^2f-\frac{1}{2}\mathrm{Id}$è semidefinito negativo. Pertanto, la norma operatore di$\nabla^2f$ deve essere limitato, il che significa che $\nabla f$ è Lipschitz (es $f$ è L-liscia).

Non sono sicuro che sia ancora valido nell'ipotesi più debole $f\in C^1(\mathbb{R}^n)$.