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

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

Сравнение итераций метода проецируемого градиента (красный) и метода Франка-Вульфа (зеленый).

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

$\operatorname {min} \limits _{x\in \mathbb {R} ^{N}}\sum _{i=1}^{n}f_{i}(x)$

где $f_{i}:\mathbb {R} ^{N}\rightarrow \mathbb {R} ,\ i=1,\dots ,n$ возможно, являются недифференцируемыми выпуклыми функциями . Отсутствие дифференцируемости исключает традиционные методы плавной оптимизации, такие как метод наискорейшего спуска и метод сопряженных градиентов , но вместо них можно использовать методы проксимального градиента.

Методы проксимального градиента начинаются с шага разделения, на котором функции $f_{1},...,f_{n}$ используются индивидуально, чтобы получить легко реализуемый алгоритм. Они называются проксимальными , потому что каждая недифференцируемая функция среди $f_{1},...,f_{n}$ задействован через своего оператора близости . Итеративный алгоритм определения порога усадки, ^{[ 1 ]} проекция Ландвебера , проецируемый градиент, чередующиеся проекции , метод чередующихся множителей , чередующиеся расщепление Брегмана являются частными случаями проксимальных алгоритмов. ^{[ 2 ]}

Для теории методов проксимального градиента с точки зрения и с приложениями к статистической теории обучения см. методы проксимального градиента для обучения .

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

Одним из широко используемых алгоритмов выпуклой оптимизации являются проекции на выпуклые множества (POCS). Этот алгоритм используется для восстановления/синтеза сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Позволять $f_{i}$ – индикаторная функция непустого замкнутого выпуклого множества $C_{i}$ моделирование ограничения. Это сводится к задаче выпуклой осуществимости, которая требует от нас найти решение, такое, что оно лежит в пересечении всех выпуклых множеств. $C_{i}$ . В методе POCS каждый набор $C_{i}$ включается его оператором проекции $P_{C_{i}}$ . Итак, на каждой итерации $x$ обновляется как

x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}

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

Примеры

Особыми случаями методов проксимального градиента являются

См. также

Примечания

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

Ссылки

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

Внешние ссылки

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

[1] Добеши, я; Дефризе, М; Де Моль, К. (2004). «Итеративный алгоритм определения порога для линейных обратных задач с ограничением разреженности». Сообщения по чистой и прикладной математике . 57 (11): 1413–1457. arXiv : math/0307152 . Бибкод : 2003math......7152D . дои : 10.1002/cpa.20042 .

[2] Подробности проксимальных методов обсуждаются в Комбеттс, Патрик Л.; Песке, Жан-Кристоф (2009). «Методы проксимального разделения при обработке сигналов». arXiv : 0912.3522 [ math.OC ].

[ 1 ]

[ 2 ]