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

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

Методы SQP решают последовательность подзадач оптимизации, каждая из которых оптимизирует квадратичную модель цели с учетом линеаризации ограничений. Если задача не имеет ограничений, то метод сводится к методу Ньютона для поиска точки, в которой градиент цели исчезает. Если задача имеет только ограничения-равенства, то метод эквивалентен применению метода Ньютона к условиям оптимальности первого порядка или условиям Каруша – Куна – Такера задачи.

Основы алгоритма

Обзорная схема, иллюстрирующая базовый алгоритм SQP

Рассмотрим задачу нелинейного программирования вида:

${\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{subject to}}&h(x)\geq 0\\&g(x)=0.\end{array}}$

Лагранжиан есть для этой задачи

${\mathcal {L}}(x,\lambda ,\sigma )=f(x)+\lambda h(x)+\sigma g(x),$

где $\lambda$ и $\sigma$ являются множителями Лагранжа .

Стандартный метод Ньютона ищет решение. $\nabla {\mathcal {L}}(x,\lambda ,\sigma )=0$ повторяя следующее уравнение, где $\nabla _{xx}^{2}$ обозначает матрицу Гессе :

${\begin{bmatrix}x_{k+1}\\\lambda _{k+1}\\\sigma _{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\lambda _{k}\\\sigma _{k}\end{bmatrix}}-\underbrace {{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}&\nabla h&\nabla g\\\nabla h^{T}&0&0\\\nabla g^{T}&0&0\end{bmatrix}}^{-1}} _{\nabla ^{2}{\mathcal {L}}}\underbrace {\begin{bmatrix}\nabla f+\lambda _{k}\nabla h+\sigma _{k}\nabla g\\h\\g\end{bmatrix}} _{\nabla {\mathcal {L}}}$.

Однако поскольку матрица $\nabla ^{2}{\mathcal {L}}$ вообще сингулярна (и, следовательно, необратима ) , шаг Ньютона $d_{k}=\left(\nabla _{xx}^{2}{\mathcal {L}}\right)^{-1}\nabla {\mathcal {L}}$ невозможно вычислить напрямую. Вместо этого базовый алгоритм последовательного квадратичного программирования определяет подходящее направление поиска. $d_{k}$ на итерации $(x_{k},\lambda _{k},\sigma _{k})$, как решение квадратичного программирования подзадачи

${\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &h(x_{k})+\nabla h(x_{k})^{T}d\geq 0\\&g(x_{k})+\nabla g(x_{k})^{T}d=0.\end{array}}$

где квадратичная форма образована гессианом лагранжиана.Обратите внимание, что термин $f(x_{k})$ в приведенном выше выражении можно не учитывать в задаче минимизации, поскольку оно постоянно при $\min \limits _{d}$ оператор.

Вместе алгоритм SQP начинается с выбора начальной итерации. $(x_{0},\lambda _{0},\sigma _{0})$, затем вычисляем $\nabla ^{2}{\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})$ и $\nabla {\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})$. Затем строится и решается подзадача QP для нахождения направления шага Ньютона. $d_{0}$ который используется для обновления итерации родительской проблемы с использованием $\left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+d_{k}$. Этот процесс повторяется для $k=0,1,2,\ldots$ до тех пор, пока родительская задача не будет удовлетворять тесту на сходимость.

Практические реализации

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

• Возможность неразрешимой подзадачи QP.
• Подзадача QP, дающая плохой шаг: тот, который либо не может уменьшить цель, либо увеличивает нарушение ограничений.
• Срыв итераций из-за значительного отклонения цели/ограничений от их квадратичных/линейных моделей.

Для решения этих проблем обычно используются различные стратегии:

• Использование функций оценки, которые оценивают прогресс в направлении ограниченного решения, или методов фильтрации.
• Доверительные методы поиска области или линии для управления отклонениями между квадратичной моделью и фактической целью.
• Специальные этапы восстановления выполнимости для решения невыполнимых подзадач или использование подзадач с штрафом L1 для постепенного уменьшения невыполнимости.

Эти стратегии можно комбинировать различными способами, в результате чего получается широкий спектр методов SQP.

подходы

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

Реализации

Методы SQP были реализованы в хорошо известных численных средах, таких как MATLAB и GNU Octave . Также существует множество библиотек программного обеспечения, в том числе с открытым исходным кодом:

• SciPy (фактический стандарт для научного Python) имеет решатель scipy.optimize.minimize(method='SLSQP').
• NLopt (реализация C/C++ с многочисленными интерфейсами, включая Julia, Python, R, MATLAB/Octave), реализованная Дитером Крафтом как часть пакета для оптимального управления и модифицированная С.Г. Джонсоном.
• Решатель ALGLIB SQP (C++, C#, Java, Python API)

и коммерческий

• ЛабВЬЮ
• КНИТРО (C, C++, C#, Java, Python, Julia, Fortran)
• НПСОЛ (Фортран)
• СНОПТ (Фортран)
• НЛПQL (Фортран)
• МАТЛАБ
• СуанШу (Ява)

См. также

• метод Ньютона
• Метод секущего
• Модель прогнозирующего управления

Ссылки

• Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: Теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. дои : 10.1007/978-3-540-35447-5 . ISBN  978-3-540-35445-1 . МР   2265882 .
• Хорхе Носедал и Стивен Дж. Райт (2006). Численная оптимизация . Спрингер. ISBN  978-0-387-30303-1 .

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

• Руководство по последовательному квадратичному программированию в NEOS