Algoritmo de Karmarkar

El algoritmo de Karmarkar es un algoritmo introducido por Narendra Karmarkar en 1984 para resolver problemas de programación lineal . Fue el primer algoritmo razonablemente eficiente que resuelve estos problemas en tiempo polinómico . El método del elipsoide también es de tiempo polinómico, pero demostró ser ineficiente en la práctica.

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

${\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 se incluye en 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]

El algoritmo

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

El algoritmo de Karmarkar determina la siguiente dirección factible hacia la optimalidad y reduce la escala 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 escalamiento afín

Como el algoritmo actual es bastante complicado, los investigadores buscaron una versión más intuitiva del mismo y en 1985 desarrollaron el escalamiento afín , una versión del algoritmo de Karmarkar que utiliza transformaciones afines donde Karmarkar utilizó las proyectivas , solo para darse cuenta cuatro años después de que habían redescubierto un algoritmo publicado por el matemático soviético II Dikin en 1967. ^[14] El método de escalamiento afín se puede describir sucintamente de la siguiente manera. ^[15] Si bien es aplicable a problemas de pequeña escala, no es un algoritmo de tiempo polinomial. ^{[ cita requerida ]}

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

 ${\displaystyle k\leftarrow 0}$hacer mientras  criterio de detención  no satisfecho  si entonces devuelve ilimitado  fin si fin hacer ${\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}}$   ${\displaystyle h_{v}\geq 0}$    ${\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}$

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

Ejemplo

Ejemplo de solución

Consideremos el programa lineal

${\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&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 y 11 restricciones asociadas con valores variables de . Esta figura muestra cada iteración del algoritmo como puntos de círculos rojos. Las restricciones se muestran como líneas azules. ${\displaystyle x_{1},x_{2}}$ ${\displaystyle p}$

Controversia sobre patentes

En el momento en que inventó el algoritmo, Karmarkar trabajaba para IBM como investigador postdoctoral en el Laboratorio de Investigación IBM de San José, en California. El 11 de agosto de 1983 impartió un seminario en la Universidad de Stanford explicando el algoritmo, y su afiliación todavía figuraba como IBM. En el otoño de 1983, Karmarkar empezó a trabajar en AT&T y presentó su artículo en el Simposio ACM de 1984 sobre teoría de la computación (STOC, celebrado del 30 de abril al 2 de mayo de 1984) indicando que su afiliación eran los Laboratorios Bell de AT&T . ^[16] Después de aplicar el algoritmo para optimizar la red telefónica de AT&T, ^[17] se dieron cuenta de que su invención podía tener importancia práctica. En abril de 1985, AT&T solicitó rápidamente una patente para su algoritmo.

La patente se convirtió en más combustible para la controversia en curso sobre el tema de las patentes de software . ^[18] Esto dejó a muchos matemáticos incómodos, como Ronald Rivest (él mismo uno de los titulares de la patente sobre el algoritmo RSA ), quien expresó la opinión de que la investigación se realizó sobre la base de que los algoritmos deberían ser libres. Incluso antes de que se otorgara la patente, se argumentó que podría haber habido técnica anterior que fuera 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 erudito legal Andrew Chin opina que el argumento de Gill era defectuoso, 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 todo el trabajo previo, incluyendo Fiacco-McCormick, Gill y otros citados por Saltzman. ^{[21] [22] [23]} La patente fue debatida en el Senado de los EE. UU. ^{[ cita requerida ]} y concedida 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 8,9 millones de dólares estadounidenses. ^{[25] [26]} Su primer cliente fue el Pentágono . ^{[27] [28]}

Los oponentes a las patentes de software han argumentado además que las patentes arruinaron los ciclos de interacción positiva que anteriormente 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 se encuentra actualmente en el dominio público .

La Corte Suprema de los Estados Unidos sostuvo que las matemáticas no pueden patentarse en Gottschalk v. Benson [ ^30]. En ese caso, la Corte primero abordó si los algoritmos informáticos podían patentarse y sostuvo que no podían porque el sistema de patentes no protege las ideas y abstracciones similares. En Diamond v. Diehr ^[31] , la Corte Suprema afirmó: "Una fórmula matemática como tal no recibe la protección de nuestras leyes de patentes, y este principio no puede eludirse intentando 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]

Aplicaciones

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

Referencias

• Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio GC ; Veiga, Geraldo (1989). "Una implementación del algoritmo de Karmarkar para programación lineal". Programación matemática . 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ág. 373–395.

1. Arkadi Nemirovsky (2004). Métodos de tiempo polinomial de punto interior en programación convexa.
2. Strang, Gilbert (1 de junio de 1987). "El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas". The Mathematical Intelligencer . 9 (2): 4–10. doi :10.1007/BF03025891. ISSN  0343-6993. MR  0883185. S2CID  123541868.
3. Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Actas del decimosexto simposio anual de la ACM sobre teoría de la computación - STOC '84 . págs. 302–311. doi :10.1145/800057.808695. ISBN 0897911334. Número de identificación  S2C13101261.
4. Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Combinatorica . 4 (4): 373–395. doi :10.1007/BF02579150. S2CID  7257867.
5. Karmarkar, Narendra K. (1989). "Variantes de series de potencias de algoritmos de tipo Karmarkar". AT&T Technical Journal . 68 (3): 20–36. doi :10.1002/j.1538-7305.1989.tb00316.x. S2CID  42071587.
6. Karmarkar, Narendra (1990). "Un enfoque de punto interior para problemas NP-completos. I". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. Vol. 114. Providence, RI: American Mathematical Society. págs. 297–308. doi :10.1090/conm/114/1097880. MR  1097880.
7. Karmarkar, Narendra (1990). "Geometría riemanniana subyacente a los métodos de punto interior para programación lineal". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. Vol. 114. Providence, RI: American Mathematical Society. págs. 51–75. doi :10.1090/conm/114/1097865. MR  1097865.
8. Karmarkar NK, Lagarias, JC, Slutsman, L. y Wang, P., Variantes de series de potencias del algoritmo KarmarkarType, AT & T technical Journal 68, n.º 3, mayo/junio (1989).
9. Karmarkar, NK, Métodos de puntos interiores en optimización, Actas de la Segunda Conferencia Internacional sobre Matemáticas Industriales y Aplicadas, SIAM, págs. 160-181 (1991)
10. Karmarkar, NK y Kamath, AP, Un enfoque continuo para derivar límites superiores en problemas de maximización cuadrática con restricciones enteras, Avances recientes en optimización global, págs. 125-140, Princeton University Press (1992).
11. 26. Karmarkar, NK, Thakur, SA, Un enfoque de punto interior para un problema de optimización tensorial con aplicación a límites superiores en problemas de optimización cuadrática de enteros, Actas de la Segunda Conferencia sobre Programación Entera y Optimización Combinatoria, (mayo de 1992).
12. 27. Kamath, A., Karmarkar, NK, Un método continuo para calcular límites en problemas de optimización cuadrática entera, Journal of Global Optimization (1992).
13. Karmarkar, NK, Más allá de la convexidad: nuevas perspectivas en optimización computacional. Springer Lecture Notes in Computer Science LNCS 6457, diciembre de 2010
14. Vanderbei, RJ; Lagarias, JC (1990). "Resultado de convergencia de II Dikin para el algoritmo de escalamiento afín". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. Vol. 114. Providence, RI: American Mathematical Society. págs. 109–119. doi :10.1090/conm/114/1097868. MR  1097868.
15. Robert J. Vanderbei ; Meketon, Marc; Freedman, Barry (1986). "Una modificación del algoritmo de programación lineal de Karmarkar" (PDF) . Algorithmica . 1 (1–4): 395–407. doi :10.1007/BF01840454. S2CID  779577.
16. Algoritmo de Karmarkar, IBM Research , consultado el 1 de junio de 2016
17. Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A. y Ramakrishnan KG, Planificación de redes en el extranjero, Actas del tercer simposio internacional de planificación de redes, NETWORKS' 86, Tarpon Springs, Florida (junio de 1986).
18. Kolata, Gina (12 de marzo de 1989). "IDEAS Y TENDENCIAS; Los matemáticos están preocupados por las afirmaciones sobre sus recetas". The New York Times .
19. Varias publicaciones de Matthew Saltzman, Universidad de Clemson
20. Gill, Philip E.; Murray, Walter; Saunders, Michael A.; Tomlin, JA; Wright, Margaret H. (1986). "Sobre los métodos de barrera de Newton proyectados para programación lineal y una equivalencia con el método proyectivo de Karmarkar". Programación matemática . 36 (2): 183–209. doi :10.1007/BF02592025. S2CID  18899771.
21. Andrew Chin (2009). "Sobre la abstracción y la equivalencia en la doctrina de las patentes de software: una respuesta a Bessen, Meurer y Klemens" (PDF) . Revista de Derecho de la Propiedad Intelectual . 16 : 214–223.
22. Mark A. Paley (1995). "La patente Karmarkar: por qué el Congreso debería "abrir la puerta" a los algoritmos como materia patentable". 22 Computer L. Rep. 7
23. Margaret H. Wright (2004). "La revolución del punto interior en la optimización: historia, desarrollos recientes y consecuencias duraderas" (PDF) . Boletín de la American Mathematical Society . 42 : 39–56. doi : 10.1090/S0273-0979-04-01040-7 .
24. Marc S. Meketon; YC Cheng; DJ Houck; JMLiu; L. Slutsman; Robert J. Vanderbei ; P. Wang (1989). "El sistema AT&T KORBX". Revista técnica AT&T . 68 (3): 7–19. doi :10.1002/j.1538-7305.1989.tb00315.x. S2CID  18548851.
25. Lowenstein, Roger (15 de agosto de 1988). «AT&T comercializa un solucionador de problemas basado en el hallazgo de un genio de las matemáticas por 8,9 millones de dólares» (PDF) . Wall Street Journal . Archivado desde el original (PDF) el 8 de junio de 2016. Consultado el 30 de enero de 2016 .
26. Markoff, John (13 de agosto de 1988). "Big AT&T. Computadora para complejidades". The New York Times .
27. "El ejército es el primer cliente anunciado de AT&T Software". Associated Press . AP News . Consultado el 11 de junio de 2019 .
28. Kennington, JL (1989). "Uso de KORBX para aplicaciones de transporte aéreo militar". Actas de la 28.ª Conferencia IEEE sobre decisión y control . págs. 1603–1605. doi :10.1109/CDC.1989.70419. S2CID  60450719.
29. "今野浩: カーマーカー特許とソフトウェア - 数学は 特許に なるか (Konno Hiroshi: La patente y el software de Kamarkar - ¿Se han vuelto patentables las matemáticas?)". FFII . Archivado desde el original el 27 de junio de 2008 . Consultado el 27 de junio de 2008 .
30. 409 US 63 (1972). El caso se refería a un algoritmo para convertir números decimales codificados en binario a binario puro.
31. 450 Estados Unidos 175 (1981).
32. 450 US en 191. Véase también Parker v. Flook , 437 US 584, 585 (1978) ("el descubrimiento de una fórmula matemática novedosa y útil no puede patentarse").
33. 566 Estados Unidos __, 132 S. Ct. 1289 (2012).
34. Accord Alice Corp. contra CLS Bank Int'l , 573 US __, 134 S. Ct. 2347 (2014).