Méthode du point intérieur

Méthode du point intérieur

Les méthodes de point intérieur forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation convexe (linéaire ou non).

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

  • La méthode « affine scaling » (optimisation sur des ellipsoïdes )
  • La méthode de réduction du potentiel (notion de barrière, chemin central, relaxation). La méthode du chemin central est le représentant le plus important de cette famille.

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 Khachiyan démontre que la méthode des ellipsoïdes, appliquée à la PL 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é 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 Kamarkar 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. A 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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode du point intérieur de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Methode du point interieur — Méthode du point intérieur Les méthodes de point intérieur forment une classe d algorithmes qui permettent de résoudre des problèmes d optimisation convexe (linéaire ou non). Les méthodes de points intérieurs se répartissent en plusieurs familles …   Wikipédia en Français

  • Méthode Du Point Intérieur — Les méthodes de point intérieur forment une classe d algorithmes qui permettent de résoudre des problèmes d optimisation convexe (linéaire ou non). Les méthodes de points intérieurs se répartissent en plusieurs familles: La méthode « affine… …   Wikipédia en Français

  • MÉTHODE — Le mot «méthode», d’origine grecque, signifie chemin: celui, tracé à l’avance, qui conduit à un résultat. La méthode ou bien se rapporte à la meilleure façon de conduire un raisonnement, ou bien est un programme de recherche (Aristote: Essayer… …   Encyclopédie Universelle

  • Adherence, interieur et frontiere d'un convexe — Adhérence, intérieur et frontière d un convexe Dans le cas particulier de parties convexes d un espace vectoriel topologique, les opérateurs topologiques élémentaires d adhérence ou intérieur préservent la convexité. Sous une réserve technique… …   Wikipédia en Français

  • Methode Ziggourat — Méthode Ziggourat La méthode Ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniformes. Il s agit d une méthode de rejet et pour être choisie pour simuler une variable aléatoire ayant une densité strictement monotone …   Wikipédia en Français

  • Methode des elements finis — Méthode des éléments finis Pour les articles homonymes, voir Élément. Solution bidimensionnelle d une équation magnétostatique obtenue par éléments fin …   Wikipédia en Français

  • Méthode Des Éléments Finis — Pour les articles homonymes, voir Élément. Solution bidimensionnelle d une équation magnétostatique obtenue par éléments fin …   Wikipédia en Français

  • Methode bille-anneau — Point de ramollissement bille et anneau Le point de ramollissement par la méthode bille et anneau (ou TBA, température bille anneau) concerne typiquement les résines sous forme solide et les matériaux thermoplastiques, plus précisément ceux… …   Wikipédia en Français

  • Methode bille et anneau — Point de ramollissement bille et anneau Le point de ramollissement par la méthode bille et anneau (ou TBA, température bille anneau) concerne typiquement les résines sous forme solide et les matériaux thermoplastiques, plus précisément ceux… …   Wikipédia en Français

  • Méthode Bille-Anneau — Point de ramollissement bille et anneau Le point de ramollissement par la méthode bille et anneau (ou TBA, température bille anneau) concerne typiquement les résines sous forme solide et les matériaux thermoplastiques, plus précisément ceux… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”