Compléments et autres algorithmes
101
5.1.2. Méthodes de chemin intérieur
La dénomination de ce type de méthode n'est pas très explicite, car avec les méthodes
précédentes, on a affaire clairement à un cheminement intérieur. Leur réservant
cependant ce terme, voyons les principes sur lesquelles elles se fondent (elles
aboutissent d'ailleurs in fine à des formalisations voisines de celles que l'on a vues).
L'idée est la suivante : si nous reprenons notre petit exemple, on peut penser se
débarrasser des contraintes embêtantes que sont
. Pour les autres contraintes (en
l'occurrence une seule dans notre petit exemple), elles sont transformées en égalités
grâce aux variables d'écart (ici ). Compliquons la formule de la fonction économique
de la façon suivante :
Où µ est un nombre très petit. On s'interdit ainsi d'avoir des variables, principales ou
d'écart, qui soient négatives ou nulles (on a introduit des fonctions « barrières »). µ étant
très petit, on traite à peu près la même fonctionnelle. On peut s'inquiéter du fait que l'on
n'atteint jamais un
, ce qui se produit à l'optimum pour un certain nombre d'entre
eux, mais justement, comme précédemment, l'ambition de ces méthodes est uniquement
d'approcher la solution à un seuil près, faible, et donc cela ne pose pas de problème non
plus.
Mais on se trouve alors confronté au problème classique d'optimisation d'une fonction de
n variables soumises à m contraintes d'égalité. (on n'a plus d'inégalités) et on peut
appliquer le dispositif des multiplicateurs de Lagrange. Pour l'exemple, si le
multiplicateur est , on a le lagrangien suivant :
Et les conditions du premier ordre donnent :
Inconnues : ,
Evidemment, même sur cet exemple très simple, la résolution de ce système d'équations,
non linéaire (où les inconnues sont les variables), n'est pas évident (cela n'est pas pour
surprendre; dans le cas contraire, on n'aurait pas inventé l'algorithme du simplexe et on
ne se serait pas intéressé non plus aux programmes linéaires).
Ecrivons le même système d'équations dans le cas général, mais en l'enrichissant par un
calcul analogue sur le dual (l'algorithme correspondant porte le nom de primal-dual
intérieur). Sous forme matricielle, prenons les notations suivantes : A matrice des
contraintes du primal sous forme canonique, X et Y vecteurs colonnes des variables
principales du primal et du dual, X e et Y e vecteurs colonnes des variables d'écart, b
101
5.1.2. Méthodes de chemin intérieur
La dénomination de ce type de méthode n'est pas très explicite, car avec les méthodes
précédentes, on a affaire clairement à un cheminement intérieur. Leur réservant
cependant ce terme, voyons les principes sur lesquelles elles se fondent (elles
aboutissent d'ailleurs in fine à des formalisations voisines de celles que l'on a vues).
L'idée est la suivante : si nous reprenons notre petit exemple, on peut penser se
débarrasser des contraintes embêtantes que sont
. Pour les autres contraintes (en
l'occurrence une seule dans notre petit exemple), elles sont transformées en égalités
grâce aux variables d'écart (ici ). Compliquons la formule de la fonction économique
de la façon suivante :
Où µ est un nombre très petit. On s'interdit ainsi d'avoir des variables, principales ou
d'écart, qui soient négatives ou nulles (on a introduit des fonctions « barrières »). µ étant
très petit, on traite à peu près la même fonctionnelle. On peut s'inquiéter du fait que l'on
n'atteint jamais un
, ce qui se produit à l'optimum pour un certain nombre d'entre
eux, mais justement, comme précédemment, l'ambition de ces méthodes est uniquement
d'approcher la solution à un seuil près, faible, et donc cela ne pose pas de problème non
plus.
Mais on se trouve alors confronté au problème classique d'optimisation d'une fonction de
n variables soumises à m contraintes d'égalité. (on n'a plus d'inégalités) et on peut
appliquer le dispositif des multiplicateurs de Lagrange. Pour l'exemple, si le
multiplicateur est , on a le lagrangien suivant :
Et les conditions du premier ordre donnent :
Inconnues : ,
Evidemment, même sur cet exemple très simple, la résolution de ce système d'équations,
non linéaire (où les inconnues sont les variables), n'est pas évident (cela n'est pas pour
surprendre; dans le cas contraire, on n'aurait pas inventé l'algorithme du simplexe et on
ne se serait pas intéressé non plus aux programmes linéaires).
Ecrivons le même système d'équations dans le cas général, mais en l'enrichissant par un
calcul analogue sur le dual (l'algorithme correspondant porte le nom de primal-dual
intérieur). Sous forme matricielle, prenons les notations suivantes : A matrice des
contraintes du primal sous forme canonique, X et Y vecteurs colonnes des variables
principales du primal et du dual, X e et Y e vecteurs colonnes des variables d'écart, b