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

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

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

$\operatorname {min} \limits _{x\in \mathbb {R} ^{N}}\sum _{i=1}^{n}f_{i}(x)$

где $f_{i},\ i=1,\dots ,n$ — выпуклые функции, определённые как отображения $f:\mathbb {R} ^{N}\rightarrow \mathbb {R}$, где некоторые из функций недифференцируемы, что исключает обычные техники гладкой оптимизации, такие как метод наискорейшего спуска или метод сопряжённых градиентов и др., вместо них могут быть использованы проксимальные градиентные методы. Эти методы работают путём расщепления, так что функции $f_{1},...,f_{n}$ используются индивидуально, что позволяет разработать более просто реализуемые алгоритмы. Они называются проксимальными (англ. proximal, ближайший), поскольку каждая негладкая функция среди $f_{1},...,f_{n}$ вовлекается в процесс через оператор близости. Итерационный алгоритм мягкой пороговой фильтрации, проекция Ландвебера, проекция градиента, попеременные проекции, метод чередующихся направлений мультипликаторов, метод чередующихся расщеплений Брэгмана являются частными случаями проксимальных алгоритмов. Для рассмотрения проксимальных градиентных методов со стороны статистической теории обучения и приложений к этой теории см. статью Методы проксимального градиента для машинного обучения.

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

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

$\iota _{C}:x\mapsto {\begin{cases}0&&x\in C\\+\infty &&x\notin C\end{cases}}$

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

$\|x\|_{p}=(|x_{1}|^{p}+|x_{2}|^{p}+\cdots +|x_{N}|^{p})^{1/p}$

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

$D_{C}(x)=\min _{y\in C}\|x-y\|_{2}$

Если $C$ замкнуто и выпукло, проекцией $x\in \mathbb {R} ^{N}$ в множество $C$ является единственная точка $P_{C}x\in C$, такая что $D_{C}(x)=\|x-P_{C}x\|_{2}$.

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

$\partial f(x)=\{u\in \mathbb {R} ^{N}\mid \forall y\in \mathbb {R} ^{N},(y-x)^{\mathrm {T} }u+f(x)\leqslant 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}$

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

Определение

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

$\operatorname {argmin} \limits _{y}{\bigg (}f(y)+{\frac {1}{2}}\left\|x-y\right\|_{2}^{2}{\bigg )}$

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

$\operatorname {prox} _{f}(x):\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{N}$

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

${\begin{aligned}\operatorname {prox} _{\iota _{C}}(x)&=\operatorname {argmin} \limits _{y}{\begin{cases}{\frac {1}{2}}\left\|x-y\right\|_{2}^{2}&&y\in C\\+\infty &&y\notin C\end{cases}}\\&=\operatorname {argmin} \limits _{y\in C}{\frac {1}{2}}\left\|x-y\right\|_{2}^{2}\\&=P_{C}(x)\end{aligned}}$

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

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

$p=\operatorname {prox} _{f}(x)\Leftrightarrow x-p\in \partial f(p)\qquad (\forall (x,p)\in \mathbb {R} ^{N}\times \mathbb {R} ^{N})$

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

$p=\operatorname {prox} _{f}(x)\Leftrightarrow x-p=\nabla f(p)\quad (\forall (x,p)\in \mathbb {R} ^{N}\times \mathbb {R} ^{N})$

Примеры

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

• проекция Ландвебера
• Попеременное проецирование
• метод чередующихся направлений мультипликаторов

См. также

• Выпуклое программирование
• Алгоритм Франк — Вульфа
• Проксимальный оператор

Литература

• Daubechies I., Defrise M., De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint // Communications on Pure and Applied Mathematics. — 2004. — Т. 57, вып. 11. — doi:10.1002/cpa.20042. — . — arXiv:math/0307152.
• Rockafellar R. T. Convex analysis. — Princeton: Princeton University Press, 1970.
• Patrick L. Combettes, Jean-Christophe Pesquet. Springer's Fixed-Point Algorithms for Inverse Problems in Science and Engineering. — 2011. — Т. 49. — С. 185–212.

Ссылки

• 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.