Methode du point interieur

Méthode du point intérieur

Les méthodes de point intérieur forment une classe d'algorithmes qui permettent de résoudre des problèmes d'optimisation convexe (linéaire ou non).

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

• La méthode « affine scaling » (optimisation sur des ellipsoïdes )
• La méthode de réduction du potentiel (notion de barrière , chemin central , relaxation) (La méthode du chemin central est le représentant le plus important de cette famille)

Historique

Toutes ces méthodes trouvent leur origine (historique) dans les travaux d’un élève de Kolmogorov : Dikin. C’est, en effet, à Dikin que l’on doit la méthode des ellipsoïdes sur laquelle se fondent plus ou moins toutes les méthodes de points intérieurs. Nemirovsky, Yudin, Shor développent, en 1972, la méthode des ellipsoïdes pour des problèmes d'optimisation (non linéaire) convexe. En 1979, Khachiyan démontre que la méthode des ellipsoïdes, appliquée à la PL a une complexité, dans le pire des cas, polynomiale. Cependant, l'algorithme qu'il propose est beaucoup plus lent que le simplexe. Cette approche, qui s'étend de façon très élégante à des problèmes non linéaires convexes peut être considéré comme l'idée germinale des méthodes de points intérieurs développées par la suite.

Les algorithmes développés par la suite ont été inspiré par l'Algorithme de Karmarkar, développé en 1984 par Narendra Kamarkar pour la programmation linéaire. L'idée de base de la méthode est d'utiliser des fonctions barrières pour décrire l'ensemble des solutions qui est convexe par définition du problème. A 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.

Ce document provient de « M%C3%A9thode du point int%C3%A9rieur ».