Une famille d'algorithmes d'optimisation qui parcourent l'intérieur de la région réalisable, utilisant des fonctions barrière, des systèmes primaux-duaux ou des stratégies de suivi de chemin pour approcher des solutions optimales sans visiter explicitement les sommets.

Principe

Remplacer les contraintes dures par des termes barrière lisses ou résoudre des systèmes KKT primaux-duaux couplés de sorte que les itérés restent strictement réalisables et suivent un chemin central vers l'optimalité avec des mises à jour de pas contrôlées.

Démonstration

Résoudre un programme quadratique en ajoutant des termes barrière logarithmiques aux contraintes d'inégalité, calculer des pas de Newton pour le système augmenté par la barrière, réduire le paramètre de barrière et répéter jusqu'à satisfaire les conditions d'optimalité.

Mauvaise application

Employer des pas de points intérieurs sans maintenir la condition numérique (mauvaises résolutions linéaires ou contrôle insuffisant de la réduction de la barrière) peut produire des itérés imprécis ou stagner loin d'une solution optimale.

Conséquence

Fournit des garanties de complexité polynomiale pour de nombreux problèmes convexes, produit des approximations primales et duales de haute qualité et s'adapte bien aux grands problèmes creux lorsqu'il est implémenté avec une algèbre linéaire robuste.

Inversion

Contraste avec les méthodes combinatoires suivant la frontière (par exemple la simplex) : les méthodes de points intérieurs évitent les changements explicites de base et substituent aux mouvements combinatoires des résolutions non linéaires continues.

Limite

Principalement applicables aux programmes convexes (linéaires, quadratiques, coniques) ; les problèmes non convexes ne reçoivent que des solutions locales et exigent des stratégies de globalisation ou des heuristiques.

Tension sémantique

Tension avec la perspective simplex sur la parcimonie et le warm-start : le simplex offre des warm starts et une parcimonie d'extrémum tandis que les points intérieurs favorisent un progrès lisse et des itérés souvent plus denses.

Synthèse

Les méthodes de points intérieurs recadrent l'optimisation convexe comme un suivi continu de chemin à l'intérieur de l'ensemble réalisable : maintenir la stricte réalisabilité via barrière ou conditions primales-duales et avancer par mises à jour de type Newton vers l'optimalité.