Programación secuencial lineal-cuadrática - Sequential linear-quadratic programming

La programación secuencial lineal-cuadrática ( SLQP ) es un método iterativo para problemas de optimización no lineal donde la función objetivo y las restricciones son dos veces diferenciables de forma continua . De manera similar a la programación cuadrática secuencial (SQP), SLQP procede resolviendo una secuencia de subproblemas de optimización. La diferencia entre los dos 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 se encuentran disponibles solucionadores LP y EQP eficientes, siendo estos problemas más fáciles de escalar que los programas cuadráticos completos.

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 {st}} & b (x) \ geq 0 \\ & c (x) = 0. \ end {array}}}$

El lagrangiano para este problema es

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

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

Fase LP

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

${\ Displaystyle {\ 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 {matriz}}}$

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

Fase EQP

En la fase EQP de SLQP, la dirección de búsqueda del paso se obtiene resolviendo el siguiente programa cuadrático: ${\ 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 _ {{\ cal {A}} _ {k}} (x_ {k}) + \ nabla b _ {{\ cal {A}} _ {k}} (x_ {k}) ^ {T} d \ geq 0 \\ & c _ {{\ cal {A}} _ {k}} (x_ {k}) + \ nabla c _ {{\ cal {A}} _ {k}} (x_ {k}) ^ { T} d = 0. \ End {matriz}}}$

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

Ver también

• Método de Newton
• Método secante
• Programación lineal secuencial
• Programación cuadrática secuencial

Notas

Referencias

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