Cubo de menta y klee

Hipercubo unitario de dimensión variable cuyos vértices han sido perturbados

Cubo Klee Minty para el método símplex de vértices de sombra.

El cubo de Klee-Minty o politopo de Klee-Minty (denominado así por Victor Klee y George J. Minty ) es un hipercubo unitario de dimensión variable cuyos vértices han sido perturbados. Klee y Minty demostraron que el algoritmo símplex de George Dantzig tiene un rendimiento deficiente en el peor de los casos cuando se inicializa en un vértice de su "cubo aplastado". En la versión tridimensional, el algoritmo símplex y el algoritmo criss-cross visitan los 8 vértices en el peor de los casos.

En particular, muchos algoritmos de optimización lineal muestran un rendimiento deficiente cuando se aplican al cubo de Klee-Minty. En 1973, Klee y Minty demostraron que el algoritmo símplex de Dantzig no era un algoritmo de tiempo polinomial cuando se aplicaba a su cubo. ^[1] Posteriormente, las modificaciones del cubo de Klee-Minty han mostrado un comportamiento deficiente tanto para otros algoritmos de pivoteo de intercambio de bases como para algoritmos de punto interior. ^[2]

Descripción

El cubo de Klee-Minty se especificó originalmente con un sistema parametrizado de inecuaciones lineales, con la dimensión como parámetro. El cubo en el espacio bidimensional es un cuadrado aplastado y el "cubo" en el espacio tridimensional es un cubo aplastado . Han aparecido ilustraciones del "cubo" además de descripciones algebraicas. ^[3] El politopo de Klee-Minty viene dado por: ^[4] $${\displaystyle {\begin{aligned}x_{1}&\leq 5\\4x_{1}+x_{2}&\leq 25\\8x_{1}+4x_{2}+x_{3}&\leq 125\\&\vdots \\2^{D}x_{1}+2^{D-1}x_{2}+\dots +4x_{D-1}+x_{D}&\leq 5^{D}\\x_{1}\geq 0,\,\,\dots ,\,\,x_{D}&\geq 0.\end{aligned}}}$$

Este tiene variables, restricciones distintas de las restricciones de no negatividad y vértices, tal como lo hace un hipercubo de dimensión . Si la función objetivo que se debe maximizar es y si el vértice inicial para el algoritmo símplex es el origen, entonces el algoritmo formulado por Dantzig visita todos los vértices y finalmente llega al vértice óptimo . ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle 2^{D}}$ ${\displaystyle D}$ $${\displaystyle 2^{D-1}x_{1}+2^{D-2}x_{2}+\dots +2x_{D-1}+x_{D},}$$ ${\displaystyle 2^{D}}$ ${\displaystyle (0,0,\dots ,5^{D})}$

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 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 el orden de las operaciones, y por eso se dice que tiene complejidad temporal polinómica porque su complejidad está limitada por un polinomio cúbico . Hay ejemplos de algoritmos que no tienen complejidad temporal polinómica. Por ejemplo, una generalización de la eliminación gaussiana llamada algoritmo de Buchberger tiene como 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 polinómicas, una complejidad exponencial implica que un algoritmo tiene un rendimiento lento en problemas grandes. ${\displaystyle D^{3}}$

Peor de los casos

Ilustración de un politopo tridimensional que es la región factible de un problema de programación lineal. El algoritmo símplex recorre las aristas entre los vértices hasta llegar a un vértice óptimo. En el caso mostrado, el algoritmo símplex requiere cinco pasos. Sin embargo, el algoritmo símplex visita cada vértice en el peor caso de un problema cuya región factible es el cubo de Klee-Minty, por lo que el número de pasos aumenta exponencialmente con la dimensión del problema.

En optimización matemática, el cubo de Klee-Minty es un ejemplo que muestra la complejidad computacional en el peor de los casos de muchos algoritmos de optimización lineal . Es un cubo deformado con exactamente 2 ^D  esquinas en dimensión . Klee y Minty demostraron que el algoritmo símplex de Dantzig visita todas las esquinas de un cubo (perturbado) en dimensión en el peor de los casos . ^[5] ${\displaystyle D}$ ${\displaystyle D}$

Las modificaciones de la construcción de Klee-Minty mostraron una complejidad temporal exponencial similar para otras reglas de pivote de tipo simplex, que mantienen la viabilidad primaria, como la regla de Bland . ^[6] Otra modificación mostró que el algoritmo criss-cross , que no mantiene la viabilidad primaria, también visita todas las esquinas de un cubo de Klee-Minty modificado. ^[7] Al igual que el algoritmo simplex, el algoritmo criss-cross visita las 8 esquinas del cubo tridimensional en el peor de los casos.

Algoritmos de seguimiento de rutas

Otras modificaciones del cubo de Klee-Minty han demostrado el bajo rendimiento de los algoritmos de seguimiento de la 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 estos algoritmos de seguimiento de rutas tienen una complejidad de tiempo polinomial para la optimización lineal. ^[8]

Caso promedio

El cubo de Klee-Minty también ha inspirado la investigación sobre la complejidad del caso promedio . Cuando los pivotes elegibles se realizan aleatoriamente (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 . ^[9] Las variantes estándar del algoritmo simplex toman en promedio pasos para un cubo. ^[a] Sin embargo, según Fukuda y Namiki (1994), cuando se inicializa en una esquina aleatoria del cubo, el algoritmo criss-cross visita solo esquinas adicionales. ^[11] Tanto el algoritmo simplex como el algoritmo criss-cross visitan exactamente 3 esquinas adicionales del cubo tridimensional en promedio. ${\displaystyle O(D^{2})}$ ${\displaystyle D}$ ${\displaystyle D}$

Véase también

• Algoritmo proyectivo de Karmarkar
• Algoritmo elipsoidal de Khachiyan

Referencias

Notas

1. De manera más general, para el algoritmo simplex, el número esperado de pasos es proporcional a para problemas de programación lineal que se extraen aleatoriamente de la esfera unitaria euclidiana , como lo demostraron Borgwardt y Smale . ^[10] ${\displaystyle D}$

Citas

1. Klee y Minty (1972).
2. Deza, Nematollahi y Terlaky (2008).
3. • Deza, Nematollahi y Terlaky (2008)
   • Gartner y Ziegler (1994)
4. García (1997).
5. • Klee y menta (1972)
   • Murty (1983), 14.2 Complejidad computacional en el peor de los casos, págs. 434–437
   • Terlaky y Zhang (1993)
6. • Bland (1977) Murty (1983), Capítulo 10.5, págs. 331–333; el problema 14.8, pág. 439 describe la regla de Bland .
   • Murty (1983), Problema 14.3, pág. 438; problema 14.8, pág. 439 describe la complejidad del peor caso de la regla de Bland.
7. • Terlaky y Zhang (1993)
   • Gallos (1990)
   • Fukuda y Terlaky (1997)
8. • Deza, Nematollahi y Terlaky (2008)
   • Megido y Shub (1989)
9. Gartner y Ziegler (1994).
10. Borgwardt (1987).
11. • Fukuda y Namiki (1994), pág. 367
    • Fukuda y Terlaky (1997), pág. 385

Bibliografía

• Bland, Robert G. (mayo de 1977). "Nuevas reglas de pivoteo finito para el método símplex". Matemáticas de la investigación de operaciones . 2 (2): 103–107. doi :10.1287/moor.2.2.103. JSTOR  3689647. MR  0459599.
• Borgwardt, Karl-Heinz (1987). El método símplex: un análisis probabilístico . Algoritmos y combinatoria (textos de estudio e investigación). Vol. 1. Berlín: Springer-Verlag. ISBN 978-3-540-17096-9.Sr. 0868467  .
• 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 complejidad de iteración" (PDF) . Programación matemática . 113 (1): 1–14. CiteSeerX  10.1.1.214.111 . doi :10.1007/s10107-006-0044-x. MR  2367063. S2CID  156325.
• Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre los comportamientos extremos del método del índice mínimo de Murty". Programación matemática . 64 (1): 365–370. doi :10.1007/BF01582581. MR  1286455. S2CID  21476636.
• Greenberg, Harvey J. (1997). "El politopo Klee-Minty muestra la complejidad temporal exponencial del método símplex" (PDF) . Universidad de Colorado en Denver.
• Fukuda, Komei ; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos pivote". Programación matemática, Serie B . 79 (Artículos del 16.º Simposio internacional sobre programación matemática celebrado en Lausana, 1997): 369–395. CiteSeerX  10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181. Preimpresión de Postscript.
• Gartner, B.; Ziegler, GM (1994). "Algoritmos símplex aleatorios en cubos Klee-Minty". Actas del 35.º Simposio anual sobre fundamentos de la informática . IEEE. págs. 502–510. CiteSeerX  10.1.1.24.1405 . doi :10.1109/SFCS.1994.365741. ISBN . 978-0-8186-6580-6.S2CID8090478  .​
• Klee, Victor ; Minty, George J. (1972). "¿Qué tan bueno es el algoritmo simplex?". En Shisha, Oved (ed.). Inequalities III (Actas del Tercer Simposio sobre Inequalities 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. MR  0332165.
• Megiddo, Nimrod ; Shub, Michael (febrero de 1989). "Comportamiento en los límites de algoritmos de puntos interiores en programación lineal". Matemáticas de la investigación de operaciones . 14 (1): 97–146. CiteSeerX  10.1.1.80.184 . doi :10.1287/moor.14.1.97. JSTOR  3689840. MR  0984561.
• Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons. pp. xix+482. ISBN 978-0-471-09725-9.Sr. 0720547  .
• Roos, C. (1990). "Un ejemplo exponencial de la regla de pivoteo de Terlaky para el método símplex entrecruzado". Programación matemática . Serie A. 46 (1): 79–84. doi :10.1007/BF01585729. MR  1045573. S2CID  33463483.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para programación lineal: una encuesta sobre desarrollos teóricos recientes". Annals of Operations Research . 46 (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. MR  1260019. S2CID  6058077.

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 complejidad de iteración" (PDF) . Programación matemática . 113 (1): 1–14. CiteSeerX  10.1.1.214.111 . doi :10.1007/s10107-006-0044-x. MR  2367063. S2CID  156325.
• Gartner, B.; Ziegler, GM (1994). "Algoritmos símplex aleatorios en cubos Klee-Minty". Actas del 35.º Simposio anual sobre fundamentos de la informática . IEEE. págs. 502–510. CiteSeerX  10.1.1.24.1405 . doi :10.1109/SFCS.1994.365741. ISBN . 978-0-8186-6580-6. S2CID  8090478. IEEE escribe mal el nombre "Gärnter" como "Gartner" (sic.).

Imágenes sin sistema lineal

• Artículos de E. Nematollahi, que tratan el cubo Klee-Minty con ilustraciones.
• Imagen de un cubo de Klee-Minty que muestra una ruta de algoritmo simplex (traducción automática del alemán) de Günter Ziegler . La imagen se encuentra en la segunda mitad de la página.