Algoritmo 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 suficientemente eficiente para resolver problemas en tiempo polinomial . El método del elipsoide también es un algoritmo de tiempo polinomial, pero ha demostrado ser ineficiente en aplicaciones prácticas.

Si es el número de variables y es el número de bits de entrada, el algoritmo de Karmarkar requiere operaciones con números con signo , mientras que el método del elipsoide requiere tales operaciones. El tiempo de ejecución del algoritmo Karmarkar es $norte$ $L$ $O(n^{3.5}L)$ ${\ estilo de visualización O (L)}$ $O(n^{6}L)$

O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)

cuando se usa el método de multiplicación de Schönhage-Strassen (ver "O" grande ).

El algoritmo de Karmarkar pertenece a la clase de métodos de puntos interiores : la solución factible actual no se mueve a lo largo del límite del dominio de soluciones factibles como en el método simplex , sino que se mueve a lo largo de los puntos interiores del dominio de valores factibles, mejorando con cada uno. iteración la aproximación de la solución óptima por una fracción determinada y que conduce a una solución óptima con datos racionales [1] .

Algoritmo

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

maximizar c T x
bajo restricciones	Hacha ≤ b.

El algoritmo determina la siguiente dirección factible hacia la solución óptima y retrocede por un factor 0 < γ ≤ 1.

El algoritmo de Karmarkar es bastante complicado. Los lectores interesados pueden encontrar información sobre las referencias [2] [3] [4] [5] [6] [7] [8] . Una versión simplificada llamada "Método de escalado afín" analizada en otros artículos [9] se puede describir brevemente de la siguiente manera. Tenga en cuenta que el método de escalamiento afín, cuando se usa para problemas de tamaño pequeño, no es un algoritmo de tiempo polinomial. Para problemas de gran tamaño y complejos, se debe seguir el enfoque original. Karmarkar también amplió la metodología [10] [11] [12] [13] de resolución de problemas con restricciones de enteros y problemas no convexos [14] .

Entrada: A, b, c, , Criterio de parada , .

x^0

\gama

k\flecha izquierda 0

hacer mientras que el criterio de parada falla si luego devuelve la decisión ilimitada finaliza si finaliza hacer

v^{k}\leftarrow b-Ax^{k}

D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots,v_{m}^{k})

h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c

h_{v}\leftarrow -Ah_{x}

h_{v}\geq 0

\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v}) _ {i} <0,\,i=1,\ldots,m\}

x^{k+1}\leftarrow x^{k}+\alpha h_{x}

{\ estilo de visualización k \ flecha izquierda k + 1}

Aquí

"←" es la abreviatura de "cambiar a". Por ejemplo, "elemento ← más grande" significa que el valor del elemento más grande se reemplaza por el valor del elemento.
"return" interrumpe el algoritmo y muestra el valor que se escribe después del comando.

Ejemplo

Sea dado un problema de programación lineal

maximizar		$x_{1}$	+	$x_{2}$
bajo condiciones		${\ estilo de visualización 2px_ {1}}$	+	$x_{2}$	$\leq$ $p^{2}+1$ , $p=0.0,0.1,0.2,\ldots,0.9,1.0.$

Es decir, hay dos variables y 11 restricciones correspondientes a diferentes valores de . La figura muestra cada iteración del algoritmo como un punto rojo. Los límites se muestran como líneas azules. $x_{1},x_{2}$ $pags$

Debate sobre patentes - ¿Se pueden patentar las matemáticas?

En el momento en que Narenda Karmarkar propuso su algoritmo, trabajaba en AT&T . Después de la implementación del algoritmo para optimizar la red telefónica de AT&T [15] , se dieron cuenta de que podía tener una importancia práctica. En abril de 1985, AT&T solicitó rápidamente una patente sobre el algoritmo de Karmarkar, y este evento agregó combustible al acalorado debate sobre la patente del software [16] . Esto ha causado preocupación a muchos matemáticos, como Ronald Rivest (es uno de los titulares de la patente del algoritmo RSA ), quien opinó que la investigación basada en este algoritmo debería ser gratuita. Incluso antes de que se aprobara la patente, algunos afirmaron que había un prototipo no realizado [17] .

Matemáticos especializados en métodos computacionales , como Philip Gill y otros, han argumentado que el algoritmo de Karmarkar es equivalente al método de barrera proyectivo de Newton con una función de barrera logarítmica si los parámetros se eligen correctamente [18] . Sin embargo, el argumento de Gill tiene una falla, ya que el método que describe ni siquiera se considera un "algoritmo", ya que requiere la elección de parámetros que no están determinados por la lógica interna del método y dependen completamente del control externo, especialmente con respecto a al algoritmo de Karmarkar [19] . Además, la contribución de Karmarkar está lejos de ser obvia a la luz de todos los trabajos anteriores, incluidos los de Fiacco-McCormick, Gill y otros enumerados por Saltzman [19] [20] [21] . La patente fue debatida en el Senado de EE. UU., fue aprobada en reconocimiento de la significativa originalidad del trabajo de Karmarkar y se presentó como Patente de EE. UU. 4.744.026 "Métodos y aparatos para la asignación eficiente de recursos" en mayo de 1988. AT&T suministró el KORBX [22] [23 ] basado en esta patente, The Pentagon [24] [25] , que lo utilizó para resolver problemas matemáticos que antes se consideraban irresolubles.

Los opositores a las patentes de software afirmaron más tarde que las patentes interrumpieron el ciclo positivo que caracterizaba la relación de los investigadores en programación lineal y producción y, en particular, aislaron al propio Karmarkar de la investigación matemática en su campo [26] .

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

Notas

↑ Gilbert Strang. El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas (inglés) // The Mathematical Intelligencer . - Nueva York: Springer, 1987. - vol. 9 , edición. 2 . - Pág. 4-10 . — ISSN 0343-6993 . -doi : 10.1007/ BF03025891 .
↑ Un nuevo algoritmo de tiempo polinomial para programación lineal . Consultado el 26 de agosto de 2015. Archivado desde el original el 14 de febrero de 2019. (indefinido)
↑ Un nuevo algoritmo de tiempo polinomial para programación lineal: Springer . Consultado el 29 de septiembre de 2017. Archivado desde el original el 6 de septiembre de 2017. (indefinido)
↑ Power Series Variants of Karmarkar-Type Algorithms - Karmarkar - 2013 - AT&T Technical Journal - Wiley Online Library . Consultado el 26 de agosto de 2015. Archivado desde el original el 16 de julio de 2015. (indefinido)
↑ Karmarkar NK, An InteriorPoint Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, pp. 297308 (junio de 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Archivado el 4 de marzo de 2016 en Wayback Machine .
↑ Karmarkar, NK., Geometría de Riemann que subyace a los métodos de puntos interiores para la programación lineal, serie AMS sobre matemáticas contemporáneas 114, págs. 5175 (junio de 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf Archivado el 4 de marzo de 2016 en Wayback Machine .
↑ Karmarkar NK, Lagarias, JC, Slutsman, L. y Wang, P., Power Series Variants of KarmarkarType Algorithm, AT&T Technical Journal 68, no. 3, mayo/junio (1989).
↑ Copia archivada (enlace no disponible) . Consultado el 26 de agosto de 2015. Archivado desde el original el 4 de marzo de 2016. (indefinido)
↑ Robert J. Vanderbei , Marc Meketon, Barry Freedman. Una modificación del algoritmo de programación lineal de Karmarkar // Algorithmica. - 1986. - T. 1 . - S. 395-407 . -doi : 10.1007/ BF01840454 .
↑ Karmarkar, NK, Interior Point Methods in Optimization, Actas de la Segunda Conferencia Internacional sobre Matemática Industrial y Aplicada, SIAM, págs. 160181 (1991)
↑ Karmarkar, NK y Kamath, AP, Un enfoque continuo para derivar límites superiores en problemas de maximización cuadrática con restricciones de enteros, Avances recientes en la optimización global, págs. 125140, Prensa de la Universidad de Princeton (1992).
↑ 26. Karmarkar, NK, Thakur, SA, An Interior Point Approach to a Tensor Optimization Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Actas de la segunda conferencia sobre programación entera y optimización combinatoria (mayo de 1992).
↑ 27. Kamath, A., Karmarkar, NK, Un método continuo para calcular límites en problemas de optimización cuadrática de enteros, Journal of Global Optimization (1992).
↑ Karmarkar, NK, Más allá de la convexidad: nuevas perspectivas en la optimización computacional. Springer Lecture Notes in Computer Science LNCS 6457, diciembre de 2010
↑ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A. y Ramakrishnan KG, Overseas Network Planning, Actas del Tercer Simposio Internacional de Planificación de Redes, NETWORKS' 86, Tarpon Springs, Florida (junio de 1986).
↑ Gina Kolata. IDEAS Y TENDENCIAS; Los matemáticos están preocupados por las afirmaciones sobre sus recetas // The New York Times . — 1989-03-12.
↑ Varias publicaciones de Matthew Saltzman, Universidad de Clemson . Consultado el 26 de agosto de 2015. Archivado desde el original el 23 de septiembre de 2015. (indefinido)
↑ Philip E. Gill, Walter Murray, Michael A. Saunders, JA Tomlin, Margaret H. Wright. Sobre métodos de barrera de Newton proyectados para programación lineal y una equivalencia al método proyectivo de Karmarkar // Programación matemática. - 1986. - T. 36 . - S. 183-209 . -doi : 10.1007/ BF02592025 .
↑ 12 Andrew Chin . Sobre abstracción y equivalencia en la doctrina de patentes de software: una respuesta a Bessen, Meurer y Klemens // Journal Of Intellectual Property Law. - 2009. - T. 16 . - S. 214-223 .
↑ Mark A. Paley (1995). "La patente de Karmarkar: por qué el Congreso debería" abrir la puerta "a los algoritmos como materia patentable". 22 COMPUTADORA IZQ. REP. 7
↑ Margaret H. Wright. La revolución del punto interior en la optimización: historia, desarrollos recientes y consecuencias duraderas // Boletines de la Sociedad Matemática Estadounidense. - 2004. - T. 42 . - S. 39-56 .
↑ Marc S. Meketon, YC Cheng, DJ Houck, JMLiu, L. Slutsman, Robert J. Vanderbei , P. Wang. El sistema KORBX de AT&T // Diario técnico de AT&T. - 1989. - T. 68 . - S. 7-19 .
↑ Gran AT&T. Computadora para Complejidades - NYTimes.com . Consultado el 29 de septiembre de 2017. Archivado desde el original el 1 de febrero de 2018. (indefinido)
↑ Military es el primer cliente anunciado de AT&T Software . Consultado el 26 de agosto de 2015. Archivado desde el original el 6 de septiembre de 2015. (indefinido)
↑ Resumen de IEEE Xplore: uso de KORBX para aplicaciones de transporte aéreo militar . Consultado el 26 de agosto de 2015. Archivado desde el original el 13 de noviembre de 2014. (indefinido)
↑ 今野浩: カーマーカー特許とソフトウェア – 数学は特許になるか (Konno Hiroshi: La patente y el software de Kamarkar: ¿las matemáticas se han vuelto patentables?). — FFI . Archivado desde el original el 27 de junio de 2008.

Literatura

Ilan Adler, Narendra Karmarkar, Mauricio GC Resende y Geraldo Veiga (1989). "Una implementación del algoritmo de Karmarkar para programación lineal". Programación Matemática , Vol 44, p. 297-335.
Narendra Karmarkar (1984). " Un nuevo algoritmo de tiempo polinomial para programación lineal ", Combinatorica , Vol 4 , nr. 4, pág. 373-395.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial