Расширенный лагранжевый метод

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

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

Этот метод был первоначально известен как метод множителей и много изучался в 1970 и 1980-х годах как хорошая альтернатива штрафным методам. Впервые он был обсужден Магнусом Хестенесом и Майклом Пауэллом в 1969 году. Метод был изучен Р. Тиррелл Рокафеллар в отношении двойственности Фенхеля, особенно в отношении методов проксимальной точки и максимальных монотонных операторов : эти методы использовались в структурной оптимизации. Этот метод также изучал Димитрий Бертсекас, в частности, в его книге 1982 года, вместе с расширениями, включающими неквадратичные функции регуляризации, такие как энтропийная регуляризация, которая дает начало «экспоненциальному методу множителей., "метод, который обрабатывает ограничения неравенства с дважды дифференцируемой расширенной функцией Лагранжа.

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

• 1 Общий метод
• 2 Метод переменного направления множителей
• 3 Стохастическая оптимизация
• 4 Альтернативные подходы
• 5 Программное обеспечение
• 6 См. Также
• 7 Ссылки
• 8 Библиография

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

$min\; f\; (x)\; \{\backslash \; displaystyle\; \backslash \; min\; f\; (\backslash \; mathbf\; \{x\})\}$

subject to

$ci\; (x)\; =\; 0\; \forall \; i\; \in \; I.\; \{\backslash \; displaystyle\; c\_\; \{i\}\; (\backslash \; mathbf\; \{x\})\; =\; 0\; ~\; \backslash \; forall\; i\; \backslash \; in\; I.\}$

Эту проблему можно решить как серию задач безусловной минимизации. Для справки сначала перечислим k-й шаг метода метода штрафа :

$min\; \Phi \; k\; (x)\; =\; f\; (x)\; +\; \mu \; k\; \sum \; i\; \in \; I\; c\; i\; (x)\; 2.\; \{\backslash \; displaystyle\; \backslash \; min\; \backslash \; Phi\; \_\; \{k\}\; (\backslash \; mathbf\; \{x\})\; =\; f\; (\backslash \; mathbf\; \{x\})\; +\; \backslash \; mu\; \_\; \{k\}\; ~\; \backslash \; sum\; \_\; \{i\; \backslash \; in\; I\}\; ~\; c\_\; \{i\}\; (\; \backslash \; mathbf\; \{x\})\; ^\; \{2\}.\}$

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

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

$min\; \Phi \; k\; (x)\; =\; f\; (x)\; +\; \mu \; k\; 2\; \sum \; i\; \in \; I\; ci\; (x)\; 2\; +\; \sum \; i\; \in \; I\; \lambda \; ici\; (Икс)\; \{\backslash \; Displaystyle\; \backslash \; мин\; \backslash \; Phi\; \_\; \{к\}\; (\backslash \; mathbf\; \{x\})\; =\; F\; (\backslash \; mathbf\; \{x\})\; +\; \{\backslash \; frac\; \{\backslash \; mu\; \_\; \{k\}\}\; \{2\}\}\; ~\; \backslash \; сумма\; \_\; \{i\; \backslash \; in\; I\}\; ~\; c\_\; \{i\}\; (\backslash \; mathbf\; \{x\})\; ^\; \{2\}\; +\; \backslash \; sum\; \_\; \{i\; \backslash \; in\; I\}\; ~\; \backslash \; lambda\; \_\; \{i\}\; c\_\; \{i\}\; (\backslash \; mathbf\; \{x\})\; \}$

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

$\lambda \; i\; \leftarrow \; \lambda \; i\; +\; \mu \; kci\; (xk)\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{i\}\; \backslash \; leftarrow\; \backslash \; lambda\; \_\; \{i\}\; +\; \backslash \; mu\; \_\; \{k\}\; c\_\; \{\; i\}\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\})\}$

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

Переменная $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$является оценкой множителя Лагранжа и точности этой оценки улучшается с каждым шагом. Основное преимущество метода заключается в том, что в отличие от метода штрафа , нет необходимости брать $\mu \; \to \; \infty \; \{\backslash \; displaystyle\; \backslash \; mu\; \backslash \; rightarrow\; \backslash \; infty\}$, чтобы решить исходную задачу с ограничениями. Вместо этого, из-за наличия множителя Лагранжа, $\mu \; \{\backslash \; displaystyle\; \backslash \; mu\}$может оставаться намного меньше, что позволяет избежать плохой обусловленности.

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

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

$min\; x\; f\; (x)\; +\; g\; (x).\; \{\backslash \; displaystyle\; \backslash \; min\; \_\; \{x\}\; f\; (x)\; +\; g\; (x).\}$

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

$min\; x,\; yf\; (x)\; +\; g\; (y),\; при\; условии\; x\; =\; у.\; \{\backslash \; displaystyle\; \backslash \; min\; \_\; \{x,\; y\}\; f\; (x)\; +\; g\; (y),\; \backslash \; quad\; \{\backslash \; text\; \{subject\; to\}\}\; \backslash \; quad\; x\; =\; y.\}$

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

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

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

$L\; ^\; \rho ,\; k\; =\; f\; 1\; (xk)\; +\; ⟨\nabla \; f\; (xk,\; \zeta \; k\; +\; 1),\; Икс⟩\; +\; г\; (Y)\; -\; Z\; T\; (A\; Икс\; +\; В\; Y\; -\; с)\; +\; \rho \; 2\; \Vert \; A\; Икс\; +\; В\; Y\; -\; с\; \Vert \; 2\; +\; \Vert \; Икс\; -\; XK\; \Vert \; 2\; 2\; \eta \; К\; +\; 1,\; \{\backslash \; Displaystyle\; \{\backslash \; шляпа\; \{\backslash \; mathcal\; \{L\}\}\}\; \_\; \{\backslash \; rho,\; k\}\; =\; f\_\; \{1\}\; (x\_\; \{k\})\; +\; \backslash \; langle\; \backslash \; nabla\; f\; (x\_\; \{k\},\; \backslash \; zeta\; \_\; \{k\; +\; 1\}),\; x\; \backslash \; rangle\; +\; g\; (y)\; -z\; ^\; \{T\}\; (Ax\; +\; By-c)\; +\; \{\backslash \; frac\; \{\backslash \; rho\}\; \{2\}\}\; \backslash \; Vert\; Ax\; +\; By-c\; \backslash \; Vert\; ^\; \{2\}\; +\; \{\backslash \; frac\; \{\; \backslash \; Vert\; x-x\_\; \{k\}\; \backslash \; Vert\; ^\; \{2\}\}\; \{2\; \backslash \; eta\; \_\; \{k\; +\; 1\}\}\},\}$

где $\eta \; k\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; eta\; \_\; \{k\; +\; 1\; \}\}$- размер шага, изменяющийся во времени.

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

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

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

• Accord.NET (реализация C # расширенного лагранжевого оптимизатора)
• ALGLIB (реализации C # и C ++ предварительно обусловленного расширенного лагранжевого решателя)
• (GPL 3, коммерческая лицензия доступно)
• LANCELOT (бесплатная лицензия для «внутреннего использования», платные коммерческие опции)
• MINOS (также использует расширенный лагранжев метод для некоторых типов проблем).
• Код для Apache 2.0 доступна в Интернете.

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

1. ^Hestenes, MR (1969). «Множители и градиентные методы». Журнал теории оптимизации и приложений. 4 : 303–320. doi : 10.1007 / BF00927673.
2. ^Пауэлл, М. Дж. Д. (1969). «Метод нелинейных ограничений в задачах минимизации». В Флетчер, Р. (ред.). Оптимизация. Нью-Йорк: Academic Press. С. 283–298. ISBN 0-12-260650-7.
3. ^Берцекас, Дмитрий П. (1996) [1982]. Ограниченная оптимизация и методы множителя Лагранжа. Athena Scientific.
4. ^ Nocedal Wright (2006), глава 17
5. ^Eckstein, J.; Бертсекас, Д. П. (1992). «О методе расщепления Дугласа – Рачфорда и алгоритме проксимальной точки для максимальных монотонных операторов». Математическое программирование. 55 (1–3): 293–318. CiteSeerX 10.1.1.141.6246. doi : 10.1007 / BF01581204.
6. ^Ouyang, H.; Курицы.; Тран Л. и Грей А. Г. (2013). «Стохастический метод переменных направлений множителей». Материалы 30-й Международной конференции по машинному обучению: 80–88.
7. ^Boyd, S.; Парих, Н.; Chu, E.; Пелеато, Б. Экштейн, Дж. (2011). «Распределенная оптимизация и статистическое обучение с помощью метода множителей переменного направления». Основы и тенденции {\ textregistered} в машинном обучении. 3 (1): 1–122. CiteSeerX 10.1.1.360.1664. doi : 10.1561 / 2200000016.
8. ^Wahlberg, B.; Boyd, S.; Аннергрен, М.; Ван, Ю. (2012). "Алгоритм ADMM для класса регуляризованных задач оценивания полной вариации". arXiv : 1203.1828 [stat.ML ].
9. ^Esser, E.; Чжан, X.; Чан, Т. (2010). «Общая основа для класса первично-дуальных алгоритмов первого порядка для выпуклой оптимизации в области визуализации». SIAM Journal on Imaging Sciences. 3 (4).
10. ^Mota, J. FC; Xavier, J. MF; Aguiar, P. MQ; Пущель, М. (2012). «Распределенный ADMM для прогнозирующего управления моделью и контроля перегрузки». Решение и контроль (CDC), 2012 г. 51-я ежегодная конференция IEEE О.
11. ^«Код ПРИЧИНЫ».

• Бертсекас, Дмитрий П. (1999), Нелинейное программирование (2-е изд.), Бельмонт, Массачусетс: Athena Scientific, ISBN 978-1-886529-00-7
• Носедал, Хорхе; Райт, Стивен Дж. (2006), Численная оптимизация (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-0-387-30303- 1