Une synthèse sur les méthodes du point intérieur

Abstract

En 1984, Karmarkar a publié un algorithme de type point intérieur pour la programmation linéaire. Il a affirmé qu'en plus d'être de complexité polynomiale, il est plus efficace que le simplexe surtout pour des problèmes de grande taille. Ainsi une recherche s'est déclenchée dans les méthodes de point intérieur et a donné comme résultat une grande variété d'algorithmes de ce type qui peuvent être classés en quatre catégories de méthodes : méthodes projectives, méthodes affinées, méthodes du potentiel et méthodes de la trajectoire centrale. Dans ce travail, nous allons présenter une synthèse de ces méthodes incluant les derniers développements dans ce domaine.