Vés al contingut

Mètode del conjunt actiu

De la Viquipèdia, l'enciclopèdia lliure

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

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 en la regió factible, una restricció

és anomenada activa en si , i inactiva en si Les restriccions d'igualtat són sempre actives. El conjunt actiu en està compost per aquelles restriccions 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

[modifica]

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:[1]

  • 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)

Referències

[modifica]
  1. Nocedal & Wright 2006, pàg. 467–480

Bibliografia

[modifica]