comprehension de l'algo lagrangien augmenté

[invite9c7554e3]

Bonjour tous,

J'essai de comprendre en ce moment "en profondeur" l'algorithme de minimisation par multiplicateur de Lagrange augmenté

et j'aimerai votre aide pour bien comprendre. (ici je parle dans un contexte de résolution par méthode numérique)

Bases/introduction

J'ai une fonction coût que je veux minimiser tout en respectant une contrainte .

1) Si on veut minimiser une fonction sous contrainte on peut résoudre le problème par minimisation de



Néanmoins il est possible d'avoir une concavité dans la fonction ce qui peut faire échouer cette méthode numérique dans certains cas.

2) Du coup, on général on fonctionne par pénalisation et on cherche à minimiser la quantité



Le soucis est que la méthode peut déplacer la position du minimum initial si la constante 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)



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

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=mu_k
}

ou

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 ?

Pour moi, l'idée de la méthode du lagrangien augmenté serait de chercher à annuler 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
-----

[invite9c7554e3]

pas une petite idée les amis ?