Método del elipsoide

En optimización matemática , el método del elipsoide es un método iterativo para minimizar funciones convexas sobre conjuntos convexos . 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 .

Cuando se especializa en resolver problemas factibles de optimización lineal con datos racionales, el método del 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 tiene una larga historia. Naum Z. Shor introdujo una versión preliminar como método iterativo . 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, el algoritmo del elipsoide fue estudiado por Leonid Khachiyan ; el logro de Khachiyan fue demostrar la resolubilidad en tiempo polinómico 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 símplex , que tiene un tiempo de ejecución que normalmente es lineal en el tamaño del problema, pero para el cual existen ejemplos para los que es exponencial en el tamaño del problema. Como tal, tener un algoritmo que se garantiza que sea polinómico para todos los casos fue un gran avance teórico.

El trabajo de Khachiyan demostró, por primera vez, que pueden existir algoritmos para resolver programas lineales cuyo tiempo de ejecución puede demostrarse que es polinómico. En la práctica, sin embargo, el algoritmo es bastante lento y de poco interés práctico, aunque proporcionó inspiración para trabajos posteriores que resultaron ser de mucha mayor utilidad práctica. En concreto, el algoritmo de Karmarkar , un método de puntos interiores , es mucho más rápido que el método del 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 optimización combinatoria durante muchos años. ^{[1] [2] [3] [4]} Solo en el siglo XXI aparecieron algoritmos de punto interior con propiedades de complejidad similares. ^{[ cita requerida ]}

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} }$${\estilo de visualización 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}$$estilo de visualización f_{i}}$ ${\estilo de visualización 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)}\subconjunto \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 .${\estilo de visualización x^{*}}$${\displaystyle P_{(0)}\succ 0}$$estilo de visualización x_{0}}$${\displaystyle {\mathcal {E}}}$

Por último, necesitamos la existencia de un oráculo de separación para el conjunto convexo . Dado un punto , el oráculo debería devolver una de dos respuestas: ^[5]${\estilo de visualización Q}$${\displaystyle x\in \mathbb {R} ^{n}}$

• "El punto está en ", o -${\estilo de visualización x}$${\estilo de visualización Q}$
• "El punto no está en , y además, aquí hay un hiperplano que se separa de ", es decir, un vector tal que para todo .${\estilo de visualización x}$${\estilo de visualización Q}$${\estilo de visualización x}$${\estilo de visualización Q}$${\estilo de visualización c}$${\displaystyle c\cdot x<c\cdot y}$${\displaystyle y\en Q}$

La salida del método del elipsoide es:

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

La minimización de una función que es cero en todas partes, con restricciones de desigualdad, corresponde al problema de simplemente identificar cualquier punto factible. Resulta que cualquier problema de programación lineal puede reducirse a un problema de factibilidad lineal (por ejemplo, minimizar la función cero sujeta a algunas restricciones de desigualdad e igualdad lineales). Una forma de hacerlo es combinando los programas lineales primarios y duales en un solo programa, y ​​agregando la restricción (lineal) adicional de que el valor de la solución primaria no sea 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. ^{[ cita requerida ]}

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 al 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 lo tanto concluimos que

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

Fijamos 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{aligned}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{aligned}}}$

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 detención viene dado por la propiedad que

${\displaystyle {\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .}$

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 registre 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 posible, realice esencialmente la misma actualización que en el caso sin restricciones, eligiendo un subgradiente que satisfaga${\displaystyle x^{(k)}}$$estilo de visualización g_{0}$

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

• Si es inviable y viola la restricción j -ésima, actualice el elipsoide con un corte de factibilidad. Nuestro corte de factibilidad puede ser un subgradiente del cual debe satisfacer${\displaystyle x^{(k)}}$$estilo de visualización g_ {j}}$$estilo de visualización f_ {j}}$

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

para todos los z posibles .

La garantía de complejidad en tiempo de ejecución del método elipsoide en el modelo RAM real está dada por el siguiente teorema. ^{[6] : Teorema 8.3.1}

Consideremos una familia de problemas de optimización convexa de la forma: minimizar f ( x ) st x está en G , donde f es una función convexa y G es un conjunto convexo (un subconjunto de un espacio euclidiano R ⁿ ). Cada problema p en la familia está representado por un vector de datos Data( p ), por ejemplo, los coeficientes de valor real en matrices y vectores que representan la función f y la región factible G . El tamaño de un problema p , Size( p ), se define como el número de elementos (números reales) en Data( p ). Se necesitan los siguientes supuestos:

1. G (la región factible) es:
   • Encerrado;
   • Tiene un interior no vacío (por lo que hay un punto estrictamente factible);
2. Dados los datos ( p ), se pueden calcular utilizando operaciones aritméticas poli(Tamaño(p)):
   • Un elipsoide que contiene G ;
   • Un límite inferior MinVol(p ) >0 en el volumen de G.
3. Dados datos ( p ) y un punto x en R ⁿ , se pueden calcular utilizando operaciones aritméticas poli(Tamaño(p)):
   • Un oráculo de separación para G (es decir: afirmar que x está en G o devolver un hiperplano que separa x de G ).
   • Un oráculo de primer orden para f (es decir: calcular el valor de f ( x ) y un subgradiente f' ( x )).

Bajo estos supuestos, el método del elipsoide es "R-polinomial". Esto significa que existe un polinomio Poly tal que, para cada instancia del problema p y cada razón de aproximación ε > 0, el método encuentra una solución x que satisface:

${\displaystyle f(x)-\min _{G}f\leq \varepsilon \cdot [\max _{G}f-\min _{G}f]}$,

utilizando como máximo el siguiente número de operaciones aritméticas sobre números reales:

${\displaystyle Poli(Tamaño(p))\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

donde V ( p ) es una cantidad dependiente de los datos. Intuitivamente, significa que la cantidad de operaciones requeridas para cada dígito adicional de precisión es polinómica en Size( p ). En el caso del método del elipsoide, tenemos:

${\displaystyle V(p)=\left[{\frac {Vol({\text{initial ellipsoid}})}{Vol(G)}}\right]^{1/n}\leq \left[{\frac {Vol({\text{initial ellipsoid}})}{MinVol(p)}}\right]^{1/n}}$.

El método del elipsoide requiere como máximo pasos, y cada paso requiere operaciones aritméticas Poly(Size(p)).${\displaystyle 2(n-1)n\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

El método del elipsoide se utiliza en problemas de baja dimensión, como los problemas de ubicación plana, donde es numéricamente estable . Nemirovsky y BenTal ^{[6] : Sec.8.3.3} dicen que es eficiente si el número de variables es como máximo 20-30; esto es así incluso si hay miles de restricciones, ya que el número de iteraciones no depende del número de restricciones. Sin embargo, en problemas con muchas variables, el método del elipsoide es muy ineficiente, ya que el número de iteraciones crece como O( n ² ).

Incluso en problemas de tamaño "pequeño", sufre de inestabilidad numérica y bajo rendimiento en la práctica ^{[ cita requerida ]} .

El método del elipsoide es una técnica teórica importante en la optimización combinatoria . En la teoría de la complejidad computacional , el algoritmo del 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.

El método del elipsoide se puede utilizar para demostrar que muchos problemas algorítmicos en conjuntos convexos son equivalentes en tiempo polinomial.

Leonid Khachiyan aplicó el método del elipsoide al caso especial de programación lineal : minimizar c ^T x st Ax ≤ b , donde todos los coeficientes en A,b,c son números racionales. Demostró que los programas lineales pueden resolverse en tiempo polinomial. A continuación se presenta un esbozo del teorema de Khachiyan. ^{[6] : Sec.8.4.2}

Paso 1: reducción de la optimización a búsqueda . El teorema de dualidad de programación lineal dice que podemos reducir el problema de minimización anterior al problema de búsqueda: encontrar x,y st Ax ≤ b ; A ^T y = c ; y ≤ 0 ; c ^T x=b ^T y. El primer problema es solucionable si y solo si el segundo problema es solucionable; en caso de que el problema sea solucionable, las componentes x de la solución al segundo problema son una solución óptima al primer problema. Por lo tanto, de ahora en adelante, podemos asumir que necesitamos resolver el siguiente problema: encontrar z ≥ 0 st Rz ≤ r . Multiplicando todos los coeficientes racionales por el denominador común, podemos asumir que todos los coeficientes son números enteros.

Paso 2: reducir la búsqueda a la comprobación de viabilidad . El problema de encontrar z ≥ 0 st Rz ≤ r se puede reducir al problema de decisión binario: "¿ existe un z ≥ 0 tal que Rz ≤ r ? ". Esto se puede hacer de la siguiente manera. Si la respuesta al problema de decisión es "no", entonces la respuesta al problema de búsqueda es "Ninguna", y hemos terminado. De lo contrario, tome la primera restricción de desigualdad R ₁ z ≤ r ₁ ; reemplácela con una igualdad R ₁ z = r ₁ ; y aplique el problema de decisión nuevamente. Si la respuesta es "sí", mantenemos la igualdad; si la respuesta es "no", significa que la desigualdad es redundante y podemos eliminarla. Luego procedemos a la siguiente restricción de desigualdad. Para cada restricción, la convertimos en igualdad o la eliminamos. Finalmente, solo tenemos restricciones de igualdad, que se pueden resolver mediante cualquier método para resolver un sistema de ecuaciones lineales.

Paso 3 : el problema de decisión puede reducirse a un problema de optimización diferente. Defina la función residual f(z) := max[(Rz) ₁ -r ₁ , (Rz) ₂ -r ₂ , (Rz) ₃ -r ₃ ,...]. Claramente, f ( z )≤0 si y solo si Rz ≤ r . Por lo tanto, para resolver el problema de decisión, es suficiente resolver el problema de minimización: min _z f ( z ). La función f es convexa (es un máximo de funciones lineales). Denotemos el valor mínimo por f *. Entonces la respuesta al problema de decisión es "sí" si y solo si f*≤0.

Paso 4 : En el problema de optimización min _z f ( z ), podemos suponer que z está en una caja de lado 2 ^L , donde L es la longitud de bits de los datos del problema. Por lo tanto, tenemos un programa convexo acotado, que se puede resolver hasta cualquier precisión ε mediante el método del elipsoide, en un polinomio de tiempo en L .

Paso 5 : Se puede demostrar que, si f*>0, entonces f*>2 ^-poly(L) , para algún polinomio. Por lo tanto, podemos elegir la precisión ε=2 ^-poly(L) . Entonces, la solución ε-aproximada hallada por el método del elipsoide será positiva, si y solo si f*>0, si y solo si el problema de decisión es irresoluble.

El método del elipsoide tiene varias variantes, dependiendo de qué cortes exactamente se utilicen en cada paso. ^{[1] : Sec. 3}

En el método del elipsoide de corte central , ^{[1] : 82, 87–94} los cortes siempre pasan por el centro del elipsoide actual. La entrada es un número racional ε >0, un cuerpo convexo K dado por un oráculo de separación débil y un número R tal que S(0, R ) (la bola de radio R alrededor del origen) contiene K . La salida es una de las siguientes:

• (a) Un vector a una distancia de como máximo ε desde K, o --
• (b) Una matriz definida positiva A y un punto a tales que el elipsoide E( A , a ) contiene a K , y el volumen de E( A , a ) es como máximo ε .

El número de pasos es , el número de dígitos de precisión requeridos es p  := 8 N y la precisión requerida del oráculo de separación es d  := 2 ^{- p} .${\displaystyle N:=\lceil 5n\log(1/\epsilon )+5n^{2}\log(2R)\rceil }$

En el método de corte profundo del elipsoide , ^{[1] : 83} los cortes eliminan más de la mitad del elipsoide en cada paso. Esto hace que sea más rápido descubrir que K está vacío. Sin embargo, cuando K no está vacío, hay ejemplos en los que el método de corte central encuentra un punto factible más rápido. El uso de cortes profundos no cambia el orden de magnitud del tiempo de ejecución.

En el método del elipsoide de corte superficial , ^{[1] : 83, 94–101} los cortes eliminan menos de la mitad del elipsoide en cada paso. Esta variante no es muy útil en la práctica, pero tiene importancia teórica: permite demostrar resultados que no se pueden derivar de otras variantes. La entrada es un número racional ε >0, un cuerpo convexo K dado por un oráculo de separación superficial y un número R tal que S(0, R ) contiene a K . La salida es una matriz definida positiva A y un punto a tal que se cumple una de las siguientes condiciones:

• (a) El elipsoide E( A , a ) ha sido declarado "duro" por el oráculo, o -
• (b) K está contenido en E( A , a ) y el volumen de E( A , a ) es como máximo ε .

El número de pasos es y el número de dígitos de precisión requeridos es p  := 8 N.${\displaystyle N:=\lceil 5n(n+1)^{2}\log(1/\epsilon )+5n^{2}(n+1)^{2}\log(2R)+\log(n+1)\rceil }$

También existe una distinción entre los métodos del elipsoide circunscrito y del elipsoide inscrito: ^[7]

• En el método del elipsoide circunscrito , cada iteración encuentra un elipsoide de menor volumen que contiene la parte restante del elipsoide anterior. Este método fue desarrollado por Yudin y Nemirovskii. ^[8]
• En el método del elipsoide inscrito , cada iteración encuentra un elipsoide de mayor volumen que está contenido en la parte restante del elipsoide anterior. Este método fue desarrollado por Tarasov, Khachian y Erlikh. ^[9]

Los métodos difieren en su complejidad de tiempo de ejecución (a continuación, n es el número de variables y epsilon es la precisión):

• El método circunscrito requiere iteraciones, donde cada iteración consiste en encontrar un hiperplano separador y encontrar un nuevo elipsoide circunscrito. Encontrar un elipsoide circunscrito requiere tiempo.${\displaystyle O(n^{2})\ln {\frac {1}{\epsilon }}}$${\displaystyle O(n^{2})}$
• El método inscrito requiere iteraciones, donde cada iteración consiste en encontrar un hiperplano separador y encontrar un nuevo elipsoide inscrito. Encontrar un elipsoide inscrito requiere tiempo para algunos pequeños .${\displaystyle O(n)\ln {\frac {1}{\epsilon }}}$${\displaystyle O(n^{3.5+\delta })}$${\displaystyle \delta >0}$

La eficiencia relativa de los métodos depende del tiempo requerido para encontrar un hiperplano separador, que depende de la aplicación: si el tiempo de ejecución es para entonces el método circunscrito es más eficiente, pero si entonces el método inscrito es más eficiente. ^[7]${\displaystyle O(n^{t})}$${\displaystyle t\leq 2.5}$${\displaystyle t>2.5}$

• El método del centro de gravedad es un método conceptualmente más simple, que requiere menos pasos. Sin embargo, cada paso es costoso en términos computacionales, ya que requiere calcular el centro de gravedad del politopo factible actual.
• Los métodos de puntos interiores también permiten resolver problemas de optimización convexa en tiempo polinomial, pero su rendimiento práctico es mucho mejor que el método del elipsoide.

• 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, Programación lineal, 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, Programación entera, 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 sobre 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 , republicació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 

• EE364b, página de inicio de un curso de Stanford