Método de conjunto activo

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

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 todas las x para buscar la solución óptima. Dado un punto en la región factible, una restricción ${\displaystyle x}$

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

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

El conjunto activo es particularmente importante en la teoría de optimización, ya que determina qué restricciones influirán en el resultado final de la optimización. Por ejemplo, al resolver el 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 , como la solución no está necesariamente en uno de los bordes del polígono delimitador, una estimación del conjunto activo nos proporciona un subconjunto de desigualdades para observar mientras buscamos la solución, lo que reduce la complejidad de la búsqueda.

Métodos de conjunto activo

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

búsqueda de restricciones inviables

Fin de repetición

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

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

Actuación

Consideremos el problema de la programación cuadrática convexa linealmente restringida. Bajo supuestos razonables (el problema es factible, el sistema de restricciones es regular en cada punto y el objetivo cuadrático es fuertemente convexo), el método del conjunto activo termina después de un número finito de pasos y produce 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 símplex . Sin embargo, su comportamiento práctico es típicamente mucho mejor. ^{[2] : Sec.9.1}

Referencias

1. Nocedal y Wright 2006, págs. 467–480
2. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .

Bibliografía

• 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 desde el original el 2010-04-01 . Consultado el 2010-04-03 .
• Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2.ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1.