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:
El lagrangiano para este problema es [1]
dónde y son 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 solución al subproblema de programación cuadrática
Tenga en cuenta que el término en la expresión anterior puede quedar fuera para el problema de minimización, ya que es constante bajo el operador.
Aproximaciones alternativas
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. [2] [3]
- LabVIEW
- KNITRO [4] (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
- ^ Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica . Saltador. ISBN 978-0-387-30303-1.
- ^ Kraft, Dieter (septiembre de 1994). "Algoritmo 733: Módulos TOMP – Fortran para cálculos de control óptimos" . Transacciones ACM en software matemático . 20 (3): 262-281. CiteSeerX 10.1.1.512.2567 . doi : 10.1145 / 192115.192124 . S2CID 16077051 . Consultado el 1 de febrero de 2019 .
- ^ Kraft, Dieter (julio de 1988). "Un paquete de software para programación cuadrática secuencial" . Informe técnico DFVLR-FB 88-28 . Oberpfaffenhofen: Institut für Dynamik der Flugsysteme . Consultado el 1 de febrero de 2019 .
- ^ Guía del usuario de KNITRO: algoritmos
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