méthodes de points intérieurs

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 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 « affine scaling » (optimisation sur des ellipsoïdes) ; * les méthodes de réduction du potentiel (notion de barrière, chemin central, relaxation).