Проксимальные градиентные методы - это обобщенная форма проекции, используемая для решения недифференцируемых задач выпуклой оптимизации .
Многие интересные задачи можно сформулировать как задачи выпуклой оптимизации вида
где являются выпуклые функции , определенные изгде некоторые функции недифференцируемы. Это исключает обычные гладкие методы оптимизации , такие как метод спуска наискорейшего , сопряженный градиентный метод и т.д. проксимальные градиентные методы могут быть использовано вместо. Эти методы основываются на разделении, так как функциииспользуются индивидуально, чтобы получить легко реализуемый алгоритм. Они называются проксимальными, потому что каждая негладкая функция средиучаствует через своего оператора близости. Алгоритм пороговой обработки итеративного сжатия, [1] прогноз Ландвебера , прогнозируемый градиент, чередующиеся проекции , метод чередующихся направлений множителей , чередующееся разбиение Брегмана - особые примеры проксимальных алгоритмов. [2] Для теории методов проксимального градиента с точки зрения и с приложениями к теории статистического обучения , см. Методы проксимального градиента для обучения .
Обозначения и терминология
Позволять , то -мерное евклидово пространство , - область определения функции. Предполагать непустое выпуклое подмножество . Тогда индикаторная функция определяется как
- -норма определяется как ( )
Расстояние от к определяется как
Если замкнуто и выпукло, проекция на это единственная точка такой, что .
Субдифференциал из в дан кем-то
Проекция на выпуклые множества (POCS)
Один из широко используемых алгоритмов выпуклой оптимизации - это проекции на выпуклые множества (POCS). Этот алгоритм используется для восстановления / синтеза сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Позволять - индикаторная функция непустого замкнутого выпуклого множества моделирование ограничения. Это сводится к проблеме выпуклой выполнимости, которая требует от нас найти решение, лежащее в пересечении всех выпуклых множеств.. В методе POCS каждый наборвключается оператором проекции . Итак, на каждой итерации обновляется как
Однако, помимо таких проблем, операторы проекции не подходят, и для их решения требуются более общие операторы. Среди различных существующих обобщений понятия оператора выпуклого проектирования операторы близости лучше всего подходят для других целей.
Определение
Оператор близости выпуклой функции в определяется как единственное решение
и обозначается .
Обратите внимание, что в конкретном случае, когда индикаторная функция некоторого выпуклого множества
показывая, что оператор близости действительно является обобщением оператора проекции.
Оператор близости характеризуется включением
Если дифференцируемо, то приведенное выше уравнение сводится к
Примеры
Особые примеры методов проксимального градиента:
Смотрите также
Заметки
- ^ Добеши, я; Дефриз, М; Де Мол, К. (2004). «Итерационный алгоритм определения порога для линейных обратных задач с ограничением разреженности». Сообщения по чистой и прикладной математике . 57 (11): 1413–1457. arXiv : math / 0307152 . Bibcode : 2003math ...... 7152D . DOI : 10.1002 / cpa.20042 .
- ^ Подробности проксимальных методов обсуждаются в Комбеты, Патрик Л .; Песке, Жан-Кристоф (2009). «Методы проксимального расщепления в обработке сигналов». arXiv : 0912.3522 [ math.OC ].
Рекомендации
- Рокафеллар, RT (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета.
- Комбеты, Патрик Л .; Песке, Жан-Кристоф (2011). Алгоритмы Спрингера с фиксированной точкой для обратных задач в науке и технике . 49 . С. 185–212.
Внешние ссылки
- Стивен Бойд и Ливен Ванденберге Книга, Выпуклая оптимизация
- EE364a: Convex Optimization I и EE364b: Convex Optimization II , домашние страницы курсов Стэнфорда
- EE227A: Ливен Ванденберг записывает лекцию 18
- ProximalOperators.jl : пакет Julia , реализующий проксимальные операторы.
- ProximalAlgorithms.jl : пакет Julia , реализующий алгоритмы на основе проксимального оператора, включая метод проксимального градиента.
- Репозиторий Proximity Operator : набор операторов близости, реализованных в Matlab и Python .