Convexidade e continuidade de Lipschitz

Question

Provavelmente é uma pergunta fácil, mas de alguma forma estou preso.

Pergunta A seguinte afirmação é verdadeira? Se sim, como provar?

Suponha que $f\in C^1(\mathbb{R}^n)$ é convexo e $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ para alguns $L>0$ e tudo $x,y\in\mathbb{R}^n$. Isso segue isso$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ para todos $x,y\in\mathbb{R}^n$?

Answer 1

Esse é um resultado padrão na otimização convexa. Por exemplo, o Teorema 2.1.5 nas "Palestras Introdutórias sobre Otimização Convexa" de Nesterov afirma que o seguinte é equivalente:

• $f$ é $C^1$, convexo e o gradiente $\nabla f$ é $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$

(No caso de você estar interessado: A prova lá é diretamente para $C^1$ funções e nenhuma segunda derivada são usadas nas etapas intermediárias.)

Answer 2

sim

Considere primeiro o caso onde $f\in{\cal C}^2$. Então$$\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.$$ Agora, a suposição te diz que $\|{\rm D}^2f(x+t(y-x))\|\le L$, de onde vem o resultado.

Agora, o caso geral pode ser obtido por um argumento de densidade. Deixe uma função convexa$f$satisfazer sua suposição. Para$\epsilon>0$, vamos definir uma função convexa suave $f_\epsilon$ por inf-convolução: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Aplique o resultado a $f_\epsilon$, então passe ao limite como $\epsilon\rightarrow0$.

Answer 3

Esta resposta é uma pequena modificação da resposta de Denis Serre. Acrescentei para conveniência do leitor: (1) o resultado é um pouco mais geral; (2) a resposta contém muito mais detalhes; (3) Estou usando uma aproximação de convolução por molificação em vez de inf-convolução.

Uma vez que as funções convexas satisfazem $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ é suficiente provar o seguinte resultado mais geral.

Teorema. Deixar$f\in C^1(\mathbb{R}^n)$ e deixar $L>0$.Assim, as seguintes condições são equivalentes: \ begin {equation} (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 {equação} \ begin {equação} (2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ nabla f (x) - \ nabla f (y) | \ leq L | xy | \ quad \ text {para todos$x,y\in\mathbb{R}^n$.} \ end {equation}

Prova. Embora a implicação de (2) a (1) seja óbvia, a outra não é, vamos provar a implicação de (2) a (1) agora. Assuma primeiro que$f\in C^\infty(\mathbb{R}^n)$. Para$|u|=1$, (1) produz, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ passando assim ao limite como $t\to 0$ dá $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ Desde a $D^2 f(x)$ é uma matriz simétrica, o teorema espectral implica que a norma do operador da matriz $D^2f(x)$ satisfaz $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$Esta estimativa, entretanto, implica facilmente no resultado \ 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} Isto completa a prova quando$f\in C^\infty$. Presuma agora que$f\in C^1$ e deixar $f_\epsilon=f*\varphi_\epsilon$ser uma aproximação padrão por convolução. Lembre-se disso$f_\epsilon\in C^\infty$ e $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. Temos \ 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 \ Grande \ rangle \ Grande | \\ & \ 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} onde a última desigualdade é uma consequência de (1) e$\int_{\mathbb{R}^n}\varphi_\epsilon=1$. Desde a$f_\epsilon\in C^\infty$, a primeira parte da prova resulta $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ e o resultado segue passando ao limite de $\epsilon\to 0$.

Answer 4

Uma resposta parcial: se você está disposto a fortalecer sua suposição e supor $f\in C^2(\mathbb{R}^n)$, então sim. Caso contrário, não tenho certeza.

---

Funções que satisfazem - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ são chamados de "L-semi-côncavo", e funções que satisfazem - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ são chamados de "L-smooth".

Se $f\in C^2(\mathbb{R}^n)$ é pelo menos L-semi-convexo (em particular, convexo) e pelo menos L-semi-convave - então é de fato L-liso.

Pode-se provar isso considerando o Hessian $\nabla^2f$ de $f$: a convexidade implica que é semidefinida positiva, e a semiconcavidade implica que $\nabla^2f-\frac{1}{2}\mathrm{Id}$é semidefinido negativo. Portanto, a norma do operador de$\nabla^2f$ deve ser limitado, o que significa que $\nabla f$ é Lipschitz (ie $f$ é L-liso).

Não tenho certeza se ainda se mantém sob a suposição mais fraca $f\in C^1(\mathbb{R}^n)$.