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

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

Методи SQP вирішують послідовність підпроблем оптимізації, кожна з яких оптимізує квадратичну модель об'єкта, що підлягає лінеаризації обмежень. Якщо проблема не обмежена, то метод зводиться до методу Ньютона для пошуку точки, де градієнт об'єкта зникає. Якщо проблема має лише обмеження рівності, то метод еквівалентний застосуванню методу Ньютона до умов оптимальності першого порядку або умов Каруша – Куна – Таккера .

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

Розглянемо нелінійну задачу програмування даної форми:

{\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}

Лагранжан для цієї проблеми є [1]

{\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}(b(x)-(y_{i})^{2})-\sigma ^{T}c(x),

де $\lambda$ і $\sigma$ є множниками Лагранжа . На ітерації $x_{k}$ , основний алгоритм послідовного квадратичного програмування визначає відповідний напрямок пошуку $d_{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.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}

Зауважимо, що функція $f(x_{k})$ у рівнянні вище може бути залишена для проблеми мінімізації, оскільки вона є постійною.

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

Послідовне лінійне програмування
Послідовне лінійно-квадратичне програмування
Доповнений метод Лагрангія

Впровадження

Методами SQP були реалізовані такі добре відомі числові середовища, як MATLAB і GNU Octave . Існують також численні бібліотеки програмного забезпечення, в тому числі з відкритим кодом

SciPy (фактично стандарт для наукового Python) має розв'язувач scipy.optimize.minimize (метод = 'SLSQP').
NLopt (реалізація C / C ++, з численними інтерфейсами, включаючи Python, R, MATLAB / Octave), реалізований Dieter Kraft як частина пакету для оптимального управління та модифікований SG Johnson. [2] [3]
LabVIEW
KNITRO [4] (C, C ++, C #, Java, Python, Fortran)
NPSOL (Фортран)
SNOPT (Фортран)
NLPQL (Fortran)
MATLAB

SuanShu (Java)

Дивись також

Примітки

Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.
Kraft, Dieter (Sep 1994). Algorithm 733: TOMP–Fortran modules for optimal control calculations. Transactions on Mathematical Software 20 (3): 262–281. doi:10.1145/192115.192124. Процитовано 1 лютого 2019. Проігноровано невідомий параметр |citeseerx= (довідка)
Kraft, Dieter (July 1988). A software package for sequential quadratic programming. Oberpfaffenhofen: Institut für Dynamik der Flugsysteme. Процитовано 1 лютого 2019.
KNITRO User Guide: Algorithms

Список літератури

Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (вид. Second revised ed. of translation of 1997 French). Berlin: Springer-Verlag. с. xiv+490. ISBN 978-3-540-35445-1. MR 2265882. doi:10.1007/978-3-540-35447-5.
Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.

зовнішні посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.

[Kraft-2] Kraft, Dieter (Sep 1994). Algorithm 733: TOMP–Fortran modules for optimal control calculations. Transactions on Mathematical Software 20 (3): 262–281. doi:10.1145/192115.192124. Процитовано 1 лютого 2019. Проігноровано невідомий параметр |citeseerx= (довідка)

[3] Kraft, Dieter (July 1988). A software package for sequential quadratic programming. Oberpfaffenhofen: Institut für Dynamik der Flugsysteme. Процитовано 1 лютого 2019.

[4] KNITRO User Guide: Algorithms