Programación cuadrática secuencial

Algoritmo de optimización

La programación cuadrática secuencial ( SQP ) es un método iterativo para la optimización no lineal restringida que puede considerarse un método cuasi-Newton . Los métodos SQP se utilizan en problemas matemáticos para los cuales la función objetivo y las restricciones son dos veces continuamente diferenciables , pero no necesariamente convexas.

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 se anule. 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.

Fundamentos de algoritmos

Esquema general que ilustra el algoritmo SQP básico

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

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{subject to}}&h(x)\geq 0\\&g(x)=0.\end{array}}}$

El lagrangiano para este problema es ^[1]

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)+\lambda h(x)+\sigma g(x),}$

donde y son multiplicadores de Lagrange . ${\displaystyle \lambda }$ ${\displaystyle \sigma }$

El método estándar de Newton busca la solución iterando la siguiente ecuación, donde denota la matriz hessiana : ${\displaystyle \nabla {\mathcal {L}}(x,\lambda ,\sigma )=0}$ ${\displaystyle \nabla _{xx}^{2}}$

${\displaystyle {\begin{bmatrix}x_{k+1}\\\lambda _{k+1}\\\sigma _{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\lambda _{k}\\\sigma _{k}\end{bmatrix}}-\underbrace {{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}&\nabla h&\nabla g\\\nabla h^{T}&0&0\\\nabla g^{T}&0&0\end{bmatrix}}^{-1}} _{\nabla ^{2}{\mathcal {L}}}\underbrace {\begin{bmatrix}\nabla f+\lambda _{k}\nabla h+\sigma _{k}\nabla g\\h\\g\end{bmatrix}} _{\nabla {\mathcal {L}}}}$.

Sin embargo, debido a que la matriz es generalmente singular (y por lo tanto no invertible ), el paso de Newton no se puede calcular directamente. En cambio, el algoritmo básico de programación cuadrática secuencial define una dirección de búsqueda apropiada en una iteración , como una solución al subproblema de programación cuadrática. ${\displaystyle \nabla ^{2}{\mathcal {L}}}$ ${\displaystyle d_{k}=\left(\nabla _{xx}^{2}{\mathcal {L}}\right)^{-1}\nabla {\mathcal {L}}}$ ${\displaystyle d_{k}}$ ${\displaystyle (x_{k},\lambda _{k},\sigma _{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 {s.t.} &h(x_{k})+\nabla h(x_{k})^{T}d\geq 0\\&g(x_{k})+\nabla g(x_{k})^{T}d=0.\end{array}}}$

donde la forma cuadrática se forma con el hessiano del lagrangiano. Nótese 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 \limits _{d}}$

En conjunto, el algoritmo SQP comienza eligiendo primero la iteración inicial , luego calculando y . Luego, se construye y resuelve el subproblema QP para encontrar la dirección del paso de Newton que se utiliza para actualizar la iteración del problema principal utilizando . Este proceso se repite hasta que el problema principal satisface una prueba de convergencia. ${\displaystyle (x_{0},\lambda _{0},\sigma _{0})}$ ${\displaystyle \nabla ^{2}{\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})}$ ${\displaystyle \nabla {\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})}$ ${\displaystyle d_{0}}$ ${\displaystyle \left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+d_{k}}$ ${\displaystyle k=0,1,2,\ldots }$

Implementaciones prácticas

Las implementaciones prácticas del algoritmo SQP son significativamente más complejas que su versión básica descrita anteriormente. Para adaptar el algoritmo SQP a aplicaciones del mundo real, se deben abordar los siguientes desafíos:

• La posibilidad de un subproblema QP inviable.
• Subproblema QP que produce un paso incorrecto: uno que no logra reducir el objetivo o aumenta la violación de las restricciones.
• Ruptura de iteraciones debido a una desviación significativa del objetivo/restricciones de sus modelos cuadráticos/lineales.

Para superar estos desafíos, normalmente se emplean diversas estrategias:

• Uso de funciones de mérito, que evalúan el progreso hacia una solución restringida, o métodos de filtro.
• Confíe en los métodos de búsqueda de regiones o líneas para gestionar las desviaciones entre el modelo cuadrático y el objetivo real.
• Fases especiales de restauración de la viabilidad para manejar subproblemas inviables, o el uso de subproblemas penalizados por L1 para disminuir gradualmente la inviabilidad

Estas estrategias se pueden combinar de numerosas maneras, dando como resultado una gama diversa de métodos SQP.

Enfoques alternativos

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

Implementaciones

Los métodos SQP se han implementado en entornos numéricos 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(method='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]}
• Solucionador ALGLIB SQP (C++, C#, Java, API de Python)

y comercial

• LabVIEW
• KNITRO ^[4] (C, C++, C#, Java, Python, Julia, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• Lenguaje de programación de calidad de lenguaje natural (Fortran)
• MATLAB
• Suan Shu (Java)

Véase también

• El método de Newton
• Método de la secante
• Control predictivo de modelos

Notas

1. Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica. Springer. ISBN 978-0-387-30303-1.
2. Kraft, Dieter (septiembre de 1994). "Algoritmo 733: módulos TOMP–Fortran para cálculos de control óptimos". ACM Transactions on Mathematical Software . 20 (3): 262–281. CiteSeerX 10.1.1.512.2567 . doi :10.1145/192115.192124. S2CID  16077051 . Consultado el 1 de febrero de 2019 . 
3. "Algoritmos NLopt: SLSQP". Leer la documentación . Julio de 1988. Consultado el 1 de febrero de 2019 .
4. 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. pp. 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. Springer. ISBN 978-0-387-30303-1.

Enlaces externos

• Guía de programación cuadrática secuencial en NEOS