Проксимальный градиентный метод - Proximal gradient method

Проксимальные градиентные методы являются обобщенной формой проекции, используемой для решения недифференцируемых выпуклая оптимизация проблемы.

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

${\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}}$ используются индивидуально, чтобы легко получить осуществимый алгоритма и называются проксимальный потому что каждый не гладкая функция среди ${\displaystyle f_{1},...,f_{n}}$ задействован через свой оператор близости. Алгоритм пороговой обработки итеративной усадки,^[1] по прогнозам Landweber, прогнозируемый градиент, чередующиеся проекции, метод переменного направления множителей, альтернативное разделение Брегман являются частными экземплярами проксимальных алгоритмов.^[2] За теорию методов проксимального градиента с точки зрения и с приложениями к теория статистического обучения, видеть методы проксимального градиента для обучения.

Обозначения и терминология

Позволять ${\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&{\text{if }}x\in C\\+\infty &{\text{if }}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)\leq f(y).\}}$

Проекция на выпуклые множества (POCS)

Одним из широко используемых алгоритмов выпуклой оптимизации является проекции на выпуклые множества (POCS). Этот алгоритм используется для восстановления / синтеза сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Позволять ${\displaystyle f_{i}}$ - индикаторная функция непустого замкнутого выпуклого множества ${\displaystyle C_{i}}$ моделирование ограничения. Это сводится к проблеме выпуклой выполнимости, которая требует от нас найти решение, лежащее в пересечении всех выпуклых множеств ${\displaystyle C_{i}}$. В методе POCS каждый набор ${\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}&{\text{if }}y\in C\\+\infty &{\text{if }}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})}$

Примеры

Особые примеры методов проксимального градиента:

• Прогнозируемый Landweber
• Альтернативная проекция
• Метод переменного направления умножителей

Смотрите также

• Альтернативная проекция
• Выпуклая оптимизация
• Алгоритм Франка – Вульфа
• Проксимальный оператор
• Методы проксимального градиента для обучения

Примечания

1. Добеши, I; Дефрайз, М; Де Мол, C (2004). «Итерационный алгоритм пороговой обработки для линейных обратных задач с ограничением разреженности». Сообщения по чистой и прикладной математике. 57 (11): 1413–1457. arXiv:математика / 0307152. Bibcode:2003математика ...... 7152D. Дои:10.1002 / cpa.20042.
2. Детали проксимальных методов обсуждаются в Комбеты, Патрик Л .; Песке, Жан-Кристоф (2009). «Методы проксимального расщепления в обработке сигналов». arXiv:0912.3522 [math.OC ].

Рекомендации

• Рокафеллар, Р. Т. (1970). Выпуклый анализ. Принстон: Издательство Принстонского университета.
• Комбеты, Патрик Л .; Песке, Жан-Кристоф (2011). Алгоритмы Спрингера с фиксированной точкой для обратных задач в науке и технике. 49. С. 185–212.

внешняя ссылка

• Книга Стивена Бойда и Ливена Ванденберга, Выпуклая оптимизация
• EE364a: выпуклая оптимизация I и EE364b: выпуклая оптимизация II, Домашние страницы курсов Стэнфорда
• EE227A: Заметки Ливена Ванденберга Лекция 18
• ProximalOperators.jl: а Юля пакет, реализующий проксимальные операторы.
• ProximalAlgorithms.jl: а Юля пакет, реализующий алгоритмы на основе проксимального оператора, в том числе метод проксимального градиента.
• Репозиторий Proximity Operator: набор операторов близости, реализованных в Matlab и Python.