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

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

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

${\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}}$ залучається до процесу через ^[en]. Ітераційний алгоритм м'якої порогової фільтрації, ^[en], проєкція градієнта, , ^[en] , метод почергових розщеплень ^[en] є окремими випадками проксимальних алгоритмів.

Позначення та термінологія

Нехай ${\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).\}}$

Проектування в опуклі множини

Одним із широко використовуваних опуклих алгоритмів оптимізації є ^[en]. Цей алгоритм використовується для виявлення/синтезування сигналу, що задовольняє одночасно кілька опуклих обмежень. Нехай ${\displaystyle f_{i}}$ — індикаторна функція на непорожній замкнутій опуклій множині ${\displaystyle C_{i}}$, що моделює обмеження. Це зводить задачу до задачі опуклої здійсненності (досяжності), в якій потрібно знайти розв'язок, що міститься в перетині всіх опуклих множин ${\displaystyle C_{i}}$. У методі проєктування в опуклі множини кожна множина ${\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}}$

Проте поза такими задачами проєктори не підходять і потрібні оператори загальнішого вигляду. Серед різних узагальнень поняття опуклого проєктора проксимальні оператори найкраще підходять для таких цілей.

Визначення

^[en] опуклої функції ${\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})}$

Приклади

Окремими випадками проксимальних градієнтних методів є:

• ^[en],
• ,
• ^[en].

Див. також

• Опукла оптимізація
• Алгоритм Франк — Вульфа
• ^[en]

Примітки

1. англ. Proximal = найближчий
2. Daubechies, Defrise, De Mol, 2004, с. 1413–1457.
3. Patrick L. Combettes, Jean-Christophe Pesquet (2009). Proximal Splitting Methods in Signal Processing. arXiv:0912.3522 [math.OC]. — докладно обговорюються проксимальні методи

Література

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