Méthodes de points intérieurs

Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre.

Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre

Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit

Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive ; et plus généralement aux problèmes d'optimisation convexe, pourvu que l'on dispose d'une barrière auto-concordante représentant l'ensemble admissible, calculable en temps polynomial (ce n'est pas toujours le cas, car certains problèmes d'optimisation convexe sont NP-difficiles (voir Problème NP-complet)).

Les méthodes de points intérieurs se répartissent en plusieurs familles :

• les méthodes de chemin central
• les méthodes de réduction de potentiel
• les méthodes « affine scaling »

Et pour quasiment chacune de ces approches, on peut considérer une version primale, une version duale, une version primale-duale, et une version auto-duale.

Historique

Les premiers essais de résolutions de problèmes d’optimisations linéaires ont lieu dans les années 40, en même temps que l’introduction de l’Algorithme du simplexe par George Dantzig. Des algorithmes sont alors développés, notamment par von Neumann, Hoffman et Frisch. Cependant, le niveau de complexité mathématique de chaque étape ainsi que des tests décevants par rapport aux performances du simplexe font que cette méthode sera délaissée au profit de la méthode du simplexe.

Il faudra attendre 1984 que Narendra Karmarkar développe le premier algorithme (algorithme de Karmarkar) réellement efficace pour l’optimisation linéaire, qui s’exécute en $O(n^{3.5}L)$ opérations (où $n$ et $L$ le nombre de bits d’entrée de l’algorithme). Karmarkar annonce que son algorithme peut être jusqu’à 40 fois plus rapide que les algorithmes à base de simplexe de l’époque. À l’opposé de l’algorithme du simplexe, cette méthode atteint l’optimum du problème en passant par l’intérieur de l’ensemble des solutions réalisables.

Dans la décennie qui suit, les méthodes par points intérieurs deviennent très populaires comme alternative aux méthodes basées sur l’algorithme du simplexe, et une forme de compétition entre les deux approches émerge. Les méthodes par points intérieurs attirent car elles s’exécutent généralement en moins d’étapes de calcul, et sont plus rapides sur des tests réels que l’état de l’art sur le simplexe.

Description du problème

On a un système $Ax\leq b$ de m inégalités linéaires, et une fonction objectif $f(x)=c^{T}x$ qu’on cherche à maximiser.

Description de l’algorithme

Par méthode du chemin central

On commence par introduire une nouvelle classe de fonction, dépendant d’un paramètre µ : $f_{\mu }(x)=c^{T}x+\mu \times \sum _{i=1}^{m}\ln(b_{i}-a_{i}x)$. On remarque que, quand $\mu =0$, on retrouve la fonction objectif de départ : $f_{0}=f$. La partie suivant de µ dans la formule est appelée fonction barrière. Son rôle est de réduire la valeur de $f_{\mu }$ près des frontières, pour éviter de trop s’en rapprocher.

L’idée générale de cette méthode est assez simple. On commence par choisir une valeur de µ suffisamment grande, un point de départ à l’intérieur des solutions possibles (en général intelligemment choisi, c’est-à-dire pas trop loin du maximum de $f_{\mu }$), et on va ensuite procéder par petits pas :

• On réduit légèrement la valeur de µ
• On trouve une nouvelle approximation du max de $f_{\mu }$. Cette nouvelle approximation peut se faire efficacement en partant de principe que le nouveau maximum reste proche du point de départ
• On répète cette opération jusqu’à ce que µ soit suffisamment petit.

Article connexe

• Pénalisation (optimisation)