El algoritmo de Karmarkar

El algoritmo de Karmarkar , introducido por Narendra Karmarkar en 1984 para resolver problemas de programación lineal , fue el primer algoritmo razonablemente eficiente capaz de resolverlos en tiempo polinomial . El método del elipsoide también es polinomial, pero ha demostrado ser ineficiente en la práctica.

Denotando por${\displaystyle n}$el número de variables, m el número de restricciones de desigualdad y${\displaystyle L}$el número de bits de entrada al algoritmo, el algoritmo de Karmarkar requiere${\displaystyle O(m^{1.5}n^{2}L)}$operaciones en${\displaystyle O(L)}$números de - dígitos, en comparación con${\displaystyle O(n^{3}(n+m)L)}$tales operaciones para el algoritmo del elipsoide. ^{[ 1 ]} En problemas "cuadrados", cuando m está en O( n ), el algoritmo de Karmarkar requiere${\displaystyle O(n^{3.5}L)}$operaciones en${\displaystyle O(L)}$números de - dígitos, en comparación con${\displaystyle O(n^{4}L)}$tales operaciones para el algoritmo del elipsoide. El tiempo de ejecución del algoritmo de Karmarkar es, por lo tanto, $${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}$$ utilizando la multiplicación basada en FFT (ver notación Big O ).

El algoritmo de Karmarkar pertenece a la clase de métodos de punto interior : la estimación actual de la solución no sigue el límite del conjunto factible como en el método simplex , sino que se mueve a través del interior de la región factible, mejorando la aproximación de la solución óptima en una fracción definida con cada iteración y convergiendo a una solución óptima con datos racionales. ^{[ 2 ]}

Consideremos un problema de programación lineal en forma matricial:

El algoritmo de Karmarkar determina la siguiente dirección factible hacia la optimalidad y la reduce por un factor 0 < γ ≤ 1. Se describe en varias fuentes. ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} Karmarkar también ha extendido el método ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} para resolver problemas con restricciones enteras y problemas no convexos. ^{[ 13 ]}

Algoritmo de escalado afín

Entrada: A, b, c,${\displaystyle x^{0}}$, criterio de parada , γ .

${\displaystyle k\leftarrow 0}$hacer mientras el criterio de parada no se cumple${\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}}$si${\displaystyle h_{v}\geq 0}$entonces devolver un fin sin límites  si${\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\flecha izquierda k+1}$fin hacer

Consideremos el programa lineal. $${\displaystyle {\begin{array}{lrclr}{\text{maximizar}}&x_{1}+x_{2}\\{\text{sujeto a}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}$$ Es decir, hay 2 variables${\displaystyle x_{1},x_{2}}$y 11 restricciones asociadas con valores variables de${\displaystyle p}$Esta figura muestra cada iteración del algoritmo como puntos circulares rojos. Las restricciones se muestran como líneas azules.

Cuando inventó el algoritmo, Karmarkar trabajaba para IBM como becario postdoctoral en el Laboratorio de Investigación de IBM en San José , California. El 11 de agosto de 1983, impartió un seminario en la Universidad de Stanford explicando el algoritmo, con su afiliación aún registrada como IBM. En otoño de 1983, Karmarkar comenzó a trabajar en AT&T y presentó su artículo al Simposio ACM de 1984 sobre Teoría de la Computación (STOC, celebrado del 30 de abril al 2 de mayo de 1984), indicando AT&T Bell Laboratories como su afiliación. ^{[ 16 ]} Tras aplicar el algoritmo para optimizar la red telefónica de AT&T, ^{[ 17 ]} se percataron de que su invención podría tener importancia práctica. En abril de 1985, AT&T solicitó rápidamente una patente para su algoritmo.

La patente se convirtió en un nuevo combustible para la controversia en curso sobre el tema de las patentes de software . ^{[ 18 ]} Esto dejó a muchos matemáticos inquietos, como Ronald Rivest (uno de los titulares de la patente del algoritmo RSA ), quien expresó la opinión de que la investigación se basaba en el principio de que los algoritmos debían ser libres. Incluso antes de que se concediera la patente, se argumentó que podría haber habido un estado de la técnica anterior aplicable. ^{[ 19 ]} Los matemáticos que se especializaron en análisis numérico , incluidos Philip Gill y otros, afirmaron que el algoritmo de Karmarkar es equivalente a un método de barrera de Newton proyectado con una función de barrera logarítmica , si los parámetros se eligen adecuadamente. ^{[ 20 ]} El jurista Andrew Chin opina que el argumento de Gill era erróneo, en la medida en que el método que describen no constituye un "algoritmo", ya que requiere elecciones de parámetros que no se derivan de la lógica interna del método, sino que dependen de una guía externa, esencialmente del algoritmo de Karmarkar. ^{[ 21 ]} Además, las contribuciones de Karmarkar se consideran lejos de ser obvias a la luz de todos los trabajos anteriores, incluidos Fiacco-McCormick, Gill y otros citados por Saltzman. ^{[ 21 ] [ 22 ] [ 23 ]} La patente fue otorgada en reconocimiento de la originalidad esencial del trabajo de Karmarkar, como patente estadounidense 4,744,028 : "Métodos y aparatos para la asignación eficiente de recursos" en mayo de 1988.

AT&T diseñó un sistema informático multiprocesador vectorial específicamente para ejecutar el algoritmo de Karmarkar, llamando a la combinación resultante de hardware y software KORBX, ^{[ 24 ]} y comercializó este sistema a un precio de US$8,9 millones. ^{[ 25 ] [ 26 ]} Su primer cliente fue el Pentágono . ^{[ 27 ] [ 28 ]}

Los opositores a las patentes de software han argumentado además que las patentes arruinaron los ciclos de interacción positiva que caracterizaban la relación entre los investigadores en programación lineal y la industria, y específicamente aislaron al propio Karmarkar de la red de investigadores matemáticos en su campo. ^{[ 29 ]}

La patente expiró en abril de 2006 y el algoritmo actualmente es de dominio público .

La Corte Suprema de los Estados Unidos sostuvo que las matemáticas no pueden ser patentadas en Gottschalk v. Benson , ^{[ 30 ]} En ese caso, la Corte abordó primero si los algoritmos informáticos podían ser patentados y sostuvo que no podían porque el sistema de patentes no protege ideas y abstracciones similares. En Diamond v. Diehr , ^{[ 31 ]} la Corte Suprema declaró: "Una fórmula matemática como tal no recibe la protección de nuestras leyes de patentes, y este principio no puede ser eludido al intentar limitar el uso de la fórmula a un entorno tecnológico particular. ^{[ 32 ]} En Mayo Collaborative Services v. Prometheus Labs., Inc. , ^{[ 33 ]} la Corte Suprema explicó además que "simplemente implementar un principio matemático en una máquina física, a saber, una computadora, no es una aplicación patentable de ese principio". ^{[ 34 ]}

El algoritmo de Karmarkar fue utilizado por el Ejército de los Estados Unidos para la planificación logística durante la Guerra del Golfo . ^{[ 1 ]}

• Adler, Ilan ; Karmarkar, Narendra; Resende, Mauricio GC ; Veiga, Geraldo (1989). "Una implementación del algoritmo de Karmarkar para programación lineal". Mathematical Programming . 44 ( 1–3 ): 297–335 . doi : 10.1007/bf01587095 . S2CID 12851754 . 
• Narendra Karmarkar (1984). " Un nuevo algoritmo de tiempo polinomial para programación lineal " , Combinatorica , vol . 4 , n.º 4, págs.  373-395 .