Méthode du point intérieur

Un article de Wikipédia, l'encyclopédie libre.

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).

Ces algorithmes ont été inspirés par l'algorithme de Kamarkar, 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. Ces fonctions barrières sont des fonctions continues dont la valeur croît (très rapidement) vers l'infini lorsqu'on s'approche de la frontière de l'ensemble des solutions réalisable, ce qui empêche l'algorithme de se diriger vers des solutions non réalisables. Ainsi, à 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.

v · d · m Articles en rapport avec la convexité
Géométrie convexe	Article principal : Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyèdrale • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Programmation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Article principal : Fonction convexe Outils et résultats fondamentaux : Inégalité de Jensen Optimisation convexe : Conditions de Kuhn-Tucker • Méthode du point intérieur
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski