Método de conjunto activo

En optimización matemática , el método del conjunto activo es un algoritmo que se utiliza para identificar las restricciones activas en un conjunto de restricciones de desigualdad . Estas restricciones activas se expresan entonces como restricciones de igualdad, transformando así un problema con restricciones de desigualdad en un subproblema más sencillo con restricciones de igualdad.

Un problema de optimización se define utilizando una función objetivo para minimizar o maximizar, y un conjunto de restricciones.

${\displaystyle g_{1}(x)\geq 0,\dots,g_{k}(x)\geq 0}$

que definen la región factible , es decir, el conjunto de todos los x para buscar la solución óptima. Dado un punto${\displaystyle x}$en la región factible, una restricción

${\displaystyle g_{i}(x)\geq 0}$

se llama activo en${\displaystyle x_{0}}$si${\displaystyle g_{i}(x_{0})=0}$y inactivo en${\displaystyle x_{0}}$si${\displaystyle g_{i}(x_{0})>0.}$Las restricciones de igualdad siempre están activas. El conjunto activo en${\displaystyle x_{0}}$está compuesto por esas restricciones${\displaystyle g_{i}(x_{0})}$que están activas en el momento actual ( Nocedal y Wright 2006 , p. 308) . 

El conjunto activo es particularmente importante en la teoría de la optimización, ya que determina qué restricciones influirán en el resultado final. Por ejemplo, al resolver un problema de programación lineal , el conjunto activo proporciona los hiperplanos que se intersecan en el punto de solución. En la programación cuadrática , dado que la solución no necesariamente se encuentra en uno de los bordes del polígono delimitador, una estimación del conjunto activo nos proporciona un subconjunto de desigualdades a considerar durante la búsqueda de la solución, lo que reduce la complejidad de la misma.

Los métodos de conjunto activo, que recorren los bordes del conjunto factible, contrastan con los métodos de punto interior , que intentan permanecer siempre dentro del conjunto factible.

En general, un algoritmo de conjunto activo tiene la siguiente estructura:

Encuentra un punto de partida factible

repetir hasta que sea "suficientemente óptimo"

resolver el problema de igualdad definido por el conjunto activo (aproximadamente)

Calcular los multiplicadores de Lagrange del conjunto activo.

eliminar un subconjunto de las restricciones con multiplicadores de Lagrange negativos

buscar restricciones inviables entre las restricciones inactivas y agregarlas al problema.

fin de repetición

La razón de esto es que, cerca del óptimo, generalmente solo un pequeño número de todas las restricciones son vinculantes y el paso de resolución suele tomar un tiempo superlineal con respecto a la cantidad de restricciones. Por lo tanto, la resolución repetida de un problema de igualdad en serie, que elimina las restricciones que no se violan al mejorar pero que obstaculizan la mejora (multiplicadores de Lagrange negativos) y agrega aquellas restricciones que la solución actual viola, puede converger hacia la solución verdadera. Los óptimos del problema anterior a menudo pueden proporcionar una estimación inicial en caso de que el solucionador del problema de igualdad en serie necesite un valor inicial.

Los métodos que pueden describirse como métodos de conjunto activo incluyen: ^{[ 1 ]}

• Programación lineal sucesiva (PLS)
• Programación cuadrática secuencial (PQS)
• Programación lineal-cuadrática secuencial (SLQP)
• Método de gradiente reducido (RG)
• Método de gradiente reducido generalizado (GRG)

Consideremos el problema de programación cuadrática convexa con restricciones lineales. Bajo supuestos razonables (el problema es factible, el sistema de restricciones es regular en cada punto y la función objetivo cuadrática es fuertemente convexa), el método del conjunto activo finaliza después de un número finito de pasos y proporciona una solución global al problema. Teóricamente, el método del conjunto activo puede realizar un número de iteraciones exponencial en m , como el método simplex . Sin embargo, su comportamiento práctico suele ser mucho mejor. ^{[ 2 ] : Sec.9.1}

• Murty, KG (1988). Complementariedad lineal, programación lineal y no lineal . Serie Sigma en Matemáticas Aplicadas. Vol.  3. Berlín: Heldermann Verlag. pp.  xlviii+629 pp. ISBN 3-88538-403-5. MR 0949214 . Archivado del original el 1 de abril de 2010 . Consultado el 3 de abril de 2010 . 
• Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2.ª  ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1.