Algorithme de Karmarkar

L’algorithme de Karmarkar est un algorithme introduit par Narenda Karmarkar en 1984 pour résoudre les problèmes d'optimisation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode des ellipsoïdes fonctionne aussi en temps polynomial mais est inefficace en pratique.

En posant n le nombre de variables et L le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar réalise O(n3,5L) opérations sur O(L) bits à comparer aux O(n6L) opérations pour la méthode des ellipsoïdes. Le temps d'exécution de l'algorithme de Karmarkar est ainsi O(n3,5L2ln Lln ln L) en utilisant l'algorithme de Schönhage-Strassen (voir Comparaison asymptotique).

L'algorithme de Karmakar est une méthode du point intérieur : la solution candidate courante ne suit pas les bornes de l'espace faisable comme dans l'algorithme du simplexe, mais approche par l'intérieur de l'espace faisable et atteint la solution optimale de manière asymptotique.

Sommaire

L'algorithme

Soit le problème d'optimisation linéaire sous forme matricielle suivant :

maximize cTx
subject to Ax ≤ b.

L'algorithme de Karmarkar est complexe. Une version simplifiée, appelée "affine scaling method", est succinctement décrite ci dessous. Il faut noter que cet algorithme, bien que efficace en pratique, ne tourne pas en temps polynomial.

 Entrées : A, b, c, x0, critère d'arrêt, γ.
  k \leftarrow 0 
 do while critère d'arrêt non satisfait
  v^k \leftarrow b-Ax^k
  D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)
  h_x\leftarrow (A^TD_v^{-2}A)^{-1}c
  h_v\leftarrow -Ah_x
  if h_v \ge 0 then
    return non bornée
  end if
  \alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}
  x^{k+1}\leftarrow x^k + \alpha h_x
  k\leftarrow k+1
 end do

Exemple

Considérons le problème d'optimisation linéaire suivant :

maximiser x1 + x2
sous les contraintes 2px1 + x2 \leq p2 + 1, p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0.

Il y a 2 variables x1,x2 et 11 contraintes associées à différentes valeurs de p. La figure montre chaque itération de l'algorithme avec des points rouge. Les contraintes sont représentées par des lignes bleues.

Un brevet controversé

Au moment où il a découvert l'algorithme, Narenda Karmarkar était employé par AT&T. Comme la découverte pouvait avoir d'importantes applications, AT&T dépose un brevet pour l'algorithme de Karmarkar en avril 1985, ce qui a alimenté la controverse au sujet de la brevetabilité du logiciel[1]. Cette controverse a provoqué la réaction de nombreux mathématiciens comme Ronald Rivest (lui même est l'un des bénéficiaire du brevet sur l'algorithme de Rivest Shamir Adleman), qui défendait que le fait d'avoir des algorithmes libre de droit est une base de la recherche. Même avant que le brevet soit réellement accordé, il semble que la règle d'antériorité s'appliquait[2]. Les mathématiciens spécialisés en analyse numérique comme Philip Gill ont montré que l'algorithme de Karmarkar est équivalent à une méthode de Newton pénalisée projetée, avec une fonction de pénalisation logarithmique, si les paramètres sont bien choisis[3].

Le brevet a expiré en avril 2006 et est à présent dans le domaine public.

Références

  1. Kolata, Gina : IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes, The New York Times (1989-03-12).
  2. Various posts by Matthew Saltzman, Clemson University
  3. Philip E. Gill, « On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method », dans Mathematical Programming, vol. 36, no 2, 1986, p. 183–209 [texte intégral, lien DOI] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Karmarkar 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 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… …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

  • PLNE — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programmation lineaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programmation linéaire — En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l… …   Wikipédia en Français

  • Programmation linéaire en nombre entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programmation linéaire en nombres entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programme linéaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

Share the article and excerpts

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