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

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

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

• 1 Основы алгоритмов
• 2 Альтернативные подходы
• 3 Реализации
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Внешние ссылки

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

$min\; xf\; (x)\; st\; б\; (Икс)\; \ge \; 0\; с\; (Икс)\; =\; 0.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{array\}\; \{rl\}\; \backslash \; min\; \backslash \; limits\; \_\; \{x\}\; f\; (x)\; \backslash \backslash \; \{\backslash \; t\_dv\; \{st\}\}\; b\; (x)\; \backslash \; geq\; 0\; \backslash \backslash \; c\; (x)\; =\; 0.\; \backslash \; end\; \{array\}\}\}$

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

$L\; (x,\; \lambda ,\; \sigma )\; =\; f\; (x)\; -\; \lambda \; б\; (Икс)\; -\; \sigma \; с\; (Икс),\; \{\backslash \; Displaystyle\; \{\backslash \; mathcal\; \{L\}\}\; (х,\; \backslash \; lambda,\; \backslash \; sigma)\; =\; f\; (x)\; -\; \backslash \; lambda\; b\; (x)\; -\; \backslash \; sigma\; c\; (x),\}$

где $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$и $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$- множители Лагранжа. На итерации $xk\; \{\backslash \; displaystyle\; x\_\; \{k\}\}$базовый алгоритм последовательного квадратичного программирования определяет соответствующее направление поиска $dk\; \{\backslash \; displaystyle\; d\_\; \{k\}\}$как решение подзадачи квадратичного программирования

$min\; df\; (xk)\; +\; \nabla \; f\; (xk)\; T\; d\; +\; 1\; 2\; d\; T\; \nabla \; xx\; 2\; L\; (xk,\; \lambda \; k,\; \sigma \; k)\; ds.\; т.\; б\; (xk)\; +\; \nabla \; b\; (xk)\; T\; d\; \ge \; 0\; c\; (xk)\; +\; \nabla \; c\; (xk)\; T\; d\; =\; 0.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{rl\}\; \backslash \; min\; \backslash \; limits\; \_\; \{d\}\; f\; (x\_\; \{k\})\; +\; \backslash \; nabla\; f\; (x\_\; \{k\})\; ^\; \{T\}\; d\; +\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; d\; ^\; \{T\}\; \backslash \; nabla\; \_\; \{xx\}\; ^\; \{2\}\; \{\backslash \; mathcal\; \{\; L\}\}\; (x\_\; \{k\},\; \backslash \; lambda\; \_\; \{k\},\; \backslash \; sigma\; \_\; \{k\})\; d\; \backslash \backslash \backslash \; mathrm\; \{st\}\; b\; (x\_\; \{k\})\; +\; \backslash \; nabla\; b\; (x\_\; \{k\})\; ^\; \{\; T\}\; d\; \backslash \; geq\; 0\; \backslash \backslash \; c\; (x\_\; \{k\})\; +\; \backslash \; nabla\; c\; (x\_\; \{k\})\; ^\; \{T\}\; d\; =\; 0.\; \backslash \; End\; \{array\}\}\}$

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

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

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

• SciPy (де-факто стандарт для научного Python) имеет решатель scipy.optimize.minimize (method = 'SLSQP').
• NLopt (C / C ++ с многочисленными интерфейсами, включая Julia, Python, R, MATLAB / Octave), реализованный Дитером Крафт как часть пакета для оптимального управления и модифицированный SG Johnson.
• LabVIEW
• KNITRO ( C, C ++, C #, Java, Python, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Java)

• Алгоритм Джозефи-Ньютона
• метод Ньютона
• Секущий метод

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

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

.