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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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).\}}$

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

${\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}$

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

Оператор близости^[англ.] выпуклой функции ${\displaystyle f}$ в точке ${\displaystyle x}$ определяется как единственное решение

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle 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. — Bibcode: 2003math......7152D. — 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.