Programación lineal-cuadrática secuencial

La programación lineal-cuadrática secuencial ( SLQP ) es un método iterativo para problemas de optimización no lineal donde la función objetivo y las restricciones son dos veces continuamente diferenciables . De forma similar a la programación cuadrática secuencial (SQP), la SLQP procede resolviendo una secuencia de subproblemas de optimización. La diferencia entre ambos enfoques es que:

En SQP, cada subproblema es un programa cuadrático , con un modelo cuadrático del objetivo sujeto a una linealización de las restricciones.
En SLQP, se resuelven dos subproblemas en cada paso: un programa lineal (LP) utilizado para determinar un conjunto activo , seguido de un programa cuadrático con restricciones de igualdad (EQP) utilizado para calcular el paso total.

Esta descomposición hace que SLQP sea adecuado para problemas de optimización a gran escala, para los cuales existen solucionadores LP y EQP eficientes, siendo estos problemas más fáciles de escalar que los programas cuadráticos completos.

Puede considerarse relacionado con los métodos cuasi-Newton , pero distinto de ellos .

Conceptos básicos de algoritmos

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

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

El lagrangiano para este problema es ^{[ 1 ]}

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

dónde $\lambda \geq 0$ y $\sigma$ son multiplicadores de Lagrange .

fase LP

En la fase LP del SLQP, se resuelve el siguiente programa lineal:

{\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}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{array}}

Dejar ${\cal {A}}_{k}$ denotemos el conjunto activo en el óptimo $d_{\text{LP}}^{*}$ de este problema, es decir, el conjunto de restricciones que son iguales a cero en $d_{\text{LP}}^{*}$ Denotemos por $b_{{\cal {A}}_{k}}$ y $c_{{\cal {A}}_{k}}$ los subvectores de $b$ y $c$ correspondientes a elementos de ${\cal {A}}_{k}$ .

Fase EQP

En la fase EQP de SLQP, la dirección de búsqueda $d_{k}$ El resultado del paso se obtiene resolviendo el siguiente programa cuadrático con restricciones de igualdad:

{\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_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}

Tenga en cuenta que el término $f(x_{k})$ En las funciones objetivo anteriores, se puede omitir para los problemas de minimización, ya que es constante.

Véase también

Notas

↑ Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica . Springer. ISBN 0-387-30303-0.

Referencias

Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica . Springer. ISBN 0-387-30303-0.

[1] Jorge Nocedal y Stephen J. Wright (2006). Optimización numérica . Springer. ISBN 0-387-30303-0.

[ 1 ]