Mètode del conjunt actiu

En optimització matemàtica, es defineix un problema mitjançant una funció objectiu que s'ha de minimitzar o maximitzar, i un conjunt de restriccions escrites com a inequacions

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

que defineixen la regió factible, és a dir, el conjunt de totes les x que compleixen les restriccions i de què es trobarà la solució òptima. Donat un punt $x$ en la regió factible, una restricció

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

és anomenada activa en $x$ si $g_{i}(x)=0$, i inactiva en $x$ si $g_{i}(x)>0.$ Les restriccions d'igualtat són sempre actives. El conjunt actiu en $x$ està compost per aquelles restriccions $g_{i}(x)$ que són actives en el punt actual (Nocedal & Wright 2006, p. 308).

El conjunt actiu és particularment important en teoria de l'optimització, ja que determina quines restriccions influenciaran el resultat final de l'optimització. Per exemple, quan es resol un problema de programació lineal, el conjunt actiu dona els hiperplans que intersecten en la solució. En programació quadràtica, com que la solució no és necessàriament en un dels eixos del polígon frontera, una estimació del conjunt actiu dona un subconjunt d'inequacions a tenir en compte mentre es busca la solució, que redueix la complexitat de la cerca.

Mètodes del conjunt actiu

En general un algorisme del conjunt actiu té la següent estructura:

Trobar un punt d'inici factible (és a dir, que compleixi les restriccions)

repetir fins a obtenir "prou optimalitat"

resoldre el problema d'equacions definit pel conjunt actiu (aproximadament)

calcular els multiplicadors de Lagrange del conjunt actiu

relaxar algunes aquelles restriccions que tinguin multiplicadors de Lagrange negatius

trobar les restriccions que no són factibles

sortir del bucle

Entre els mètodes del conjunt actiu, hi ha:

• Programació lineal successiva (SLP, de l'anglès Successive Linear Programming)
• Programació quadràtica successiva (SQP, de l'anglès Sequential Quadratic Programming)
• Programació lineal-quadràtica seqüencial (SLQP, de l'anglès Sequential Linear-Quadratic Programming)
• Mètode del gradient reduït (RG, de l'anglès Reduced Gradient)
• Mètode generalitzat del gradient reduït (GRG, de l'anglès Generalized Reduced Gradient)

Bibliografia

• Murty, K. G.. Linear complementarity, linear and nonlinear programming. 3. Berlin: Heldermann Verlag, 1988, p. xlviii+629 pp (Sigma Series in Applied Mathematics). ISBN 3-88538-403-5.  Arxivat 2010-04-01 a Wayback Machine.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. 2nd. Berlin, New York: Springer-Verlag, 2006. ISBN 978-0-387-30303-1.