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.
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
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).
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.
En general, un algoritmo de conjunto activo tiene la siguiente estructura:
Los métodos que pueden describirse como métodos de conjunto activo incluyen: [1]
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