Конверт Моро

Конверт Моро (или регуляризация Моро-Йосиды) $M_{f}$ собственной полунепрерывной снизу выпуклой функции $f$ представляет собой сглаженную версию $f$ . Его предложил Жан-Жак Моро в 1965 году. ^[1]

Огибающая Моро имеет важные приложения в математической оптимизации : минимизация более чем $M_{f}$ и минимизация более $f$ являются эквивалентными задачами в том смысле, что множества минимизаторов $f$ и $M_{f}$ одинаковы. Однако алгоритмы оптимизации первого порядка могут быть напрямую применены к $M_{f}$ , с $f$ может быть недифференцируемым, хотя $M_{f}$ всегда непрерывно дифференцируемо. Действительно, многие методы проксимального градиента можно интерпретировать как метод градиентного спуска по $M_{f}$ .

Определение

Огибающая Моро собственной полунепрерывной снизу выпуклой функции $f$ из гильбертова пространства ${\mathcal {X}}$ к $(-\infty ,+\infty ]$ определяется как ^[2]

$M_{\lambda f}(v)=\inf _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2\lambda }}\|x-v\|_{2}^{2}\right).$

Учитывая параметр $\lambda \in \mathbb {R}$ , конверт Моро $\lambda f$ также называется оболочкой Моро $f$ с параметром $\lambda$ . ^[2]

Характеристики

Конверт Моро можно также рассматривать как незначительную свертку между $f$ и $(1/2)\|\cdot \|_{2}^{2}$ .
Проксимальный оператор функции связан с градиентом огибающей Моро следующим тождеством:

$\nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))$ . Определив последовательность $x_{k+1}=\mathrm {prox} _{\lambda f}(x_{k})$ и используя приведенное выше тождество, мы можем интерпретировать проксимальный оператор как алгоритм градиентного спуска по огибающей Моро.

Используя теорему двойственности Фенхеля , можно вывести следующую двойственную формулировку оболочки Моро:

$M_{\lambda f}(v)=\max _{p\in {\mathcal {X}}}\left(\langle p,v\rangle -{\frac {\lambda }{2}}\|p\|^{2}-f^{*}(p)\right),$ где $f^{*}$ обозначает сопряжение выпуклое $f$ . Поскольку субдифференциал собственной выпуклой полунепрерывной снизу функции в гильбертовом пространстве является обратным субдифференциалу ее выпукло-сопряженной функции, мы можем заключить, что если $p_{0}\in {\mathcal {X}}$ является максимизатором приведенного выше выражения, тогда $x_{0}:=v-\lambda p_{0}$ является минимизатором в основной формулировке и наоборот.

По формуле Хопфа-Лакса огибающая Моро является вязкостным решением уравнения Гамильтона-Якоби . ^[3] Стэнли Ошер и соавторы использовали это свойство и преобразование Коула – Хопфа, чтобы вывести алгоритм вычисления приближений к проксимальному оператору функции. ^[4]

См. также

Ссылки

^ Моро, Дж.Дж. (1965). «Близость и двойственность в гильбертовом пространстве» . Бюллетень Математического общества Франции . 93 : 273–299. дои : 10.24033/bsmf.1625 . ISSN 0037-9484 .
^ Перейти обратно: ^а ^б Нил Парих и Стивен Бойд (2013). «Проксимальные алгоритмы» (PDF) . Основы и тенденции оптимизации . 1 (3): 123–231 . Проверено 29 января 2019 г.
^ Хитон, Ховард; Фунг, Сэми Ву; Ошер, Стэнли (9 октября 2022 г.). «Глобальные решения невыпуклых задач путем эволюции УЧП Гамильтона – Якоби». arXiv : 2202.11014 [ math.OC ].
^ Ошер, Стэнли; Хитон, Ховард; Фунг, Сэми Ву (23 ноября 2022 г.). «Проксимальный оператор на основе Гамильтона – Якоби». arXiv : 2211.12997 [ math.OC ].

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

«Функция конверта Моро» , Математическая энциклопедия , EMS Press , 2001 [1994]
Проксимальный оператор на основе Гамильтона-Якоби : видео на YouTube, объясняющее алгоритм аппроксимации проксимального оператора.

[1] Моро, Дж.Дж. (1965). «Близость и двойственность в гильбертовом пространстве» . Бюллетень Математического общества Франции . 93 : 273–299. дои : 10.24033/bsmf.1625 . ISSN 0037-9484 .

[:0-2] Перейти обратно: ^а ^б Нил Парих и Стивен Бойд (2013). «Проксимальные алгоритмы» (PDF) . Основы и тенденции оптимизации . 1 (3): 123–231 . Проверено 29 января 2019 г.

[3] Хитон, Ховард; Фунг, Сэми Ву; Ошер, Стэнли (9 октября 2022 г.). «Глобальные решения невыпуклых задач путем эволюции УЧП Гамильтона – Якоби». arXiv : 2202.11014 [ math.OC ].

[4] Ошер, Стэнли; Хитон, Ховард; Фунг, Сэми Ву (23 ноября 2022 г.). «Проксимальный оператор на основе Гамильтона – Якоби». arXiv : 2211.12997 [ math.OC ].

[1]

[2]

[3]

[4]