Algorithme de Karmarkar

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L’algorithme de Karmarkar est un algorithme introduit par Narendra 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 de l'ellipsoïde fonctionne aussi en temps polynomial mais est inefficace en pratique.

En posant le nombre de variables et le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar réalise opérations sur bits à comparer aux opérations pour la méthode des ellipsoïdes. Le temps d'exécution de l'algorithme de Karmarkar est ainsi 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.

L'algorithme[modifier | modifier le code]

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

maximiser cTx
avec 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 qu'efficace en pratique, ne tourne pas en temps polynomial.

 Entrées : A, b, c, , critère d'arrêt, .
 
 do while critère d'arrêt non satisfait
  
  
  
  
  if  then
    return non bornée
  end if
  
  
  
 end do

Exemple[modifier | modifier le code]

Itérations de résolution

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

maximiser +
sous les contraintes + avec

Il y a deux variables et onze contraintes associées à différentes valeurs de . 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é[modifier | modifier le code]

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éficiaires du brevet sur l'algorithme de Rivest Shamir Adleman), qui défendait que le fait d'avoir des algorithmes libres 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 numériciens spécialisés en optimisation 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 l'algorithme est à présent dans le domaine public.

Références[modifier | modifier le code]

  1. (en) Gina Kolata, « IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes », The New York Times,‎ (lire en ligne)
  2. Various posts by Matthew Saltzman, Clemson University
  3. (en) Philip E. Gill, « On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method », Mathematical Programming, vol. 36, no 2,‎ , p. 183–209 (DOI 10.1007/BF02592025, lire en ligne)