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

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

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

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

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

Примерно в 2007 году произошло возрождение расширенных лагранжевых методов в таких областях, как полное шумоподавление и сжатое измерение . вариант стандартного расширенного метода Лагранжа, который использует частичные обновления (аналогично методу Гаусса – Зейделя для решения линейных уравнений), известный как метод множителей переменного направления или ADMM В частности, некоторое внимание привлек .

Общий метод

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

$\min f(\mathbf {x} )$

при условии

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

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

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

Метод штрафа решает эту проблему, затем на следующей итерации он повторно решает проблему, используя большее значение $\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})$

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

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

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

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

Метод множителей чередующегося направления (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 можно рассматривать как применение алгоритма разделения Дугласа-Рэчфорда , а алгоритм Дугласа-Рэчфорда, в свою очередь, является примером алгоритма проксимальной точки ; подробности можно найти в исх. Существует несколько современных пакетов программного обеспечения, в том числе YALL1. (2009), СпаРСА (2009) и САЛЬСА (2009), которые решают задачи поиска и варианты базиса и используют ADMM. Существуют также пакеты, использующие ADMM для решения более общих задач, некоторые из которых могут использовать несколько вычислительных ядер (например, SNAPVX (2015), параАДММ (2016)).

Стохастическая оптимизация

Стохастическая оптимизация рассматривает проблему минимизации функции потерь с доступом к зашумленным выборкам функции (градиента). Цель состоит в том, чтобы получить оценку оптимального параметра (минимайзера) для каждой новой выборки. С некоторыми модификациями 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}}},$

где $\eta _{k+1}$ это изменяющийся во времени размер шага.

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

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

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

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

Программное обеспечение

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

• Accord.NET (реализация расширенного лагранжева оптимизатора на C#)
• ALGLIB (реализации C# и C++ предварительно обусловленного расширенного решателя Лагранжа)
• PENNON (GPL 3, доступна коммерческая лицензия)
• ЛАНСЕЛОТ (бесплатная лицензия для «внутреннего использования», платные коммерческие варианты)
• MINOS (также использует расширенный метод Лагранжа для некоторых типов задач).
• Код для лицензированного Apache 2.0 REASON доступен в Интернете.
• ALGENCAN (реализация расширенного метода Лагранжа на Фортране с гарантиями). Доступно онлайн.
• NLOPT (реализация расширенного лагранжева оптимизатора на C++, доступная из разных языков программирования). )
• PyProximal (реализация расширенного лагранжевого метода на Python).

См. также

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

Библиография

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