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

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

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

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

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

${\ displaystyle {\ begin {array} {rl} \ min \ limits _ {x} & f (x) \\ {\ mbox {subject to}} & b (x) \ geq 0 \\ & c (x) = 0. \ end {массив}}}$

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

${\ Displaystyle {\ mathcal {L}} (х, \ лямбда, \ сигма) = е (х) - \ лямбда Ь (х) - \ сигма с (х),}$

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

${\ displaystyle {\ 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 { st} & b (x_ {k}) + \ nabla b (x_ {k}) ^ {T} d \ geq 0 \\ & c (x_ {k}) + \ nabla c (x_ {k}) ^ {T} d = 0. \ end {массив}}}$

Обратите внимание, что член в приведенном выше выражении может быть опущен для задачи минимизации, поскольку он постоянен под оператором. ${\ displaystyle f (x_ {k})}$${\ displaystyle \ min \ 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, Фортран)
• NPSOL (Фортран)
• СНОПТ (Фортран)
• NLPQL (Фортран)
• MATLAB
• СуанШу (Ява)

Смотрите также

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

Примечания

Рекомендации

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

внешняя ссылка

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

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