Método de conjunto activo

En optimización matemática , el método de conjunto activo es un algoritmo utilizado 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 más simple restringido por 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 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 se compone de aquellas restricciones que están activas en el punto actual (Nocedal y Wright 2006, p. 308). ${\displaystyle x_{0}}$ ${\displaystyle g_{i}(x_{0})=0}$ ${\displaystyle x}$ ${\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 la 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 cruzan en el punto de solución. En 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 da 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:

Encuentre 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

finalizar repetir

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

Considere 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 todos los puntos 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 exponenciales en m , como el método simplex . Sin embargo, su comportamiento práctico suele ser mucho mejor. ^{[2] : Sección 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ática Aplicada. vol. 3. Berlín: Heldermann Verlag. págs. xlviii+629 págs. ISBN 3-88538-403-5. SEÑOR  0949214. Archivado desde el 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.