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

Метод проксимального градиента^[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.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (20 ноября 2020) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (20 ноября 2020) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.