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

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

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

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

Основы алгоритма [ править ]

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

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

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

{\ 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. ^[2]^[3]
LabVIEW
KNITRO ^[4] (C, C ++, C #, Java, Python, Fortran)
NPSOL (Фортран)
СНОПТ (Фортран)
NLPQL (Фортран)
MATLAB
СуанШу (Ява)

См. Также [ править ]

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

Заметки [ править ]

^ Хорхе Нокедал и Стивен Дж. Райт (2006). Численная оптимизация . Springer. ISBN 978-0-387-30303-1.
^ Крафт, Дитер (сентябрь 1994). «Алгоритм 733: модули TOMP – Fortran для расчетов оптимального управления» . Транзакции ACM на математическом программном обеспечении . 20 (3): 262–281. CiteSeerX 10.1.1.512.2567 . DOI : 10.1145 / 192115.192124 . S2CID 16077051 . Дата обращения 1 февраля 2019 .
^ Крафт, Дитер (июль 1988 г.). «Программный комплекс для последовательного квадратичного программирования» . Технический отчет DFVLR-FB 88-28 . Оберпфаффенхофен: Institut für Dynamik der Flugsysteme . Дата обращения 1 февраля 2019 .
^ Руководство пользователя KNITRO: Алгоритмы

Ссылки [ править ]

Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастизабал, Клаудиа А. (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

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

[1] Хорхе Нокедал и Стивен Дж. Райт (2006). Численная оптимизация . Springer. ISBN 978-0-387-30303-1.

[Kraft-2] Крафт, Дитер (сентябрь 1994). «Алгоритм 733: модули TOMP – Fortran для расчетов оптимального управления» . Транзакции ACM на математическом программном обеспечении . 20 (3): 262–281. CiteSeerX 10.1.1.512.2567 . DOI : 10.1145 / 192115.192124 . S2CID 16077051 . Дата обращения 1 февраля 2019 .

[3] Крафт, Дитер (июль 1988 г.). «Программный комплекс для последовательного квадратичного программирования» . Технический отчет DFVLR-FB 88-28 . Оберпфаффенхофен: Institut für Dynamik der Flugsysteme . Дата обращения 1 февраля 2019 .

[4] Руководство пользователя KNITRO: Алгоритмы

[1]