« Méthodes de points intérieurs » : différence entre les versions
m fix typo and add link |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
Les '''méthodes de points intérieurs''' forment une classe d’algorithmes qui permettent de résoudre des problèmes d’[[Optimisation (mathématiques)|optimisation mathématique]]. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'[[optimisation linéaire]], [[optimisation quadratique|quadratique]] convexe, [[optimisation SDP|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''' forment une classe d’algorithmes qui permettent de résoudre des problèmes d’[[Optimisation (mathématiques)|optimisation mathématique]]. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'[[optimisation linéaire]], [[optimisation quadratique|quadratique]] convexe, [[optimisation SDP|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 points intérieurs se répartissent en plusieurs familles<ref>{{Ouvrage|prénom1=Bernd|nom1=Gärtner|titre=Understanding and using linear programming|éditeur=Springer|date=2007|isbn=978-3-540-30717-4|isbn2=3-540-30717-6|isbn3=3-540-30697-8|oclc=184984491|lire en ligne=https://www.worldcat.org/oclc/184984491|consulté le=2023-02-08}}</ref> : |
||
* les méthodes |
* les méthodes de chemin central |
||
* les méthodes de réduction |
* les méthodes de réduction de potentiel |
||
* les méthodes « affine scaling » |
|||
<!-- ; La méthode du chemin central est le représentant le plus important de cette famille.--> |
|||
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.<!-- ; La méthode du chemin central est le représentant le plus important de cette famille.--> |
|||
== Historique == |
== Historique == |
||
| Ligne 16 : | Ligne 17 : | ||
* [[Pénalisation (optimisation)]] |
* [[Pénalisation (optimisation)]] |
||
== Références == |
|||
<references /> |
|||
{{Portail|informatique théorique}} |
{{Portail|informatique théorique}} |
||
Version du 8 février 2023 à 10:32
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[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.
Historique
Toutes ces méthodes trouvent leur origine (historique) dans les travaux d’un élève du mathématicien soviétique Andreï Kolmogorov : Dikin. C’est, en effet, à Dikin que l’on doit la méthode des ellipsoïdes sur laquelle se fondent plus ou moins toutes les méthodes de points intérieurs. Arkadi Nemirovski, David B. Yudin, Shor développent, en 1972, la méthode des ellipsoïdes pour des problèmes d’optimisation (non linéaire) convexe. En 1979, Leonid Khatchian démontre que la méthode des ellipsoïdes, appliquée à la programmation linéaire, a une complexité, dans le pire des cas, polynomiale. Cependant, l’algorithme qu’il propose est beaucoup plus lent que le simplexe. Cette approche, qui s’étend de façon très élégante à des problèmes non linéaires convexes peut être considérée comme l’idée germinale des méthodes de points intérieurs développées par la suite.
Les algorithmes développés par la suite ont été inspirés par l’Algorithme de Karmarkar, développé en 1984 par Narendra Karmarkar pour l'optimisation 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. À 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.
Article connexe
Références
- Bernd Gärtner, Understanding and using linear programming, Springer, (ISBN 978-3-540-30717-4, 3-540-30717-6 et 3-540-30697-8, OCLC 184984491, lire en ligne)
