Algoritmo entrecruzado
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Este artículo trata sobre un algoritmo de optimización matemática. Para otros usos, consulte Criss-cross .

Un cubo tridimensional
El algoritmo entrecruzado visita las 8 esquinas del cubo de Klee-Minty en el peor de los casos. Visita 3 rincones adicionales en promedio. El cubo de Klee-Minty es una perturbación del cubo que se muestra aquí.

En optimización matemática , el algoritmo entrecruzado es cualquiera de una familia de algoritmos para programación lineal . Las variantes del algoritmo entrecruzado también resuelven problemas más generales con restricciones de desigualdad lineal y funciones objetivas no lineales ; existen algoritmos entrecruzados para problemas de programación lineal-fraccional , [1] [2] problemas de programación cuadrática y problemas de complementariedad lineal . [3]

Al igual que el algoritmo simplex de George B. Dantzig , el algoritmo entrecruzado no es un algoritmo de tiempo polinomial para la programación lineal. Ambos algoritmos visitan todas las  esquinas 2 D de un cubo (perturbado) en la dimensión  D , el cubo de Klee-Minty (después de Victor Klee y George J. Minty ), en el peor de los casos . [4] [5] Sin embargo, cuando se inicia en una esquina aleatoria, el algoritmo entrecruzado visita en promedio solo  D esquinas adicionales. [6] [7] [8] Por lo tanto, para el cubo tridimensional, el algoritmo visita las 8 esquinas en el peor de los casos y exactamente 3 esquinas adicionales en promedio.

Historia

El algoritmo entrecruzado fue publicado de forma independiente por Tamas Terlaky [9] y por Zhe-Min Wang; [10] algoritmos relacionados aparecieron en informes no publicados de otros autores. [3]

Comparación con el algoritmo simplex para optimización lineal

Ver también: programación lineal , algoritmo Simplex y regla de Bland
En su segunda fase, el algoritmo simplex se arrastra a lo largo de los bordes del politopo hasta que finalmente alcanza un vértice óptimo . El algoritmo entrecruzado considera bases que no están asociadas con vértices, de modo que algunas iteraciones pueden estar en el interior de la región factible, como algoritmos de punto interior; el algoritmo entrecruzado también puede tener iteraciones inviables fuera de la región factible.

En la programación lineal, el algoritmo entrecruzado pivota entre una secuencia de bases pero difiere del algoritmo simplex de George Dantzig . El algoritmo simplex primero encuentra una base (primaria) factible resolviendo un " problema de fase uno "; en la "fase dos", el algoritmo simplex pivota entre una secuencia de soluciones factibles básicas para que la función objetivo no disminuya con cada pivote, terminando con una solución óptima (también encontrando finalmente una solución "factible dual"). [3] [11]

El algoritmo entrecruzado es más simple que el algoritmo simplex, porque el algoritmo entrecruzado solo tiene una fase. Sus reglas pivotantes son similares a la regla pivotante de índice mínimo de Bland . [12] La regla de Bland usa solo signos de coeficientes en lugar de su orden (número real) al decidir pivotes elegibles. La regla de Bland selecciona una variable de entrada comparando valores de costos reducidos, usando el orden de números reales de los pivotes elegibles. [12] [13] A diferencia de la regla de Bland, el algoritmo entrecruzado es "puramente combinatorio", seleccionando una variable de entrada y una variable de salida considerando solo los signos de los coeficientes en lugar de su orden de números reales. [3] [11]El algoritmo entrecruzado se ha aplicado para proporcionar pruebas constructivas de resultados básicos en álgebra lineal , como el lema de Farkas . [14]

Si bien la mayoría de las variantes simplex son monótonas en el objetivo (estrictamente en el caso no degenerado), la mayoría de las variantes del algoritmo entrecruzado carecen de una función de mérito monótona que puede ser una desventaja en la práctica.

Descripción

El algoritmo entrecruzado funciona en un cuadro dinámico estándar (o partes calculadas sobre la marcha de un cuadro, si se implementa como el método simplex revisado). En un paso general, si el cuadro es primario o doble inviable, selecciona una de las filas / columnas inviables como fila / columna dinámica usando una regla de selección de índice. Una propiedad importante es que la selección se realiza sobre la unión de los índices inviables y la versión estándar del algoritmo no distingue los índices de columna y fila (es decir, los índices de columna básicos en las filas). Si se selecciona una fila, el algoritmo utiliza la regla de selección de índice para identificar una posición en un pivote de tipo dual, mientras que si se selecciona una columna, utiliza la regla de selección de índice para encontrar una posición de fila y realiza un pivote de tipo primario.

Complejidad computacional: casos peores y promedio

La complejidad computacional del peor de los casos del algoritmo elipsoidal de Khachiyan es un polinomio. El algoritmo entrecruzado tiene una complejidad exponencial.

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 delpolinomios 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.

Varios algoritmos para lineal programación- Khachiyan 's elipsoidal algoritmo , Karmarkar ' s algoritmo proyectiva , y algoritmos de camino central -tienen polinomio de tiempo-complejidad (en el peor de los casos y por lo tanto en promedio ). Los algoritmos elipsoidales y proyectivos se publicaron antes que el algoritmo cruzado.

Sin embargo, al igual que el algoritmo simplex de Dantzig, el algoritmo entrecruzado no es un algoritmo de tiempo polinomial para la programación lineal. El algoritmo entrecruzado de Terlaky visita todas las  esquinas bidimensionales de un cubo (perturbado) en la dimensión  D , según un artículo de Roos; El artículo de Roos modifica la construcción de Klee- Minty de un cubo en el que el algoritmo simplex da  pasos en 2 D. [3] [4] [5] Al igual que el algoritmo simplex, el algoritmo entrecruzado visita las 8 esquinas del cubo tridimensional en el peor de los casos.

Sin embargo, cuando se inicializa en una esquina aleatoria del cubo, el algoritmo entrecruzado visita solo  D esquinas adicionales, según un artículo de 1994 de Fukuda y Namiki. [6] [7] Trivialmente, el algoritmo simplex toma en promedio  D pasos para un cubo. [8] [15] Al igual que el algoritmo simplex, el algoritmo entrecruzado visita exactamente 3 esquinas adicionales del cubo tridimensional en promedio.

Variantes

El algoritmo entrecruzado se ha ampliado para resolver problemas más generales que los problemas de programación lineal.

Otros problemas de optimización con restricciones lineales

Hay variantes del algoritmo entrecruzado para la programación lineal, para la programación cuadrática y para el problema de la complementariedad lineal con "matrices suficientes"; [3] [6] [16] [17] [18] [19] a la inversa, para problemas de complementariedad lineal, el algoritmo entrecruzado termina finitamente sólo si la matriz es una matriz suficiente. [18] [19] Una matriz suficiente es una generalización tanto de una matriz definida positiva como de una matriz P , cuyos principales menores son cada uno positivo. [18] [19] [20]El algoritmo entrecruzado también se ha adaptado para la programación lineal-fraccional . [1] [2]

Enumeración de vértices

El algoritmo entrecruzado se utilizó en un algoritmo para enumerar todos los vértices de un politopo , que fue publicado por David Avis y Komei Fukuda en 1992. [21] Avis y Fukuda presentaron un algoritmo que encuentra los  vértices v de un poliedro definido por un sistema no degenerado de  n desigualdades lineales en  dimensiones D (o, dualmente, las  v facetas del casco convexo de  n puntos en  dimensiones D , donde cada faceta contiene exactamente  D puntos dados) en el tiempo  O ( nDv ) y O ( nD ) espacio . [22]

Matroides orientadas

El teorema de corte mínimo de flujo máximo establece que el flujo máximo a través de una red es exactamente la capacidad de su corte mínimo. Este teorema se puede demostrar usando el algoritmo entrecruzado para matroides orientados.

El algoritmo entrecruzado a menudo se estudia utilizando la teoría de matroides orientadas (OM), que es una abstracción combinatoria de la teoría de optimización lineal. [17] [23] De hecho, la regla pivotante de Bland se basó en sus trabajos anteriores sobre la teoría de la matroide orientada. Sin embargo, la regla de Bland exhibe ciclos en algunos problemas de programación lineal de matroides orientados. [17] El primer algoritmo puramente combinatorio para la programación lineal fue ideado por Michael J. Todd . [17] [24] El algoritmo de Todd se desarrolló no solo para programación lineal en el contexto de matroides orientadas, sino también para problemas de programación cuadrática yproblemas de complementariedad lineal . [17] [24] El algoritmo de Todd es complicado incluso de enunciar, desafortunadamente, y sus pruebas de convergencia finita son algo complicadas. [17]

El algoritmo entrecruzado y su prueba de terminación finita se pueden enunciar de forma sencilla y ampliar fácilmente la configuración de las matroides orientadas. El algoritmo se puede simplificar aún más para problemas de viabilidad lineal , es decir, para sistemas lineales con variables no negativas ; estos problemas pueden formularse para matroides orientados. [14] El algoritmo entrecruzado ha sido adaptado para problemas que son más complicados que la programación lineal: Hay variantes de matroides orientadas también para el problema de programación cuadrática y para el problema de complementariedad lineal. [3] [16] [17]

Resumen

El algoritmo entrecruzado es un algoritmo establecido de forma sencilla para la programación lineal. Fue el segundo algoritmo completamente combinatorio para programación lineal. El algoritmo simplex parcialmente combinatorio de los ciclos de Bland en algunas matroides orientadas (no realizables). El primer algoritmo completamente combinatorio fue publicado por Todd, y también es como el algoritmo simplex en el sentido de que conserva la viabilidad después de que se genera la primera base factible; sin embargo, la regla de Todd es complicada. El algoritmo entrecruzado no es un algoritmo similar al simplex, porque no necesita mantener la viabilidad. Sin embargo, el algoritmo entrecruzado no tiene complejidad de tiempo polinomial.

Los investigadores han ampliado el algoritmo entrecruzado para muchos problemas de optimización, incluida la programación lineal-fraccional. El algoritmo entrecruzado puede resolver problemas de programación cuadrática y problemas de complementariedad lineal, incluso en el contexto de matroides orientados. Incluso cuando se generaliza, el algoritmo entrecruzado permanece enunciado de manera simple.

Ver también

  • Jack Edmonds (pionero de la optimización combinatoria y teórico de la matriz orientada; asesor de doctorado de Komei Fukuda)

Notas

  1. ↑ a b Illés, Szirmai y Terlaky (1999)
  2. ↑ a b Stancu-Minasian, I. M. (agosto de 2006). "Una sexta bibliografía de programación fraccionada". Optimización . 55 (4): 405–428. doi : 10.1080 / 02331930600819613 . Señor  2258634 . S2CID  62199788 .
  3. ↑ a b c d e f g Fukuda y Terlaky (1997)
  4. ↑ a b Roos (1990)
  5. ^ a b 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 . 
  6. ↑ a b c Fukuda y Terlaky (1997 , p. 385)
  7. ↑ a b Fukuda y Namiki (1994 , p. 367)
  8. ^ a b El algoritmo simplex toma en promedio  D pasos para un cubo. 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 .
  9. ^ Terlaky (1985) y Terlaky (1987)
  10. ↑ Wang (1987)
  11. ↑ a b Terlaky y Zhang (1993)
  12. ↑ a b 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 .  
  13. ↑ La regla de Bland también está relacionada con una regla de índice mínimo anterior, que fue propuesta por Katta G. Murty para el problema de complementariedad lineal , según Fukuda & Namiki (1994) .
  14. ↑ a b Klafszky y Terlaky (1991)
  15. ^ 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 .
  16. ↑ a b Fukuda y Namiki (1994)
  17. ^ a b c d e f g Björner, Anders; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). "10 Programación lineal". Matroides orientadas . Prensa de la Universidad de Cambridge. págs. 417–479. doi : 10.1017 / CBO9780511586507 . ISBN 978-0-521-77750-6. Señor  1744046 .
  18. ^ a b c den Hertog, D .; Roos, C .; Terlaky, T. (1 de julio de 1993). "El problema de la complementariedad lineal, matrices suficientes y el método entrecruzado" (PDF) . Álgebra lineal y sus aplicaciones . 187 : 1-14. doi : 10.1016 / 0024-3795 (93) 90124-7 .
  19. ^ a b c Csizmadia, Zsolt; Illés, Tibor (2006). "Nuevos algoritmos de tipo cruzado para problemas de complementariedad lineal con matrices suficientes" (pdf) . Métodos y software de optimización . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . Señor 2195759 . S2CID 24418835 .   
  20. ^ Cottle, RW ; Pang, J.-S .; Venkateswaran, V. (marzo-abril de 1989). "Matrices suficientes y el problema de la complementariedad lineal" . Álgebra lineal y sus aplicaciones . 114-115: 231-249. doi : 10.1016 / 0024-3795 (89) 90463-1 . Señor 0986877 . 
  21. ^ Avis y Fukuda (1992 , p. 297)
  22. ^ Los  v vértices en una disposición simple de  n hiperplanos en dimensiones D se pueden encontrar en la complejidad del tiempoO ( n 2 Dv ) y del espacio O ( nD ).
  23. ↑ La teoría de las matroides orientadas fue iniciada por R. Tyrrell Rockafellar . ( Rockafellar 1969 ):

    Rockafellar, RT (1969). "Los vectores elementales de un subespacio de (1967)" R norte {\ Displaystyle R ^ {N}} (PDF) . En RC Bose y TA Dowling (ed.). Matemática combinatoria y sus aplicaciones . Serie de monografías de probabilidad y estadística de la Universidad de Carolina del Norte. Chapel Hill, Carolina del Norte: Prensa de la Universidad de Carolina del Norte. págs. 104-127. Señor  0278972 . Reimpresión de PDF .

    Rockafellar fue influenciado por los estudios anteriores de Albert W. Tucker y George J. Minty . Tucker y Minty habían estudiado los patrones de signos de las matrices que surgen a través de las operaciones pivotantes del algoritmo simplex de Dantzig.

  24. ↑ a b Todd, Michael J. (1985). "Programación lineal y cuadrática en matroides orientadas" . Revista de teoría combinatoria . Serie B 39 (2): 105-133. doi : 10.1016 / 0095-8956 (85) 90042-5 . Señor 0811116 . 

Referencias

  • Avis, David ; Fukuda, Komei (diciembre de 1992). "Un algoritmo pivotante para cascos convexos y enumeración de vértices de arreglos y poliedros" . Geometría discreta y computacional . 8 (Simposio ACM sobre geometría computacional (North Conway, NH, 1991) número 1): 295–313. doi : 10.1007 / BF02293050 . Señor  1174359 .
  • Csizmadia, Zsolt; Illés, Tibor (2006). "Nuevos algoritmos de tipo cruzado para problemas de complementariedad lineal con matrices suficientes" (pdf) . Métodos y software de optimización . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . Señor  2195759 . S2CID  24418835 .
  • 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 . S2CID  21476636 .
  • Fukuda, Komei ; Terlaky, Tamás (1997). Liebling, Thomas M .; de Werra, Dominique (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, números 1-3): 369–395. CiteSeerX  10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor  1464775 . S2CID  2794181 . Preimpresión posdata .
  • den Hertog, D .; Roos, C .; Terlaky, T. (1 de julio de 1993). "El problema de la complementariedad lineal, matrices suficientes y el método entrecruzado" (PDF) . Álgebra lineal y sus aplicaciones . 187 : 1-14. doi : 10.1016 / 0024-3795 (93) 90124-7 . Señor  1221693 .
  • Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "El método entrecruzado finito para la programación hiperbólica" . Revista europea de investigación operativa . 114 (1): 198-214. doi : 10.1016 / S0377-2217 (98) 00049-6 . Zbl  0953.90055 . Preimpresión posdata .
  • Klafszky, Emil; Terlaky, Tamás (junio de 1991). "El papel de pivotar en la demostración de algunos teoremas fundamentales del álgebra lineal" . Álgebra lineal y sus aplicaciones . 151 : 97-118. doi : 10.1016 / 0024-3795 (91) 90356-2 . Señor  1102142 .
  • 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 . S2CID  33463483 .
  • Terlaky, T. (1985). "Un método cruzado convergente". Optimización: una revista de programación matemática e investigación de operaciones . 16 (5): 683–690. doi : 10.1080 / 02331938508843067 . ISSN  0233-1934 . Señor  0798939 .
  • Terlaky, Tamás (1987). "Un método entrecruzado finito para matroides orientados" . Revista de teoría combinatoria . Serie B 42 (3): 319–327. doi : 10.1016 / 0095-8956 (87) 90049-9 . ISSN  0095-8956 . Señor  0888684 .
  • Terlaky, Tamás ; Zhang, Shu Zhong (1993) [1991]. "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 . S2CID  6058077 .
  • Wang, Zhe Min (1987). "Un algoritmo libre de eliminación conforme finito sobre programación matroide orientada". Anales chinos de matemáticas (Shuxue Niankan B Ji) . Serie B. 8 (1): 120-125. ISSN  0252-9599 . Señor  0886756 .

enlaces externos

  • Komei Fukuda (ETH Zentrum, Zurich) con publicaciones
  • Tamás Terlaky (Lehigh University) con publicaciones
Obtenido de " https://en.wikipedia.org/w/index.php?title=Criss-cross_algorithm&oldid=1032277410 "
Contribute a better translation