Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthodes de points intérieurs
Résumé
vignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre.
vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre
vignette|Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit
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)).
Les méthodes de points intérieurs se répartissent en plusieurs familles :
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.
Les premiers essais de résolutions de problèmes d’optimisations linéaires ont lieu dans les années 40, en même temps que l’introduction de l’Algorithme du simplexe par George Dantzig. Des algorithmes sont alors développés, notamment par von Neumann, Hoffman et Frisch. Cependant, le niveau de complexité mathématique de chaque étape, ainsi des tests décevants par rapport aux performances du simplexe font que cette méthode sera délaissée au profit de la méthode du simplexe.
Il faudra attendre 1984 que Narendra Karmarkar développe le premier algorithme (algorithme de Karmarkar) réellement efficace pour l’optimisation linéaire, qui s’exécute en opérations (où et le nombre de bits d’entrée de l’algorithme). Karmarkar annonce que son algorithme peut être jusqu’à 40 fois plus rapide que les algorithmes à base de simplexe de l’époque.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.