El cubo Klee-menta o politopo Klee-menta (el nombre de Victor Klee y George J. menta ) es una unidad de hipercubo de la variable dimensión cuyas esquinas han sido perturbado. Klee y menta demostrado que George Dantzig 's algoritmo simplex tiene bajo rendimiento peor de los casos cuando se inicializa en una esquina de su 'cubo aplastado'. En la versión tridimensional, el algoritmo simplex y el algoritmo entrecruzado visitan las 8 esquinas en el peor de los casos.
En particular, muchos algoritmos de optimización para la optimización lineal presentan un rendimiento deficiente cuando se aplican al cubo de Klee-Minty. En 1973, Klee y Minty demostraron que el algoritmo simplex de Dantzig no era un algoritmo de tiempo polinomial cuando se aplicaba a su cubo. [1] mal comportamiento Posteriormente, las modificaciones del cubo Klee-menta han demostrado tanto para otras bases - intercambio de algoritmos de pivote y también para los algoritmos de punto interior. [2]
Descripción del cubo
El cubo de Klee-Minty se especificó originalmente con un sistema parametrizado de desigualdades lineales, con la dimensión como parámetro. Cuando la dimensión es dos, el "cubo" es un cuadrado aplastado. Cuando la dimensión es tres, el "cubo" es un cubo aplastado. Han aparecido ilustraciones del "cubo" además de descripciones algebraicas. [3] [4]
El politopo de Klee-Minty viene dado por [5]
Esto tiene D variables, D limitaciones que no sean los D no-negatividad, y 2 D vértices, al igual que un D -dimensional hipercubo hace. Si la función objetivo a maximizar es
y si el vértice inicial para el algoritmo simplex es el origen, entonces el algoritmo formulado por Dantzig visita todos los vértices 2 D , alcanzando finalmente el vértice óptimo
Complejidad computacional
El cubo de Klee-Minty se ha utilizado para analizar el rendimiento de muchos algoritmos, tanto en el peor de los casos como en el promedio. La complejidad temporal de un algoritmo cuenta el número de operaciones aritméticas suficientes para que el algoritmo resuelva el problema. Por ejemplo, la eliminación gaussiana requiere operaciones del orden de D 3 , por lo que se dice que tiene una complejidad de tiempo polinomial, porque su complejidad está limitada por un polinomio cúbico . Hay ejemplos de algoritmos que no tienen complejidad de tiempo polinomial. Por ejemplo, una generalización de la eliminación gaussiana llamada algoritmo de Buchberger tiene por su complejidad una función exponencial de los datos del problema (el grado de los polinomios y el número de variables de los polinomios multivariados ). Debido a que las funciones exponenciales eventualmente crecen mucho más rápido que las funciones polinomiales, una complejidad exponencial implica que un algoritmo tiene un rendimiento lento en problemas grandes.
Peor de los casos
En optimización matemática, el cubo de Klee-Minty es un ejemplo que muestra la complejidad computacional del peor de los casos de muchos algoritmos de optimización lineal . Es un deformado cubo con exactamente 2 D esquinas en la dimensión D . Klee y Minty demostraron que el algoritmo simplex de Dantzig visita todas las esquinas de un cubo (perturbado) en la dimensión D en el peor de los casos . [1] [6] [7]
Las modificaciones de la construcción de Klee-Minty mostraron una complejidad de tiempo exponencial similar para otras reglas pivotantes de tipo simplex, que mantienen la viabilidad primaria, como la regla de Bland . [8] [9] [10] Otra modificación mostró que el algoritmo entrecruzado , que no mantiene la viabilidad primaria, también visita todas las esquinas de un cubo Klee-Minty modificado. [7] [11] [12] Al igual que el algoritmo simplex, el algoritmo entrecruzado visita las 8 esquinas del cubo tridimensional en el peor de los casos.
Algoritmos de seguimiento de ruta
Otras modificaciones del cubo de Klee-Minty han mostrado un bajo rendimiento de los algoritmos de seguimiento de ruta central para la optimización lineal, ya que la ruta central se acerca arbitrariamente a cada una de las esquinas de un cubo. Este rendimiento de "acecho de vértices" es sorprendente, porque tales algoritmos de seguimiento de ruta tienen una complejidad de tiempo polinomial para la optimización lineal. [3] [13]
Caso medio
El cubo de Klee-Minty también ha inspirado la investigación sobre la complejidad de los casos promedio . Cuando los pivots elegibles se realizan al azar (y no por la regla del descenso más pronunciado), el algoritmo simplex de Dantzig necesita en promedio cuadráticamente muchos pasos ( del orden de O ( D 2 ). [4] Las variantes estándar del algoritmo simplex toman D pasos para un cubo. [14] Cuando se inicializa en una esquina aleatoria del cubo, el algoritmo entrecruzado visita solo D esquinas adicionales, sin embargo, según un artículo de 1994 de Fukuda y Namiki. [15] [16] Ambos el algoritmo simplex y el algoritmo entrecruzado visitan exactamente 3 esquinas adicionales del cubo tridimensional en promedio.
Ver también
- Algoritmo proyectivo de Karmarkar
- Algoritmo elipsoidal de Khachiyan
Notas
- ↑ a b Klee y Minty (1972)
- ^ Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (mayo de 2008). "¿Qué tan buenos son los métodos de puntos interiores? Los cubos de Klee-Minty ajustan los límites de iteración-complejidad". Programación matemática . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . doi : 10.1007 / s10107-006-0044-x . Señor 2367063 . (requiere suscripción) . versión pdf en la página de inicio del profesor Deza .
- ^ a b Error de harvtxt de Deza, Nematollahi y Terlaky (2008) : objetivos múltiples (3 ×): CITEREFDezaNematollahiTerlaky2008 ( ayuda )
- ^ a b Error de harvtxt de Gartner y Ziegler (1994) : objetivos múltiples (2x): CITEREFGartnerZiegler1994 ( ayuda )
- ^ Greenberg, Harvey J., Klee-Minty Polytope muestra la complejidad del tiempo exponencial del método simplex Universidad de Colorado en Denver (1997) Descarga de PDF
- ^ Murty (1983 , 14.2 Complejidad computacional en el peor de los casos, págs. 434–437)
- ↑ a b Terlaky y Zhang (1993)
- ^ Bland, Robert G. (mayo de 1977). "Nuevas reglas de pivote finito para el método simplex". Matemáticas de la investigación operativa . 2 (2): 103–107. doi : 10.1287 / moor.2.2.103 . JSTOR 3689647 . Señor 0459599 .
- ↑ Murty (1983 , Capítulo 10.5, págs. 331–333; problema 14.8, pág. 439) describe la regla de Bland .
- ↑ Murty (1983 , Problema 14.3, p. 438; problema 14.8, p. 439) describe la complejidad del peor de los casos de la regla de Bland.
- ^ Roos (1990)
- ^ Fukuda y Terlaky (1997)
- ^ Megido y Shub (1989)
- ^ De manera más general, para el algoritmo simplex, el número esperado de pasos es proporcional a D para problemas de programación lineal que se extraen aleatoriamente de la esfera unitaria euclidiana , como lo demostraron Borgwardt y Smale .
Borgwardt (1987) : Borgwardt, Karl-Heinz (1987). El método simplex: un análisis probabilístico . Algoritmos y Combinatoria (Textos de Estudio e Investigación). 1 . Berlín: Springer-Verlag. págs. xii + 268. ISBN 978-3-540-17096-9. Señor 0868467 .
- ^ Fukuda y Namiki (1994 , p. 367)
- ^ Fukuda y Terlaky (1997 , p. 385)
Referencias
- Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (mayo de 2008). "¿Qué tan buenos son los métodos de puntos interiores? Los cubos de Klee-Minty ajustan los límites de iteración-complejidad". Programación matemática . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . doi : 10.1007 / s10107-006-0044-x . Señor 2367063 .
- Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre comportamientos extremos del método de índice mínimo de Murty". Programación matemática . 64 (1): 365–370. doi : 10.1007 / BF01582581 . Señor 1286455 .
- Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B . 79 (Artículos del 16º Simposio Internacional de Programación Matemática celebrado en Lausana, 1997): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor 1464775 . Preimpresión posdata .
- Gartner, B .; Ziegler, GM (1994). Algoritmos simplex aleatorizados en cubos Klee-Minty . Fundamentos de la informática, Simposio anual de IEEE sobre . IEEE. págs. 502–510. CiteSeerX 10.1.1.24.1405 . doi : 10.1109 / SFCS.1994.365741 . ISBN 978-0-8186-6580-6.
- Klee, Victor ; Minty, George J. (1972). "¿Qué tan bueno es el algoritmo simplex?". En Shisha, Oved (ed.). Desigualdades III (Actas del Tercer Simposio sobre Desigualdades celebrado en la Universidad de California, Los Ángeles, California, del 1 al 9 de septiembre de 1969, dedicado a la memoria de Theodore S. Motzkin) . Nueva York-Londres: Academic Press. págs. 159-175. Señor 0332165 .
- Meguido, Nimrod ; Shub, Michael (febrero de 1989). "Comportamiento de los límites de los algoritmos de puntos interiores en la programación lineal". Matemáticas de la investigación operativa . 14 (1): 97-146. CiteSeerX 10.1.1.80.184 . doi : 10.1287 / moor.14.1.97 . JSTOR 3689840 . Señor 0984561 .
- Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons. págs. xix + 482. ISBN 978-0-471-09725-9. Señor 0720547 .
- Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método simplex cruzado". Programación matemática . Serie A. 46 (1): 79–84. doi : 10.1007 / BF01585729 . Señor 1045573 .
- Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para la programación lineal: una encuesta sobre los desarrollos teóricos recientes". Anales de investigación operativa . 46–47 (Degeneración en problemas de optimización, número 1): 203–233. CiteSeerX 10.1.1.36.7658 . doi : 10.1007 / BF02096264 . ISSN 0254-5330 . Señor 1260019 .
enlaces externos
Descripción algebraica con ilustración
Los dos primeros enlaces tienen una construcción algebraica y una imagen de un cubo de Klee-Minty tridimensional:
- Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (mayo de 2008). "¿Qué tan buenos son los métodos de puntos interiores? Los cubos de Klee-Minty ajustan los límites de iteración-complejidad". Programación matemática . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . doi : 10.1007 / s10107-006-0044-x . Señor 2367063 . (requiere suscripción) . versión pdf en la página de inicio del profesor Deza .
- Gartner, B .; Ziegler, GM (1994). Algoritmos simplex aleatorizados en cubos Klee-Minty . Fundamentos de la informática, Simposio anual de IEEE sobre . IEEE. págs. 502–510. CiteSeerX 10.1.1.24.1405 . doi : 10.1109 / SFCS.1994.365741 . ISBN 978-0-8186-6580-6. IEEE escribe mal el nombre "Gärnter" como "Gartner" (sic.).
Imágenes sin sistema lineal
- Artículos de E. Nematollahi, que discuten el cubo de Klee-Minty con ilustraciones.
- Una imagen de un cubo de Klee-Minty que muestra una ruta de algoritmo simplex (traducción automática del alemán ) por Günter Ziegler . La imagen de la segunda mitad de la página.