Programación secuencial cuadrática - Sequential quadratic programming

La programación cuadrática secuencial ( SQP ) es un método iterativo para la optimización no lineal restringida . Los métodos SQP se utilizan en problemas matemáticos para los que la función objetivo y las restricciones son dos veces diferenciables de forma continua .

Los métodos SQP resuelven una secuencia de subproblemas de optimización, cada uno de los cuales optimiza un modelo cuadrático del objetivo sujeto a una linealización de las restricciones. Si el problema no tiene restricciones, entonces el método se reduce al método de Newton para encontrar un punto donde el gradiente del objetivo desaparece. Si el problema solo tiene restricciones de igualdad, entonces el método es equivalente a aplicar el método de Newton a las condiciones de optimalidad de primer orden, o condiciones de Karush-Kuhn-Tucker , del problema.

Conceptos básicos de algoritmos

Considere un problema de programación no lineal de la forma:

${\ displaystyle {\ begin {array} {rl} \ min \ limits _ {x} & f (x) \\ {\ mbox {sujeto a}} & b (x) \ geq 0 \\ & c (x) = 0. \ end {matriz}}}$

El lagrangiano para este problema es

${\ Displaystyle {\ mathcal {L}} (x, \ lambda, \ sigma) = f (x) - \ lambda b (x) - \ sigma c (x),}$

donde y son los multiplicadores de Lagrange . En una iteración , un algoritmo básico de programación cuadrática secuencial define una dirección de búsqueda apropiada como una solución al subproblema de programación cuadrática${\ 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 {matriz}}}$

Tenga en cuenta que el término en la expresión anterior puede omitirse para el problema de minimización, ya que es constante bajo el operador. ${\ Displaystyle f (x_ {k})}$${\ Displaystyle \ min \ límites _ {d}}$

Aproximaciones alternativas

• Programación lineal secuencial
• Programación secuencial lineal-cuadrática
• Método lagrangiano aumentado

Implementaciones

Los métodos SQP se han implementado en entornos numéricos bien conocidos como MATLAB y GNU Octave . También existen numerosas bibliotecas de software, incluidas las de código abierto:

• SciPy (estándar de facto para Python científico) tiene el solucionador scipy.optimize.minimize (método = 'SLSQP').
• NLopt ( implementación de C / C ++, con numerosas interfaces que incluyen Julia, Python, R, MATLAB / Octave), implementado por Dieter Kraft como parte de un paquete para un control óptimo y modificado por SG Johnson.
• LabVIEW
• KNITRO (C, C ++, C #, Java, Python, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Java)

Ver también

• Algoritmo de Josephy-Newton
• Método de Newton
• Método secante

Notas

Referencias

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: Aspectos teóricos y prácticos . Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. págs. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN   978-3-540-35445-1 . Señor   2265882 .
• Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica . Saltador. ISBN   978-0-387-30303-1 .

enlaces externos

• Programación secuencial cuadrática en la guía NEOS

Este artículo relacionado con las matemáticas aplicadas es un resumen . Puedes ayudar a Wikipedia expandiéndolo . v t mi