Дополненный лагранжев метод

Расширенные лагранжевые методы - это определенный класс алгоритмов для решения задач оптимизации с ограничениями . У них есть сходство с методами штрафа в том, что они заменяют задачу оптимизации с ограничениями серией задач без ограничений и добавляют штрафной член к цели ; разница в том, что расширенный метод Лагранжа добавляет еще один член, имитирующий множитель Лагранжа . Расширенный лагранжиан связан с методом множителей Лагранжа , но не идентичен ему .

С другой стороны, неограниченная цель - это лагранжиан ограниченной задачи с дополнительным штрафным членом ( увеличением ).

Первоначально этот метод был известен как метод множителей и много изучался в 1970 и 1980-х годах как хорошая альтернатива методам штрафов. Это впервые было рассмотрено Магнусом Хестенс , ^[1] и Майкл Пауэлл в 1969 году ^[2] Этот метод был исследован Р. Tyrrell Рокафеллар по отношению к Фенхелю двойственности , особенно в отношении методов проксимальных-точечных, Moreau-Иосиды регуляризации , и максимальные монотонные операторы : эти методы использовались в структурной оптимизации . Этот метод также изучал Дмитрий Бертсекас , в частности, в его книге 1982 г.^[3] вместе с расширениями, включающими неквадратичные функции регуляризации, такие как энтропийная регуляризация , которая приводит к «экспоненциальному методу множителей», методу, который обрабатывает ограничения неравенства с дважды дифференцируемой расширенной функцией Лагранжа.

С 1970-х годов последовательное квадратичное программирование (SQP) и методы внутренней точки (IPM) привлекают все большее внимание, отчасти потому, что они более легко используют подпрограммы с разреженными матрицами из библиотек численного программного обеспечения , а отчасти потому, что IPM доказали сложность результатов с помощью теории самосогласованные функции . Расширенный метод Лагранжа был обновлен системами оптимизации LANCELOT , ALGENCAN ^[4]^[5] и AMPL , которые позволили использовать методы разреженных матриц для решения кажущихся плотными, но «частично разделимых» проблем. Этот метод все еще полезен для некоторых проблем. ^[6] Примерно в 2007 году произошло возрождение расширенных лагранжевых методов в таких областях, как шумоподавление с полной вариацией и сжатое зондирование . В частности, некоторое внимание привлек вариант стандартного расширенного метода Лагранжа, который использует частичные обновления (аналогично методу Гаусса – Зейделя для решения линейных уравнений), известный как метод множителей переменного направления или ADMM .

Общий метод [ править ]

Допустим, мы решаем следующую задачу с ограничениями:

{\ Displaystyle \ мин е (\ mathbf {х})}

при условии

{\ displaystyle c_ {i} (\ mathbf {x}) = 0 ~ \ forall i \ in {\ mathcal {E}}.}

, где обозначает индексы для ограничений-равенств. Эта проблема может быть решена в виде серии задач безусловной минимизации. Для справки, сначала перечислим k- й шаг метода штрафа : ${\ displaystyle {\ mathcal {E}}}$

{\ displaystyle \ min \ Phi _ {k} (\ mathbf {x}) = f (\ mathbf {x}) + \ mu _ {k} ~ \ sum _ {i \ in {\ mathcal {E}}} ~ c_ {i} (\ mathbf {x}) ^ {2}.}

Метод штрафа решает эту проблему, а затем на следующей итерации повторно решает проблему, используя большее значение (и используя старое решение в качестве первоначального предположения или «горячего старта»). ${\ displaystyle \ mu _ {k}}$

Расширенный метод Лагранжа использует следующую неограниченную цель:

\min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )

и после каждой итерации, помимо обновления , переменная также обновляется по правилу $\mu _{k}$ $\lambda$

\lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})

где - решение неограниченной задачи на k- м шаге, т.е. $\mathbf {x} _{k}$ $\mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )$

Переменная является оценкой множителя Лагранжа , и точность этой оценки улучшается с каждым шагом. Основное преимущество метода заключается в том, что в отличие от метода штрафа его не нужно использовать для решения исходной задачи с ограничениями. Вместо этого, из-за наличия множителя Лагранжа, он может оставаться намного меньшим, что позволяет избежать плохой обусловленности. ^[6] Тем не менее, в практических реализациях принято проецировать оценки множителей в большом ограниченном множестве (гарантии), избегая числовых нестабильностей и приводя к сильной теоретической сходимости. ^[7] $\lambda$ $\mu \rightarrow \infty$ $\mu$

Метод может быть расширен для обработки ограничений неравенства. Для обсуждения практических улучшений см. ^[6]^[5]

Метод переменного направления множителей [ править ]

Метод множителей с переменным направлением (ADMM) - это вариант расширенной схемы Лагранжа, в которой используются частичные обновления двойных переменных. Этот метод часто применяется для решения таких задач, как

\min _{x}f(x)+g(x).

Это эквивалентно задаче с ограничениями

\min _{x,y}f(x)+g(y),\quad {\text{subject to}}\quad x=y.

Хотя это изменение может показаться тривиальным, теперь проблема может быть решена с использованием методов ограниченной оптимизации (в частности, расширенного метода Лагранжа), а целевая функция разделяется по x и y . Двойное обновление требует одновременного решения функции близости по x и y ; Метод ADMM позволяет приблизительно решить эту проблему, сначала решая для x с фиксированным y , а затем решая для y с фиксированным x . Вместо того, чтобы повторять до сходимости (как метод Якоби), алгоритм переходит непосредственно к обновлению двойной переменной, а затем повторяет процесс. Это не эквивалентно точной минимизации, но, что удивительно, все же можно показать, что этот метод сходится к правильному ответу (при некоторых предположениях). Из-за этого приближения алгоритм отличается от чисто расширенного лагранжевого метода.

ADMM можно рассматривать как приложение алгоритма расщепления Дугласа-Рэчфорда , а алгоритм Дугласа-Рэчфорда, в свою очередь, является экземпляром алгоритма проксимальной точки ; подробности можно найти здесь. ^[8] Существует несколько современных программных пакетов, которые решают базовое преследование и варианты и используют ADMM; такие пакеты включают YALL1 ^[9] (2009 г.), SpaRSA ^[10] (2009 г.) и SALSA ^[11] (2009 г.). Существуют также пакеты, которые используют ADMM для решения более общих проблем, некоторые из которых могут использовать несколько вычислительных ядер SNAPVX ^[12] (2015), parADMM ^[13] (2016).

Стохастическая оптимизация [ править ]

Этот раздел содержит контент, который написан как реклама . Пожалуйста, помогите улучшить его , удалив рекламный контент и неприемлемые внешние ссылки , а также добавив энциклопедический контент, написанный с нейтральной точки зрения . ( Апрель 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Стохастическая оптимизация рассматривает проблему минимизации функции потерь с доступом к зашумленным выборкам функции (градиента). Цель состоит в том, чтобы получить оценку оптимального параметра (минимизатора) для каждой новой выборки. ADMM изначально был пакетным методом. Однако с некоторыми изменениями его также можно использовать для стохастической оптимизации. Поскольку в стохастической настройке у нас есть доступ только к зашумленным образцам градиента, мы используем неточную аппроксимацию лагранжиана как

${\hat {\mathcal {L}}}_{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert Ax+By-c\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},$

где - изменяющийся во времени размер шага. ^[14] $\eta _{k+1}$

Метод множителей с переменным направлением (ADMM) является популярным методом для онлайн и распределенной оптимизации в больших масштабах, ^[15] и используется во многих приложениях, например, ^[16]^[17]^[18] ADMM часто применяется для решения регуляризованных задачи, в которых оптимизация функций и регуляризация могут выполняться локально, а затем координироваться глобально с помощью ограничений. Задачи регуляризованной оптимизации особенно актуальны в режиме высокой размерности, поскольку регуляризация является естественным механизмом для преодоления некорректности и поощрения экономии в оптимальном решении, например, разреженности и низкого ранга. Благодаря эффективности ADMM при решении регуляризованных задач, он имеет хороший потенциал для стохастической оптимизации в больших размерностях.

Альтернативные подходы [ править ]

Последовательное квадратичное программирование
Последовательное линейное программирование
Последовательное линейно-квадратичное программирование

Программное обеспечение [ править ]

Открытый исходный код и несвободные / коммерческие реализации расширенного метода Лагранжа:

Accord.NET (реализация расширенного лагранжевого оптимизатора на C #)
ALGLIB (реализации C # и C ++ предобусловленного расширенного лагранжевого решателя)
ПЕННОН (GPL 3, доступна коммерческая лицензия)
LANCELOT (бесплатная лицензия для «внутреннего использования», платные коммерческие опции)
MINOS (также использует расширенный лагранжев метод для некоторых типов задач).
Код для лицензированного Apache 2.0 REASON доступен в Интернете. ^[19]
ALGENCAN (реализация на Фортране расширенного лагранжевого метода с гарантиями). Доступно онлайн. ^[20]
Масштабированный АЛГЕНКАН (ALGENCAN с дополнительной возможностью масштабирования окончательного решения). Доступно онлайн. ^[21]

См. Также [ править ]

Барьерная функция
Метод внутренней точки
Множитель Лагранжа
Штрафной метод

Ссылки [ править ]

^ Hestenes, MR (1969). «Множители и градиентные методы». Журнал теории оптимизации и приложений . 4 (5): 303–320. DOI : 10.1007 / BF00927673 . S2CID 121584579 .
^ Пауэлл, MJD (1969). «Метод нелинейных ограничений в задачах минимизации». В Флетчер, Р. (ред.). Оптимизация . Нью-Йорк: Academic Press. С. 283–298. ISBN 0-12-260650-7.
^ Bertsekas, Дмитрий П. (1996) [1982]. Ограниченная оптимизация и методы множителя Лагранжа . Афина Сайентифик.
^ Андреани, R .; Биргин, ЭГ; Мартинес, JM; Шувердт, ML (2007). «О расширенных лагранжевых методах с общими ограничениями нижнего уровня». SIAM Journal по оптимизации . 18 (4): 1286–1309. DOI : 10.1137 / 060654797 .
^ a b Биргин и Мартинес (2014)
^ a b c Нокедал и Райт (2006) , глава 17
^ Андреани, R .; Fazzio, NS; Schuverdt, ML; Секчин, ЛД (2019). «Последовательное условие оптимальности, связанное с квалификацией ограничения квазинормальности и его алгоритмические последствия». SIAM Journal по оптимизации . 29 (1): 743–766. DOI : 10.1137 / 17M1147330 .
^ Eckstein, J .; Бертсекас, Д.П. (1992). «О методе расщепления Дугласа — Рачфорда и алгоритме проксимальной точки для максимальных монотонных операторов». Математическое программирование . 55 (1–3): 293–318. CiteSeerX 10.1.1.141.6246 . DOI : 10.1007 / BF01581204 . S2CID 15551627 .
^ «YALL1: Ваши алгоритмы для L1» . yall1.blogs.rice.edu .
^ "SpaRSA" . www.lx.it.pt .
^ "(C) SALSA: Решение проблем выпуклой оптимизации при восстановлении изображений" . cascais.lx.it.pt .
^ "SnapVX" . snap.stanford.edu .
^ "parADMM / engine" . 6 февраля 2021 г. - через GitHub.
^ Ouyang, H .; Курицы.; Тран, Л., Грей, А. Г. (2013). «Стохастический метод переменных направлений множителей». Материалы 30-й Международной конференции по машинному обучению : 80–88.
^ Boyd, S .; Парих, Н .; Chu, E .; Пелеато, Б. и Экштейн, Дж. (2011). «Распределенная оптимизация и статистическое обучение с помощью метода множителей переменного направления». Основы и тенденции {\ textregistered} в машинном обучении . 3 (1): 1–122. CiteSeerX 10.1.1.360.1664 . DOI : 10.1561 / 2200000016 .
^ Wahlberg, B .; Boyd, S .; Аннергрен, М .; Ван, Ю. (2012). "Алгоритм ADMM для класса регуляризованных задач оценивания полной вариации". arXiv : 1203.1828 [ stat.ML ].
^ Esser, E .; Чжан, X .; Чан, Т. (2010). «Общая основа для класса первично-дуальных алгоритмов первого порядка для выпуклой оптимизации в области визуализации». SIAM Journal on Imaging Sciences . 3 (4): 1015–1046. DOI : 10.1137 / 09076934X .
^ Мота, Дж. ФК; Xavier, J. MF; Aguiar, P. MQ; Пущел, М. (2012). «Распределенный ADMM для прогнозирующего управления моделью и контроля перегрузки». Решение и контроль (CDC), 51-я ежегодная конференция IEEE 2012 г. O : 5110–5115. DOI : 10.1109 / CDC.2012.6426141 . ISBN 978-1-4673-2066-5. S2CID 12128421 .
^ "Bitbucket" . bitbucket.org .
^ "Проект ТАНГО" . www.ime.usp.br .
^ "Леонардосекхин / чешуйчатый альгенкан" . 8 апреля 2021 г. - через GitHub.

Библиография [ править ]

Бертсекас, Дмитрий П. (1999), Нелинейное программирование (2-е изд.), Бельмонт, Массачусетс: Athena Scientific , ISBN 978-1-886529-00-7
Биргин, ЭГ; Мартинес, JM (2014), практическая дополненной лагранжевых методы условной оптимизации , Филадельфия: Общество промышленной и прикладной математики , DOI : 10,1137 / +1,9781611973365 , ISBN 978-1-611973-35-8
Нокедаль, Хорхе; Райт, Стивен Дж. (2006), Численная оптимизация (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-30303-1

[1] Hestenes, MR (1969). «Множители и градиентные методы». Журнал теории оптимизации и приложений . 4 (5): 303–320. DOI : 10.1007 / BF00927673 . S2CID 121584579 .

[2] Пауэлл, MJD (1969). «Метод нелинейных ограничений в задачах минимизации». В Флетчер, Р. (ред.). Оптимизация . Нью-Йорк: Academic Press. С. 283–298. ISBN 0-12-260650-7.

[3] Bertsekas, Дмитрий П. (1996) [1982]. Ограниченная оптимизация и методы множителя Лагранжа . Афина Сайентифик.

[4] Андреани, R .; Биргин, ЭГ; Мартинес, JM; Шувердт, ML (2007). «О расширенных лагранжевых методах с общими ограничениями нижнего уровня». SIAM Journal по оптимизации . 18 (4): 1286–1309. DOI : 10.1137 / 060654797 .

[BirginMartinez_2014-5] Биргин и Мартинес (2014)

[Nocedal_2006-6] Нокедал и Райт (2006) , глава 17

[7] Андреани, R .; Fazzio, NS; Schuverdt, ML; Секчин, ЛД (2019). «Последовательное условие оптимальности, связанное с квалификацией ограничения квазинормальности и его алгоритмические последствия». SIAM Journal по оптимизации . 29 (1): 743–766. DOI : 10.1137 / 17M1147330 .

[8] Eckstein, J .; Бертсекас, Д.П. (1992). «О методе расщепления Дугласа — Рачфорда и алгоритме проксимальной точки для максимальных монотонных операторов». Математическое программирование . 55 (1–3): 293–318. CiteSeerX 10.1.1.141.6246 . DOI : 10.1007 / BF01581204 . S2CID 15551627 .

[9] «YALL1: Ваши алгоритмы для L1» . yall1.blogs.rice.edu .

[10] "SpaRSA" . www.lx.it.pt .

[11] "(C) SALSA: Решение проблем выпуклой оптимизации при восстановлении изображений" . cascais.lx.it.pt .

[12] "SnapVX" . snap.stanford.edu .

[13] "parADMM / engine" . 6 февраля 2021 г. - через GitHub.

[14] Ouyang, H .; Курицы.; Тран, Л., Грей, А. Г. (2013). «Стохастический метод переменных направлений множителей». Материалы 30-й Международной конференции по машинному обучению : 80–88.

[15] Boyd, S .; Парих, Н .; Chu, E .; Пелеато, Б. и Экштейн, Дж. (2011). «Распределенная оптимизация и статистическое обучение с помощью метода множителей переменного направления». Основы и тенденции {\ textregistered} в машинном обучении . 3 (1): 1–122. CiteSeerX 10.1.1.360.1664 . DOI : 10.1561 / 2200000016 .

[16] Wahlberg, B .; Boyd, S .; Аннергрен, М .; Ван, Ю. (2012). "Алгоритм ADMM для класса регуляризованных задач оценивания полной вариации". arXiv : 1203.1828 [ stat.ML ].

[17] Esser, E .; Чжан, X .; Чан, Т. (2010). «Общая основа для класса первично-дуальных алгоритмов первого порядка для выпуклой оптимизации в области визуализации». SIAM Journal on Imaging Sciences . 3 (4): 1015–1046. DOI : 10.1137 / 09076934X .

[18] Мота, Дж. ФК; Xavier, J. MF; Aguiar, P. MQ; Пущел, М. (2012). «Распределенный ADMM для прогнозирующего управления моделью и контроля перегрузки». Решение и контроль (CDC), 51-я ежегодная конференция IEEE 2012 г. O : 5110–5115. DOI : 10.1109 / CDC.2012.6426141 . ISBN 978-1-4673-2066-5. S2CID 12128421 .

[19] "Bitbucket" . bitbucket.org .

[20] "Проект ТАНГО" . www.ime.usp.br .

[21] "Леонардосекхин / чешуйчатый альгенкан" . 8 апреля 2021 г. - через GitHub.

[1]