comprehension de l'algo lagrangien augmenté
Bonjour tous,
J'essai actuellement de comprendre "en profondeur" un algorithme de minimisation par multiplicateur de Lagrange augmenté et j'aimerai votre aide pour bien comprendre. Je ne vais pour le moment pas vraiment rentrer dans des questions programmation mais plus comprehension algorithmique...
Bases/introduction (plus d'info dans le forum math où j'ai posé une question sur ce genre de questions théoriques)
J'ai une fonction coût "f(x)" que je veux minimiser tout en respectant une contrainte "contrainte=g(x)-valeurVoulue=0".
1) Si on veut minimiser une fonction "f(x)" sous contrainte "contrainte=g(x)-valeurVoulue=0" on peut résoudre le problème par minimisation de
"L(x,\lambda)=f(x)-\lambda.(g(x)-valeurVoulue)"
Néanmoins dans le cas où "L" a une partie concave cette méthode peut parfois échouer numériquement.
2) Du coup, on général on fonctionne par pénalisation et on cherche à minimiser la quantité
"L(x,\mu)=f(x)+\mu.(g(x)-valeurVoulue)^2"
Le soucis est que la méthode peut déplacer la position du minimum initial si la constante "\mu" n'est pas assez grande (et si elle est trop grande ça pose des problèmes numériques de conditionnement).
3) du coup on utilise la méthode des multiplicateur de lagrange augmenté et on cherche donc à minimiser (par rapport à lambda et x)
"L(x,\lambda,\mu)=f(x)+\mu.(g(x)-valeurVoulue)^2-\lambda.(g(x)-valeurVoulue)"
Algo proposé Sur le net j'ai trouvé pas mal de méthodes pour résoudre ce problème (dont notamment sur la page 6 de ce document http://yima.csl.illinois.edu/psfile/Lin09-MP.pdf et wikipedia http://en.wikipedia.org/wiki/Augment...rangian_method ). Le problème est que ce n'est pas assez détaillé et je ne comprends donc pas vraiment l'algorithme et la partie théorique...
Il est proposé souvent par exemple de faire
Code:
1
2
3
4
5
6
| while (convergence)
{
X_k+1=solve[min{L(lambda_k,mu_k,X_k)}];
lambda_k+1=lambda_k-mu_k*contrainte(X_k+1);
mu_k+1=cstePositive*mu_k;
} |
Mais je ne comprends pas la récurrance en lambda et mu .... ? Es ce que vous auriez une idée là dessus svp ?
Même si je ne comprends pas la nécessité de la boucle "while" et ce que représente ici le critère de convergence. J'aurais eu tendance à dire que l'idée de la méthode du lagrangien augmenté serait de chercher à annuler "\mu" au fur et à mesure des itérations afin que la pénalisation ne perturbe pas trop la solution du problème de Lagrange mais quand je lis la page wikipedia je comprends l'inverse....
En gros, je suis un peu pommé avec cette méthode et j'aurais besoin de votre aide svp...
merci beaucoup
