Algorithme de Karmarkar

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

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, ${\displaystyle x^{0}}$, critère d'arrêt, ${\displaystyle \gamma }$.

 ${\displaystyle k\leftarrow 0}$
 do while critère d'arrêt non satisfait
  ${\displaystyle v^{k}\leftarrow b-Ax^{k}}$
  ${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$
  ${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$
  ${\displaystyle h_{v}\leftarrow -Ah_{x}}$
  if ${\displaystyle h_{v}\geq 0}$ then
    return non bornée
  end if
  ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$
  ${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$
  ${\displaystyle k\leftarrow k+1}$
 end do

Itérations de résolution

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

maximiser		${\displaystyle x_{1}}$	+	${\displaystyle x_{2}}$
sous les contraintes		${\displaystyle 2px_{1}}$	+	${\displaystyle x_{2}}$	${\displaystyle \leq }$ ${\displaystyle p^{2}+1}$ avec ${\displaystyle p=0.0,0.1,0.2,\ldots ,0.9,1.0.}$

Il y a deux variables ${\displaystyle x_{1},x_{2}}$ et onze contraintes associées à différentes valeurs de ${\displaystyle p}$. La figure montre chaque itération de l'algorithme avec des points rouge. Les contraintes sont représentées par des lignes bleues.

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.

• Ilan Adler, Narendra Karmarkar, Mauricio G.C. Resende and Geraldo Veiga (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming, Vol 44, p. 297–335.
• Narendra Karmarkar (1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.