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

Метод проксимального градієнта — узагальнення проєктування, що використовується для розв'язання недиференційовних задач опуклого програмування.

Багато цікавих задач можна сформулювати як задачі опуклого програмування

$\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}$. У методі проєктування в опуклі множини кожна множина $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. — arXiv:math/0307152. — Bibcode:2003math......7152D. — DOI:10.1002/cpa.20042.
• 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.