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

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

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

$\underset{x\in {ℝ}^N}{\min }\sum _{i=1}^n{f}_i(x)$

де $f_i,i=1,\dots ,n$ — опуклі функції, визначені як відображення $f:{ℝ}^N\to ℝ$, де деякі з функцій недиференційовні, що виключає звичайні техніки гладкої оптимізації, такі як метод найшвидшого спуску або метод спряжених градієнтів тощо, замість них можна використати проксимальні градієнтні методи. Ці методи ґрунтуються на розщепленні, тому функції $f_1,...,f_n$ використовуються індивідуально, що дозволяє розробити простіші для реалізації алгоритми. Їх називають проксимальними (Шаблон:Lang-en — найближчий), оскільки кожна не гладка функція серед $f_1,...,f_n$ залучається до процесу через Шаблон:Нп. Ітераційний алгоритм м'якої порогової фільтраціїШаблон:Sfn, Шаблон:Нп, проєкція градієнта, поперемінні проєкції, Шаблон:Не перекладено , метод почергових розщеплень Шаблон:Нп є окремими випадками проксимальних алгоритмівШаблон:R.

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

Нехай ${ℝ}^N$, $N$-вимірний евклідів простір, є областю визначення функції $f:{ℝ}^N\to (-\mathrm{\infty },+\mathrm{\infty }]$. Припустимо, що $C$ є непорожньою опуклою підмножиною множини ${ℝ}^N$. Тоді індикаторна функція множини $C$ визначається як

${\iota }_C:x\mapsto \{\begin{array}{ccc}0& & x\in C\\ +\mathrm{\infty }& & x\notin C\end{array}$

$p$-норма визначається як $(\Vert \cdot {\Vert }_p)$

$\Vert x{\Vert }_p=(|x_1{|}^p+|x_2{|}^p+\cdots +|x_N{|}^p{)}^{1/p}$

Відстань від $x\in {ℝ}^N$ до $C$ визначається як

$D_C(x)=\underset{y\in C}{\min }\Vert x-y{\Vert }_2$

Якщо $C$ замкнута та опукла, проекцією $x\in {ℝ}^N$ у множну $C$ є єдина точка $P_{C}x\in C$, така що $D_C(x)=\Vert x-P_{C}x{\Vert }_2$.

Субдиференціал функції $f$ у точці $x$ задається виразом

$\partial f(x)=\{u\in {ℝ}^N\mid \mathrm{\forall }y\in {ℝ}^N,(y-x{)}^{\mathrm{T}}u+f(x)⩽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$ визначається як єдиний розв'язок

$\underset{y}{\mathrm{argmin}}(f(y)+\frac{1}{2}{\Vert x-y\Vert }_2^2)$

і позначається як ${\mathrm{prox}}_f(x)$.

${\mathrm{prox}}_f(x):{ℝ}^N\to {ℝ}^N$

Зауважимо, що у випадку, коли $f$ є індикаторною функцією ${\iota }_C$ деякої опуклої множини $C$

$\begin{array}{cc}{\mathrm{prox}}_{{\iota }_C}(x)& =\underset{y}{\mathrm{argmin}}\{\begin{array}{ccc}\frac{1}{2}{\Vert x-y\Vert }_2^2& & y\in C\\ +\mathrm{\infty }& & y\notin C\end{array}\\ & =\underset{y\in C}{\mathrm{argmin}}\frac{1}{2}{\Vert x-y\Vert }_2^2\\ & =P_C(x)\end{array}$

що показує, що проксимальний оператор справді є узагальненням проєктора.

Проксимальний оператор функції $f$ описується включенням

$p={\mathrm{prox}}_f(x)\iff x-p\in \partial f(p)(\mathrm{\forall }(x,p)\in {ℝ}^N\times {ℝ}^N)$

Якщо $f$ диференційовна, то наведене рівняння вище зводиться до

$p={\mathrm{prox}}_f(x)\iff x-p=\mathrm{\nabla }f(p)(\mathrm{\forall }(x,p)\in {ℝ}^N\times {ℝ}^N)$

Приклади

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

• Шаблон:Нп,
• проєктування в опуклі множини,
• Шаблон:Не перекладено.

Див. також

• Опукла оптимізація
• Алгоритм Франк — Вульфа
• Шаблон:Не перекладено

Література

• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга

Посилання

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