Método elipsoide - Ellipsoid method

En optimización matemática , el método elipsoide es un método iterativo para minimizar funciones convexas . Cuando se especializa en resolver problemas de optimización lineal factibles con datos racionales, el método elipsoide es un algoritmo que encuentra una solución óptima en un número de pasos que es polinomial en el tamaño de entrada.

El método del elipsoide genera una secuencia de elipsoides cuyo volumen disminuye uniformemente en cada paso, encerrando así un minimizador de una función convexa .

Historia

El método elipsoide tiene una larga historia. Como método iterativo , Naum Z. Shor introdujo una versión preliminar . En 1972, Arkadi Nemirovski y David B. Yudin (Judin) estudiaron un algoritmo de aproximación para la minimización convexa real . Como algoritmo para resolver problemas de programación lineal con datos racionales, Leonid Khachiyan estudió el algoritmo elipsoide ; El logro de Khachiyan fue demostrar la solubilidad en tiempo polinomial de los programas lineales. Este fue un paso notable desde una perspectiva teórica: el algoritmo estándar para resolver problemas lineales en ese momento era el algoritmo simplex , que tiene un tiempo de ejecución que * típicamente * es lineal en el tamaño del problema, pero para el cual existen ejemplos para los cuales es * exponencial * en el tamaño del problema. Como tal, tener un algoritmo que está * garantizado * como polinomio para todos los casos parecía un avance teórico.

El trabajo de Khachiyan mostró, por primera vez, que puede haber algoritmos para resolver programas lineales cuyo tiempo de ejecución se puede demostrar que es polinomial. En la práctica, sin embargo, el algoritmo es bastante lento y de poco interés práctico, aunque sirvió de inspiración para trabajos posteriores que resultaron ser de mucho mayor uso práctico. Específicamente, el algoritmo de Karmarkar , un método de punto interior , es mucho más rápido que el método elipsoide en la práctica. El algoritmo de Karmarkar también es más rápido en el peor de los casos.

El algoritmo elipsoidal permite a los teóricos de la complejidad lograr límites (en el peor de los casos) que dependen de la dimensión del problema y del tamaño de los datos, pero no del número de filas, por lo que siguió siendo importante en la teoría de la optimización combinatoria durante muchos años. Solo en el siglo XXI aparecieron algoritmos de punto interior con propiedades de complejidad similares.

Descripción

Un problema de minimización convexa consta de los siguientes ingredientes.

• Una función convexa que se minimizará sobre el vector (que contiene n variables); ${\ Displaystyle f_ {0} (x): \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ Displaystyle x}$
• Restricciones de desigualdad convexa de la forma , donde las funciones son convexas; estas restricciones definen un conjunto convexo . ${\ Displaystyle f_ {i} (x) \ leqslant 0}$${\ Displaystyle f_ {i}}$ ${\ displaystyle Q}$
• Restricciones de igualdad lineal de la forma . ${\ Displaystyle h_ {i} (x) = 0}$

También se nos da un elipsoide inicial definido como ${\ Displaystyle {\ mathcal {E}} ^ {(0)} \ subset \ mathbb {R} ^ {n}}$

${\ Displaystyle {\ mathcal {E}} ^ {(0)} = \ left \ {z \ in \ mathbb {R} ^ {n} \: \ (z-x_ {0}) ^ {T} P_ { (0)} ^ {- 1} (z-x_ {0}) \ leqslant 1 \ right \}}$

que contiene un minimizador , donde y es el centro de . ${\ Displaystyle x ^ {*}}$${\ Displaystyle P _ {(0)} \ succ 0}$${\ Displaystyle x_ {0}}$${\ Displaystyle {\ mathcal {E}}}$

Finalmente, requerimos la existencia de un oráculo de plano de corte (también llamado oráculo de separación ) para el conjunto convexo . Dado un punto , el oráculo debería devolver una de dos respuestas: ${\ displaystyle Q}$${\ Displaystyle x \ in \ mathbb {R} ^ {n}}$

• "El punto está en ", o - ${\ Displaystyle x}$${\ displaystyle Q}$
• “El punto está en no adentro , y además, aquí hay un hiperplano que se separa de ”, es decir, un vector tal que para todos . ${\ Displaystyle x}$${\ displaystyle Q}$${\ Displaystyle x}$${\ displaystyle Q}$${\ Displaystyle c}$${\ Displaystyle c \ cdot x <c \ cdot y}$${\ Displaystyle y \ in Q}$

Un ejemplo de un oráculo de plano de corte viene dado por un subgradiente g de f .

Aplicación a la programación lineal

En el contexto de la programación lineal, las restricciones son todas lineales y es un politopo convexo . Entonces, el oráculo de separación se puede implementar fácilmente de la siguiente manera. Dadas las restricciones y un punto , el oráculo simplemente calcula : ${\ displaystyle Q}$${\ Displaystyle Q = \ {x | Ax \ leq b \}}$${\ Displaystyle x \ in \ mathbb {R} ^ {n}}$${\ Displaystyle Ax}$

• Si el resultado es como máximo , entonces está dentro ; ${\ Displaystyle b}$${\ Displaystyle x}$${\ displaystyle Q}$
• De lo contrario, hay al menos una fila de A , que es mayor que el valor correspondiente en ; esta fila nos da el hiperplano separador. ${\ Displaystyle c}$${\ Displaystyle c \ cdot x}$${\ Displaystyle b}$${\ Displaystyle c}$

Este oráculo se ejecuta en tiempo polinomial siempre que el número de restricciones sea polinomial. En algunos problemas de optimización lineal, aunque el número de restricciones es exponencial, todavía se puede escribir un oráculo de separación personalizado que funcione en tiempo polinomial. Dos ejemplos son:

• El problema de arborescencia de costo mínimo : dado un grafo dirigido ponderado y un vértice r en él, encuentre un subgrafo de costo mínimo que contenga un camino dirigido desde r hasta cualquier otro vértice. El problema se puede presentar como un LP con una restricción para cada subconjunto de vértices, que es un número exponencial de restricciones. Sin embargo, se puede implementar un oráculo de separación utilizando n -1 aplicaciones del procedimiento de corte mínimo .
• El problema del conjunto independiente máximo . Puede aproximarse mediante un LP con una restricción para cada ciclo de longitud impar. Si bien hay exponencialmente muchos de esos ciclos, un oráculo de separación que funcione en tiempo polinomial se puede implementar simplemente encontrando un ciclo impar de duración mínima.

La salida del método elipsoide es:

• Cualquier punto del politopo (es decir, cualquier punto factible), o - ${\ displaystyle Q}$
• Una prueba que está vacía. ${\ displaystyle Q}$

La minimización restringida por la desigualdad de una función que es cero en todas partes corresponde al problema de simplemente identificar cualquier punto factible. Resulta que cualquier problema de programación lineal puede reducirse a un problema de viabilidad lineal (por ejemplo, minimizar la función cero sujeta a algunas restricciones de desigualdad e igualdad lineales). Una forma de hacer esto es combinando los programas lineales primarios y duales en un solo programa, y ​​agregando la restricción adicional (lineal) de que el valor de la solución primaria no es peor que el valor de la solución dual. Otra forma es tratar el objetivo del programa lineal como una restricción adicional y usar la búsqueda binaria para encontrar el valor óptimo.

Minimización sin restricciones

En la k -ésima iteración del algoritmo, tenemos un punto en el centro de un elipsoide ${\ Displaystyle x ^ {(k)}}$

${\ Displaystyle {\ mathcal {E}} ^ {(k)} = \ left \ {x \ in \ mathbb {R} ^ {n} \: \ \ left (xx ^ {(k)} \ right) ^ {T} P _ {(k)} ^ {- 1} \ left (xx ^ {(k)} \ right) \ leqslant 1 \ right \}.}$

Consultamos el oráculo del plano de corte para obtener un vector tal que ${\ Displaystyle g ^ {(k + 1)} \ in \ mathbb {R} ^ {n}}$

${\ Displaystyle g ^ {(k + 1) T} \ left (x ^ {*} - x ^ {(k)} \ right) \ leqslant 0.}$

Por tanto, concluimos que

${\ Displaystyle x ^ {*} \ in {\ mathcal {E}} ^ {(k)} \ cap \ left \ {z \: \ g ^ {(k + 1) T} \ left (zx ^ {( k)} \ right) \ leqslant 0 \ right \}.}$

Establecemos que sea el elipsoide de volumen mínimo que contiene el semielipsoide descrito anteriormente y calculamos . La actualización viene dada por ${\ Displaystyle {\ mathcal {E}} ^ {(k + 1)}}$${\ Displaystyle x ^ {(k + 1)}}$

${\ Displaystyle {\ begin {alineado} x ^ {(k + 1)} & = x ^ {(k)} - {\ frac {1} {n + 1}} P _ {(k)} {\ tilde { g}} ^ {(k + 1)} \\ P _ {(k + 1)} & = {\ frac {n ^ {2}} {n ^ {2} -1}} \ left (P _ {(k )} - {\ frac {2} {n + 1}} P _ {(k)} {\ tilde {g}} ^ {(k + 1)} {\ tilde {g}} ^ {(k + 1) T} P _ {(k)} \ right) \ end {alineado}}}$

dónde

${\ Displaystyle {\ tilde {g}} ^ {(k + 1)} = \ left ({\ frac {1} {\ sqrt {g ^ {(k + 1) T} P _ {(k)} g ^ {(k + 1)}}}} \ right) g ^ {(k + 1)}.}$

El criterio de parada viene dado por la propiedad que

${\ Displaystyle {\ sqrt {g ^ {(k) T} P _ {(k)} g ^ {(k)}}} \ leqslant \ epsilon \ quad \ Rightarrow \ quad f \ left (x ^ {(k) } \ derecha) -f \ izquierda (x ^ {*} \ derecha) \ leqslant \ epsilon.}$

Muestra de secuencia de iteraciones

${\ Displaystyle k = 0}$	${\ Displaystyle k = 1}$	${\ Displaystyle k = 2}$
${\ Displaystyle k = 3}$	${\ Displaystyle k = 4}$	${\ Displaystyle k = 5}$

Minimización restringida por desigualdad

En la k -ésima iteración del algoritmo de minimización restringida, tenemos un punto en el centro de un elipsoide como antes. También debemos mantener una lista de valores que registren el valor objetivo más pequeño de iteraciones factibles hasta el momento. Dependiendo de si el punto es factible o no , realizamos una de dos tareas: ${\ Displaystyle x ^ {(k)}}$${\ Displaystyle {\ mathcal {E}} ^ {(k)}}$${\ displaystyle f _ {\ rm {mejor}} ^ {(k)}}$${\ Displaystyle x ^ {(k)}}$

• Si es factible, realice esencialmente la misma actualización que en el caso sin restricciones, eligiendo un subgrado que satisfaga ${\ Displaystyle x ^ {(k)}}$${\ Displaystyle g_ {0}}$

${\ Displaystyle g_ {0} ^ {T} \ left (x ^ {*} - x ^ {(k)} \ right) + f_ {0} \ left (x ^ {(k)} \ right) -f_ {\ rm {mejor}} ^ {(k)} \ leqslant 0}$

• Si no es factible y viola la j -ésima restricción, actualice el elipsoide con un corte de factibilidad. Nuestro recorte de viabilidad puede ser un subgrado del cual debe satisfacer ${\ Displaystyle x ^ {(k)}}$${\ Displaystyle g_ {j}}$${\ Displaystyle f_ {j}}$

${\ Displaystyle g_ {j} ^ {T} \ left (zx ^ {(k)} \ right) + f_ {j} \ left (x ^ {(k)} \ right) \ leqslant 0}$

para todo z factible .

Actuación

El método elipsoide se utiliza en problemas de baja dimensión, como problemas de ubicación plana, donde es numéricamente estable . Incluso en problemas de tamaño "pequeño", sufre inestabilidad numérica y un rendimiento deficiente en la práctica.

Sin embargo, el método elipsoide es una técnica teórica importante en la optimización combinatoria . En la teoría de la complejidad computacional , el algoritmo elipsoide es atractivo porque su complejidad depende del número de columnas y del tamaño digital de los coeficientes, pero no del número de filas. En el siglo XXI han aparecido algoritmos de puntos interiores con propiedades similares.

Notas

Otras lecturas

• Dmitris Alevras y Manfred W. Padberg, Optimización lineal y extensiones: problemas y extensiones , Universitext, Springer-Verlag, 2001 (Problemas de Padberg con soluciones).
• V. Chandru y MRRao, Linear Programming, Capítulo 31 en Algorithms and Theory of Computation Handbook , editado por MJAtallah, CRC Press 1999, 31-1 a 31-37.
• V. Chandru y MRRao, Integer Programming, Capítulo 32 en Algorithms and Theory of Computation Handbook , editado por MJAtallah, CRC Press 1999, 32-1 a 32-45.
• George B. Dantzig y Mukund N. Thapa. 1997. Programación lineal 1: Introducción . Springer-Verlag.
• George B. Dantzig y Mukund N. Thapa. 2003. Programación Lineal 2: Teoría y Extensiones . Springer-Verlag.
• L. Lovász : Una teoría algorítmica de números, gráficos y convexidad , serie de conferencias regionales CBMS-NSF en matemáticas aplicadas 50, SIAM, Filadelfia, Pensilvania, 1986
• Kattta G. Murty, Programación lineal , Wiley, 1983.
• M. Padberg , Optimización lineal y extensiones , segunda edición, Springer-Verlag, 1999.
• Christos H. Papadimitriou y Kenneth Steiglitz, Optimización combinatoria: algoritmos y complejidad , Reedición corregida con un nuevo prefacio, Dover.
• Alexander Schrijver , Teoría de la programación lineal y entera . John Wiley e hijos, 1998, ISBN   0-471-98232-6

enlaces externos

• EE364b , una página de inicio de cursos de Stanford