Метод проксимального градиента

Метод проксимального градиента — это обобщение проецирования, используемое для решения недифференцируемых задач выпуклого программирования.

Много интересных задач можно сформулировать как задачи выпуклого программирования вида

$\underset{x\in {ℝ}^N}{\min }\sum _{i=1}^n{f}_i(x)$

где $f_i,i=1,\dots ,n$ — выпуклые функции, определённые как отображения $f:{ℝ}^N\to ℝ$, где некоторые из функций недифференцируемы, что исключает обычные техники гладкой оптимизации, такие как метод наискорейшего спуска или метод сопряжённых градиентов и др., вместо них могут быть использованы проксимальные градиентные методы. Эти методы работают путём расщепления, так что функции $f_1,\mathrm{...},f_n$ используются индивидуально, что позволяет разработать более просто реализуемые алгоритмы. Они называются проксимальными (Шаблон:Lang-en, ближайший), поскольку каждая негладкая функция среди $f_1,\mathrm{...},f_n$ вовлекается в процесс через оператор близости. Итерационный алгоритм мягкой пороговой фильтрацииШаблон:Sfn, проекция Ландвебера, проекция градиента, попеременные проекции, Шаблон:Не переведено 5, метод чередующихся расщеплений Брэгмана являются частными случаями проксимальных алгоритмовШаблон:R. Для рассмотрения проксимальных градиентных методов со стороны статистической теории обучения и приложений к этой теории см. статью Шаблон:Не переведено 5.

Обозначения и терминология

Пусть ${ℝ}^N$, $N$-мерное евклидово пространство, будет областью определения функции $f:{ℝ}^N\to (-\mathrm{\infty },+\mathrm{\infty }]$. Предположим, что $C$ является непустым выпуклым подмножеством множества ${ℝ}^N$. Тогда индикаторная функция множества $C$ определяется как

${\iota }_C:x\mapsto \{\begin{array}{ccc}0& & x\in C\\ +\mathrm{\infty }& & x\notin C\end{array}$

$p$-норма определяется как $(\Vert \cdot {\Vert }_p)$

$\Vert x{\Vert }_p=(|x_1{|}^p+|x_2{|}^p+\cdots +|x_N{|}^p{)}^{1/p}$

Расстояние от $x\in {ℝ}^N$ до $C$ определяется как

$D_C(x)=\underset{y\in C}{min}\Vert x-y{\Vert }_2$

Если $C$ замкнуто и выпукло, проекцией $x\in {ℝ}^N$ в множество $C$ является единственная точка $P_{C}x\in C$, такая что $D_C(x)=\Vert x-P_{C}x{\Vert }_2$.

Субдифференциал функции $f$ в точке $x$ задаётся выражением

$\partial f(x)=\{u\in {ℝ}^N\mid \mathrm{\forall }y\in {ℝ}^N,(y-x{)}^{\mathrm{T}}u+f(x)⩽f(y).\}$

Проецирование в выпуклые множества

Одним из широко используемых выпуклых алгоритмов оптимизации является проецирование в выпуклые множества. Этот алгоритм используется для обнаружения/синтезирования сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Пусть $f_i$ будет индикаторной функцией на непустом замкнутом выпуклом множестве $C_i$, моделирующей ограничение. Это сводит задачу к задаче выпуклой осуществимости (достижимости), в которой нужно найти решение, содержащееся в пересечении всех выпуклых множеств $C_i$. В методe проецирования в выпуклые множества каждое множество $C_i$ ассоциируется с его проектором $P_{C_i}$. Таким образом, на каждой итерации $x$ пересчитывается по формуле

$x_{k+1}=P_{C_1}{P}_{C_2}\cdots P_{C_n}{x}_k$

Однако за пределами таких задач проекторы не подходят и требуются операторы более общего вида. Среди различных существующих обобщений понятия выпуклого проектора операторы близости лучше всего подходят для таких целей.

Определение

Шаблон:Не переведено 5 выпуклой функции $f$ в точке $x$ определяется как единственное решение

$\underset{y}{\mathrm{argmin}}(f(y)+\frac{1}{2}{\Vert x-y\Vert }_2^2)$

и обозначается как ${\mathrm{prox}}_f(x)$.

${\mathrm{prox}}_f(x):{ℝ}^N\to {ℝ}^N$

Заметим, что в случае, когда $f$ является индикаторной функцией ${\iota }_C$ некоторого выпуклого множества $C$

$\begin{array}{cc}{\mathrm{prox}}_{{\iota }_C}(x)& =\underset{y}{\mathrm{argmin}}\{\begin{array}{ccc}\frac{1}{2}{\Vert x-y\Vert }_2^2& & y\in C\\ +\mathrm{\infty }& & y\notin C\end{array}\\ & =\underset{y\in C}{\mathrm{argmin}}\frac{1}{2}{\Vert x-y\Vert }_2^2\\ & =P_C(x)\end{array}$

что показывает, что оператор близости действительно является обобщением проектора.

Оператор близости функции $f$ описывается включением

$p={\mathrm{prox}}_f(x)\iff x-p\in \partial f(p)(\mathrm{\forall }(x,p)\in {ℝ}^N\times {ℝ}^N)$

Если $f$ дифференцируема, то уравнение выше сводится к

$p={\mathrm{prox}}_f(x)\iff x-p=\mathrm{\nabla }f(p)(\mathrm{\forall }(x,p)\in {ℝ}^N\times {ℝ}^N)$

Примеры

Частными случаями проксимальных градиентных методов являются

• проекция Ландвебера
• Попеременное проецирование
• Шаблон:Не переведено 5

См. также

• Выпуклое программирование
• Алгоритм Франк — Вульфа
• Шаблон:Не переведено 5

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Stephen Boyd, Lieven Vandenberghe, Convex optimization
• EE364a: Convex Optimization I и EE364b: Convex Optimization II, Страницы стэнфордского курса
• EE227A: Lieven Vandenberghe Notes Лекция 18
• ProximalOperators.jl: Пакет на языке Julia, реализующий проксимальные операторы.
• ProximalAlgorithms.jl: Пакет на языке Julia, реализующий алгоритмы, основанные на операторах близости, включая проксимальный градиентный метод.
• Proximity Operator repository: набор операторов близости, реализованных в Matlab и на языке Python.