Выпуклость и липшицевость.

Question

Это, наверное, простой вопрос, но почему-то я застрял.

Вопрос Верно ли следующее утверждение? Если да, то как это доказать?

Предположим, что $f\in C^1(\mathbb{R}^n)$ выпуклый и $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ для некоторых $L>0$ и все $x,y\in\mathbb{R}^n$. Следует ли из этого$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ для всех $x,y\in\mathbb{R}^n$?

Answer 1

Это стандартный результат выпуклой оптимизации. Например, теорема 2.1.5 из «Вводных лекций по выпуклой оптимизации» Нестерова утверждает, что следующие утверждения эквивалентны:

• $f$ является $C^1$, выпуклый и градиент $\nabla f$ является $L$-Липшиц
• для всех $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
• для всех $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
• для всех $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(В случае, если вам интересно: Доказательство есть непосредственно для $C^1$ функции и никакие вторые производные не используются на промежуточных этапах.)

Answer 2

да

Рассмотрим сначала случай, когда $f\in{\cal C}^2$. потом$$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ Далее следует $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ Теперь предположение говорит вам, что $\|{\rm D}^2f(x+t(y-x))\|\le L$, откуда результат.

Теперь общий случай можно получить с помощью аргумента плотности. Пусть выпуклая функция$f$удовлетворите ваше предположение. Для$\epsilon>0$, и определим гладкую выпуклую функцию $f_\epsilon$ по инф-свертке: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Примените результат к $f_\epsilon$, то переходят к пределу как $\epsilon\rightarrow0$.

Answer 3

Этот ответ представляет собой небольшую модификацию ответа Дени Серра. Для удобства читателя я добавил: (1) результат немного более общий; (2) ответ содержит гораздо больше деталей; (3) Я использую свертку путем приближения смягчения вместо инф-свертки.

Поскольку выпуклые функции удовлетворяют $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ достаточно доказать следующий более общий результат.

Теорема. Позволять$f\in C^1(\mathbb{R}^n)$ и разреши $L>0$. Тогда следующие условия эквивалентны: \ begin { Equation } (1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ langle \ nabla f (x) - \ nabla f (y), xy \ rangle | \ leq L | xy | ^ 2 \ quad \ text {для всех$x,y\in\mathbb{R}^n$.} \ конец {уравнение} \ начало {уравнение} (2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ nabla f (x) - \ nabla f (y) | \ leq L | xy | \ quad \ text {для всех$x,y\in\mathbb{R}^n$.} \ end {уравнение}

Доказательство. Хотя импликация (2) в (1) очевидна, другая - нет, поэтому сейчас мы докажем импликацию из (2) в (1). Предположим сначала, что$f\in C^\infty(\mathbb{R}^n)$. Для$|u|=1$, (1) дает, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ так переходя к пределу, как $t\to 0$ дает $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ С $D^2 f(x)$ является симметричной матрицей, из спектральной теоремы следует, что операторная норма матрицы $D^2f(x)$ удовлетворяет $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$Однако из этой оценки легко следует результат \ begin {equal} \ 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 | ху |. \ end {split} \ end {формула} Это завершает доказательство, когда$f\in C^\infty$. Предположим теперь, что$f\in C^1$ и разреши $f_\epsilon=f*\varphi_\epsilon$стандартное приближение сверткой. Напомним, что$f_\epsilon\in C^\infty$ а также $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. У нас есть \ begin {уравнение} \ 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 {equal} где последнее неравенство является следствием (1) и$\int_{\mathbb{R}^n}\varphi_\epsilon=1$. С$f_\epsilon\in C^\infty$, первая часть доказательства дает $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ и результат следует при предельном переходе как $\epsilon\to 0$.

Answer 4

Частичный ответ: если вы хотите укрепить свое предположение и предположить, $f\in C^2(\mathbb{R}^n)$, тогда да. В противном случае я не уверен.

---

Функции, удовлетворяющие - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ называются L-полувогнутыми, а функции, удовлетворяющие - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ называются «L-гладкими».

Если $f\in C^2(\mathbb{R}^n)$ является как минимум L-полувыпуклым (в частности, выпуклым) и как минимум L-полувогнутым, то он действительно L-гладкий.

Это можно доказать, рассматривая гессенский $\nabla^2f$ из $f$: из выпуклости следует, что она положительно полуопределенная, а из полувогнутости следует, что $\nabla^2f-\frac{1}{2}\mathrm{Id}$отрицательно полуопределено. Следовательно, оператор-норма$\nabla^2f$ должен быть ограничен, что означает, что $\nabla f$ является липшицевым (т.е. $f$ L-гладко).

Я не уверен, верно ли это при более слабом предположении $f\in C^1(\mathbb{R}^n)$.