En optimización matemática , un problema 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 todo 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 se compone de esas limitaciones que están activos en el punto actual ( Nocedal & 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 de la optimización. Por ejemplo, al resolver el problema de programación lineal , el conjunto activo da los hiperplanos que se cruzan 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 da un subconjunto de desigualdades para observar mientras buscamos la solución, lo que reduce la complejidad de la búsqueda.
Métodos de conjuntos activos
En general, un algoritmo de conjunto activo tiene la siguiente estructura:
- Encuentra un punto de partida factible
- repita hasta "lo 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
- fin de repetir
Los métodos que pueden describirse como métodos de conjunto activo incluyen: [1]
- Programación lineal sucesiva (SLP)
- Programación secuencial cuadrática (SQP)
- Programación secuencial lineal-cuadrática (SLQP)
- Método de gradiente reducido (RG)
- Método de gradiente reducido generalizado (GRG)
Referencias
- ^ Nocedal y Wright 2006 , págs. 467–480
Bibliografía
- Murty, KG (1988). Complementariedad lineal, programación lineal y no lineal . Serie Sigma en Matemática Aplicada. 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.