L'algorithme de Karmarkar

L'algorithme de Karmarkar est un algorithme introduit par Narendra Karmarkar en 1984 pour résoudre des problèmes de programmation linéaire . Il s'agit du premier algorithme raisonnablement efficace qui résout ces problèmes en temps polynomial . La méthode de l'ellipsoïde est également en temps polynomial mais s'est avérée inefficace en pratique.

En désignant par le nombre de variables, m le nombre de contraintes d'inégalité et le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar nécessite des opérations sur des nombres à -chiffres, par rapport à de telles opérations pour l'algorithme ellipsoïde. Dans les problèmes « carrés », lorsque m est dans O( n ), l'algorithme de Karmarkar nécessite des opérations sur des nombres à -chiffres, par rapport à de telles opérations pour l'algorithme ellipsoïde. Le temps d'exécution de l'algorithme de Karmarkar est donc ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle L <semantics> <mrow> <mstyle> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle L}</annotation> </semantics> </math><img src=$ ${\displaystyle O(m^{1.5}n^{2}L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>m</mi> <mrow> <mn>1,5</mn> </mrow> </msup> <msup> <mi>n</mi> <mrow> <mn>2</mn> </mrow> </msup> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(m^{1.5}n^{2}L)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(L)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(n^{3}(n+m)L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>3</mn> </mrow> </msup> <mo>(</mo> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo>)</mo> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n^{3}(n+m)L)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(n^{3.5}L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>3.5</mn> </mrow> </msup> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n^{3.5}L)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(L)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(n^{4}L) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>4</mn> </mrow> </msup> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n^{4}L)}</annotation> </semantics> </math><img src=$

{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L), <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>3.5</mn> </mrow> </msup> <msup> <mi>L</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mi>L</mi> <mo>⋅</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mi>L</mi> <mo>)</mo> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}</annotation> </semantics> </math></span><img src=

en utilisant la multiplication basée sur la FFT (voir la notation Big O ).

L'algorithme de Karmarkar appartient à la classe des méthodes de point intérieur : l'estimation actuelle de la solution ne suit pas la limite de l' ensemble faisable comme dans la méthode du simplexe , mais se déplace à l'intérieur de la région faisable, améliorant l'approximation de la solution optimale d'une fraction définie à chaque itération et convergeant vers une solution optimale avec des données rationnelles.

L'algorithme

Considérons un problème de programmation linéaire sous forme matricielle :

L'algorithme de Karmarkar détermine la prochaine direction possible vers l'optimalité et réduit d'un facteur 0 < γ ≤ 1. Il est décrit dans un certain nombre de sources. Karmarkar a également étendu la méthode pour résoudre des problèmes avec des contraintes entières et des problèmes non convexes.

Algorithme de mise à l'échelle affine

Comme l'algorithme actuel est plutôt compliqué, les chercheurs ont cherché une version plus intuitive de celui-ci et ont développé en 1985 la mise à l'échelle affine , une version de l'algorithme de Karmarkar qui utilise des transformations affines là où Karmarkar utilisait des transformations projectives , pour se rendre compte quatre ans plus tard qu'ils avaient redécouvert un algorithme publié par le mathématicien soviétique II Dikin en 1967. La méthode de mise à l'échelle affine peut être décrite succinctement comme suit. Bien qu'applicable aux problèmes à petite échelle, ce n'est pas un algorithme en temps polynomial.

Entrée : A, b, c, ,  ${\displaystyle x^{0 <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mn>0</mn> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{0}}</annotation> </semantics> </math></span><img src=$ 
critère d'arrêt , γ .

 ${\displaystyle k\leftarrow 0 <semantics> <mrow> <mstyle> <mi>k</mi> <mo>←</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle k\leftarrow 0}</annotation> </semantics> </math></span><img src=$ 
faire pendant 
l'arrêt critère 
non satisfait 
si alors renvoyer illimité  fin si fin faire ${\displaystyle v^{k}\leftarrow b-Ax^{k <semantics> <mrow> <mstyle> <msup> <mi>v</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>←</mo> <mi>b</mi> <mo>−</mo> <mi>A</mi> <msup> <mi>x</mi> <mrow> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle v^{k}\leftarrow b-Ax^{k}}</annotation> </semantics> </math></span><img src=$ 
 ${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k}) <semantics> <mrow> <mstyle> <msub> <mi>D</mi> <mrow> <mi>v</mi> </mrow> </msub> <mo>←</mo> <mi>diag</mi> <mo>⁡</mo> <mo>(</mo> <msubsup> <mi>v</mi> <mrow> <mn>1</mn> </mrow> <mrow> <mi>k</mi> </mrow> </msubsup> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msubsup> <mi>v</mi> <mrow> <mi>m</mi> </mrow> <mrow> <mi>k</mi> </mrow> </msubsup> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}</annotation> </semantics> </math></span><img src=$ 
 ${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c <semantics> <mrow> <mstyle> <msub> <mi>h</mi> <mrow> <mi>x</mi> </mrow> </msub> <mo>←</mo> <mo>(</mo> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <msubsup> <mi>D</mi> <mrow> <mi>v</mi> </mrow> <mrow> <mo>−</mo> <mn>2</mn> </mrow> </msubsup> <mi>A</mi> <msup> <mo>)</mo> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>c</mi> </mstyle> </mrow> <annotation>{\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}</annotation> </semantics> </math></span><img src=$ 
 ${\displaystyle h_{v}\leftarrow -Ah_{x <semantics> <mrow> <mstyle> <msub> <mi>h</mi> <mrow> <mi>v</mi> </mrow> </msub> <mo>←</mo> <mo>−</mo> <mi>A</mi> <msub> <mi>h</mi> <mrow> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle h_{v}\leftarrow -Ah_{x}}</annotation> </semantics> </math></span><img src=$ 

 ${\displaystyle h_{v}\geq 0 <semantics> <mrow> <mstyle> <msub> <mi>h</mi> <mrow> <mi>v</mi> </mrow> </msub> <mo>≥</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle h_{v}\geq 0}</annotation> </semantics> </math></span><img src=$ 

 ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\ <semantics> <mrow> <mstyle> <mi>α</mi> <mo>←</mo> <mi>γ</mi> <mo>⋅</mo> <mo>min</mo> <mo>{</mo> <mo>−</mo> <msubsup> <mi>v</mi> <mrow> <mi>i</mi> </mrow> <mrow> <mi>k</mi> </mrow> </msubsup> <mrow> <mo>/</mo> </mrow> <mo>(</mo> <msub> <mi>h</mi> <mrow> <mi>v</mi> </mrow> </msub> <msub> <mo>)</mo> <mrow> <mi>i</mi> </mrow> </msub> <mspace></mspace> <mspace></mspace> <mrow> <mo>|</mo> </mrow> <mspace></mspace> <mspace></mspace> <mo>(</mo> <msub> <mi>h</mi> <mrow> <mi>v</mi> </mrow> </msub> <msub> <mo>)</mo> <mrow> <mi>i</mi> </mrow> </msub> <mo><</mo> <mn>0</mn> <mo>,</mo> <mspace></mspace> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>m</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}</annotation> </semantics> </math></span><img src=$ 
 ${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo>←</mo> <msup> <mi>x</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>+</mo> <mi>α</mi> <msub> <mi>h</mi> <mrow> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}</annotation> </semantics> </math></span><img src=$ 
 ${\displaystyle k\leftarrow k+1 <semantics> <mrow> <mstyle> <mi>k</mi> <mo>←</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle k\leftarrow k+1}</annotation> </semantics> </math></span><img src=$

« ← » désigne une affectation . Par exemple, « le plus grand élément ← » signifie que la valeur du plus grand élément change en valeur de l'élément .
« return » termine l'algorithme et renvoie la valeur suivante.

Exemple

Considérons le programme linéaire

{\displaystyle {\begin{array}{lrclr}{ ext{maximize}}&x_{1}+x_{2}\\{ ext{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mrow> <mtext>maximize</mtext> </mrow> </mtd> <mtd> <msub> <mi>x</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow> <mn>2</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <mrow> <mtext>subject to</mtext> </mrow> </mtd> <mtd> <mn>2</mn> <mi>p</mi> <msub> <mi>x</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow> <mn>2</mn> </mrow> </msub> </mtd> <mtd> <mo>≤</mo> </mtd> <mtd> <msup> <mi>p</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>1</mn> <mo>,</mo> </mtd> <mtd> <mi>p</mi> <mo>=</mo> <mn>0.0</mn> <mo>,</mo> <mn>0.1</mn> <mo>,</mo> <mn>0.2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mn>0.9</mn> <mo>,</mo> <mn>1.0.</mn> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{array}{lrclr}{ ext{maximize}}&x_{1}+x_{2}\\{ ext{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}</annotation> </semantics> </math></span><img src=

Autrement dit, il existe 2 variables et 11 contraintes associées à des valeurs variables de . Cette figure montre chaque itération de l'algorithme sous forme de points en forme de cercle rouge. Les contraintes sont représentées par des lignes bleues. ${\displaystyle x_{1},x_{2 <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>x</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{1},x_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle p <semantics> <mrow> <mstyle> <mi>p</mi> </mstyle> </mrow> <annotation>{\displaystyle p}</annotation> </semantics> </math><img src=$

Controverse sur les brevets

À l'époque où il a inventé l'algorithme, Karmarkar était employé par IBM en tant que chercheur postdoctoral au laboratoire de recherche IBM de San Jose en Californie. Le 11 août 1983, il a donné un séminaire à l'université de Stanford expliquant l'algorithme, son affiliation étant toujours indiquée comme IBM. À l'automne 1983, Karmarkar a commencé à travailler chez AT&T et a soumis son article au Symposium ACM de 1984 sur la théorie de l'informatique (STOC, qui s'est tenu du 30 avril au 2 mai 1984) en indiquant AT&T Bell Laboratories comme son affiliation. Après avoir appliqué l'algorithme à l'optimisation du réseau téléphonique d'AT&T, ils ont réalisé que son invention pourrait avoir une importance pratique. En avril 1985, AT&T a rapidement déposé une demande de brevet sur son algorithme.

Le brevet est devenu un élément de plus dans la controverse en cours sur la question des brevets logiciels . Cela a laissé de nombreux mathématiciens mal à l'aise, comme Ronald Rivest (lui-même l'un des détenteurs du brevet sur l' algorithme RSA ), qui a exprimé l'opinion que la recherche se déroulait sur la base que les algorithmes devraient être libres. Même avant que le brevet ne soit effectivement accordé, on a fait valoir qu'il pourrait y avoir un art antérieur applicable. Des mathématiciens spécialisés dans l'analyse numérique , dont Philip Gill et d'autres, ont affirmé que l'algorithme de Karmarkar est équivalent à une méthode de barrière de Newton projetée avec une fonction de barrière logarithmique , si les paramètres sont choisis de manière appropriée. Le juriste Andrew Chin estime que l'argument de Gill était erroné, dans la mesure où la méthode qu'ils décrivent ne constitue pas un « algorithme », car elle nécessite des choix de paramètres qui ne découlent pas de la logique interne de la méthode, mais s'appuient sur des conseils externes, essentiellement de l'algorithme de Karmarkar. De plus, les contributions de Karmarkar sont considérées comme loin d'être évidentes à la lumière de tous les travaux antérieurs, y compris ceux de Fiacco-McCormick, Gill et d'autres cités par Saltzman. Le brevet a été débattu au Sénat américain et accordé en reconnaissance de l'originalité essentielle du travail de Karmarkar, sous le brevet américain 4 744 028 : « Méthodes et appareils pour une allocation efficace des ressources » en mai 1988.

AT&T a conçu un système informatique multiprocesseur vectoriel spécifiquement pour exécuter l'algorithme de Karmarkar, appelant la combinaison résultante de matériel et de logiciel KORBX, et a commercialisé ce système au prix de 8,9 millions de dollars américains. Son premier client était le Pentagone .

Les opposants aux brevets logiciels ont en outre soutenu que les brevets ont ruiné les cycles d'interaction positifs qui caractérisaient auparavant la relation entre les chercheurs en programmation linéaire et l'industrie, et plus particulièrement qu'ils ont isolé Karmarkar lui-même du réseau de chercheurs en mathématiques dans son domaine.

Le brevet lui-même a expiré en avril 2006 et l’algorithme est actuellement dans le domaine public .

La Cour suprême des États-Unis a jugé que les mathématiques ne pouvaient pas être brevetées dans l'affaire Gottschalk c. Benson [ ]. Dans cette affaire, la Cour a d'abord examiné si les algorithmes informatiques pouvaient être brevetés et a jugé qu'ils ne le pouvaient pas parce que le système des brevets ne protège pas les idées et les abstractions similaires. Dans l'affaire Diamond c. Diehr , la Cour suprême a déclaré : « Une formule mathématique en tant que telle ne bénéficie pas de la protection de nos lois sur les brevets, et ce principe ne peut être contourné en essayant de limiter l'utilisation de la formule à un environnement technologique particulier. » Dans l'affaire Mayo Collaborative Services c. Prometheus Labs., Inc. , la Cour suprême a expliqué en outre que « la simple mise en œuvre d'un principe mathématique sur une machine physique, à savoir un ordinateur, n'est pas une application brevetable de ce principe. »

Applications

L'algorithme de Karmarkar a été utilisé par l'armée américaine pour la planification logistique pendant la guerre du Golfe .

Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio GC ; Veiga, Geraldo (1989). "Une implémentation de l'algorithme de Karmarkar pour la programmation linéaire". Programmation mathématique . 44 (1–3) : 297–335. doi :10.1007/bf01587095. S2CID 12851754.
Narendra Karmarkar (1984). « Un nouvel algorithme de temps polynomial pour la programmation linéaire », Combinatorica , Vol 4 , nr. 4, p. 373–395.

Optimisation : algorithmes , méthodes et heuristiques