Липшицевость

Липшицевая функция

Пусть есть два метрических пространства AA с метрикой dAd_A и BB с метрикой dBd_B.

Функция f ⁣:A→Bf \colon A \to B называется LL-липшицевой, если для любых x,y∈Ax, y \in A

dB(f(x),f(y))⩽L⋅dA(x,y)d_B(f(x), f(y)) \le L \cdot d_A(x, y)

Более естественное определение для отображения f ⁣:A→Bf \colon A \to B для нормированных векторных пространств AA и BB

∥f(x)−f(y)∥⩽L⋅∥x−y∥\|f(x) - f(y)\| \le L \cdot \|x - y\|

Квадратичное ограничение сверху для липшицевой гладкости

Пусть у функции f ⁣:Rn→Rf \colon \RR^n \to \RR градиент ∇f\nabla f является LL-липшицевым:

∥∇f(y)−∇f(x)∥⩽L⋅∥y−x∥для всех x,y∈Rn\|\nabla f (y) - \nabla f (x) \| \le L \cdot \|y-x\| \quad \text{для всех}~ x,y \in \RR^n

Тогда для всех x,y∈Rnx, y \in \RR^n верно неравенство

f(y)⩽f(x)+∇f(x)T⋅(y−x)+L2⋅∥y−x∥2f(y) \le f(x) + \nabla f (x) ^\T \cdot (y-x) + \frac{L}{2} \cdot \|y-x\|^2

Выберем x,y∈Rnx, y \in \RR^n — две произвольные точки.

Посмотри на функцию φ(t)=f(x+t⋅(y−x))\varphi(t) = f \big( x + t \cdot (y-x) \big) при 0⩽t⩽10 \le t \le 1. Можем записать f(y)−f(x)f(y) - f(x) через эту функцию

f(y)−f(x)=∫01φ′(t)dt=∫01∇f(x−t⋅(y−x))T⋅(y−x)dtf(y) - f(x) = \int\limits_0^1 \varphi'(t) dt = \int\limits_0^1 \nabla f \big( x - t \cdot (y-x) \big) ^\T \cdot (y-x) dt

Добавляя и вычитая ∇f(x)T⋅(y−x)\nabla f (x) ^\T \cdot (y-x), получаем формулу

f(y)−f(x)=∇f(x)T⋅(y−x)+∫01(∇f(x−t⋅(y−x))−∇f(x))T⋅(y−x)dtf(y) - f(x) = \nabla f (x) ^\T \cdot (y-x) + \int\limits_0^1 \Big( \nabla f \big( x - t \cdot (y-x) \big) - \nabla f (x) \Big) ^\T \cdot (y-x) dt

Применяя неравенство Коши-Шварца и липшицевость градиента, получаем

(∇f(x−t⋅(y−x))−∇f(x))T⋅(y−x)⩽∥∇f(x−t⋅(y−x))−∇f(x)∥⋅∥y−x∥⩽⩽L⋅∥x−t⋅(y−x)−x∥⋅∥y−x∥==L⋅t⋅∥y−x∥2\begin{align*} \Big(\nabla f \big( x - t \cdot (y-x) \big) - \nabla f (x) \Big) ^\T \cdot (y-x) &\le \Big\| \nabla f \big( x - t \cdot (y-x) \big) - \nabla f (x) \Big\| \cdot \|y-x\| \le \\ &\le L \cdot \| x - t \cdot (y-x) - x \| \cdot \|y-x\| = \\ &= L \cdot t \cdot \|y-x\|^2 \end{align*}

Применяем полученное неравенство для оценки интеграла

f(y)−f(x)⩽∇f(x)T⋅(y−x)+∫01L⋅t⋅∥y−x∥2dt=∇f(x)T⋅(y−x)+L2⋅∥y−x∥2f(y) - f(x) \le \nabla f (x) ^\T \cdot (y-x) + \int\limits_0^1 L \cdot t \cdot \|y-x\|^2 dt = \nabla f (x) ^\T \cdot (y-x) + \frac{L}{2} \cdot \|y-x\|^2

Получили требуемый результат

f(y)⩽f(x)+∇f(x)T⋅(y−x)+L2⋅∥y−x∥2f(y) \le f(x) + \nabla f (x) ^\T \cdot (y-x) + \frac{L}{2} \cdot \|y-x\|^2