Méthodes de points intérieurs

famille d’algorithmes de résolution de problèmes d’optimisation / De Wikipedia, l'encyclopédie libre

Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :

Pouvez-vous énumérer les principaux faits et statistiques sur Méthodes de points intérieurs?

Résumez cet article pour un enfant de 10 ans

AFFICHER TOUTES LES QUESTIONS

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 barrière auto-concordante 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)).

Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre.
Simplex-method-3-dimensions.png
Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre
Ellipsoid-method.png
Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit

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

  • les méthodes de chemin central
  • les méthodes de réduction de potentiel
  • les méthodes « affine scaling »

Et pour quasiment chacune de ces approches, on peut considérer une version primale, une version duale, une version primale-duale, et une version auto-duale.

Oops something went wrong: