método elipsoide

Método iterativo para minimizar funciones convexas.

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 de optimización lineal factibles con datos racionales, el método del elipsoide es un algoritmo que encuentra una solución óptima en una serie de pasos que es polinómica en el tamaño de entrada.

Historia

El método del elipsoide tiene una larga historia. Como método iterativo , Naum Z. Shor presentó 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 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 simplex , 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 cuales es exponencial en el tamaño del problema. Como tal, tener un algoritmo que garantice que sea polinómico en todos los casos parecía un 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 ser polinómico. 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 mucha mayor utilidad práctica. Específicamente, el algoritmo de Karmarkar , un método de punto interior , 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 alcanzar 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. ^{[1] [2] [3] [4]} Sólo en el siglo XXI aparecieron algoritmos de punto interior con propiedades de complejidad similares. ^{[ cita necesaria ]}

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 convexas 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 separación para el conjunto convexo . Dado un punto , el oráculo debería devolver una de dos respuestas: ^[5] ${\displaystyle Q}$ ${\displaystyle x\in \mathbb {R} ^{n}}$

• "El punto está en ", o - ${\displaystyle x}$ ${\displaystyle Q}$
• "La cuestión no está en , y además, aquí hay un hiperplano que 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}$

El resultado del método del elipsoide es:

• Cualquier punto en el 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 lineal). Una forma de hacerlo es combinando los programas lineales primario y dual en un solo programa y agregando la restricción (lineal) adicional 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 utilizar la búsqueda binaria para encontrar el valor óptimo. ^{[ cita necesaria ]}

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(x-x^{(k)}\right)^{T}P_{(k)}^{-1}\left(x-x^{(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 lo tanto concluimos que

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

Lo configuramos como el elipsoide de volumen mínimo que contiene el medio elipsoide 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 parada está 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 .}$

Minimización restringida por la 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 {best}}^{(k)}}$ ${\displaystyle x^{(k)}}$

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

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

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

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

para todo z factible .

Rendimiento en programas convexos.

Garantía de complejidad teórica en tiempo de ejecución

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

Considere 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 de la familia está representado por un vector de datos Datos ( p ), por ejemplo, los coeficientes de valores reales en matrices y vectores que representan la función f y la región factible G. El tamaño de un problema p , Tamaño ( p ), se define como el número de elementos (números reales) en Datos ( p ). Se necesitan los siguientes supuestos:

1. G (la región factible) es:
   • Encerrado;
   • Tiene un interior no vacío (por lo que es 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 los datos ( p ) y un punto x en R ⁿ , se pueden calcular usando 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 el "polinomio R". Esto significa que existe un polinomio Poly tal que, para cada instancia de problema p y cada relació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 con números reales:

${\displaystyle Poly(Size(p))\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

donde V ( p ) es una cantidad que depende de los datos. Intuitivamente, significa que el número de operaciones requeridas para cada dígito adicional de precisión es polinómico en tamaño ( 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)}$

Rendimiento práctico

El método del elipsoide se utiliza en problemas de baja dimensión, como problemas de ubicación plana, donde es numéricamente estable . Nemirovsky y BenTal ^{[6] : La sección 8.3.3} dice 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 mal desempeño en la práctica ^{[ cita necesaria ]} .

Importancia teórica

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

Rendimiento en programas lineales

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 se pueden resolver en tiempo polinomial. Aquí hay un bosquejo del teorema de Khachiyan. ^{[6] : Sección 8.4.2}

Paso 1: reducir la optimización de la búsqueda . El teorema de la 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; cTx = ^bTy .^​ El primer problema tiene solución si el segundo problema tiene solución; en caso de que el problema tenga solución, las componentes x de la solución del segundo problema son una solución óptima del 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 suponer que todos los coeficientes son números enteros.

Paso 2: reducir la búsqueda a verificación de viabilidad . El problema de encontrar z ≥ 0 st Rz ≤ r se puede reducir al problema de decisión binaria: " ¿existe un z ≥ 0 tal que Rz ≤ r ? ". Esto puede hacerse de la siguiente manera. Si la respuesta al problema de decisión es "no", entonces la respuesta al problema de búsqueda es "Ninguno" y hemos terminado. De lo contrario, tome la primera restricción de desigualdad R ₁ z ≤ r ₁ ; reemplácelo con una igualdad R ₁ z = r ₁ ; y aplicar 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 a igualdad o la eliminamos. Finalmente, solo tenemos restricciones de igualdad, que pueden resolverse mediante cualquier método para resolver un sistema de ecuaciones lineales.

Paso 3 : el problema de decisión se puede reducir 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 Rz ≤ r . Por tanto, para resolver el problema de decisión, basta con resolver el problema de minimización: min _z f ( z ). La función f es convexa (es un máximo de funciones lineales). Denota el valor mínimo por f *. Entonces la respuesta al problema de decisión es "sí" sif*≤0.

Paso 4 : En el problema de optimización min _z f ( z ), podemos suponer que z está en una caja de longitud lateral 2 ^L , donde L es la longitud de bits de los datos del problema. Por tanto, tenemos un programa convexo acotado, que puede resolverse con cualquier precisión ε mediante el método del elipsoide, en tiempo polinomio 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 encontrada por el método del elipsoide será positiva, si y solo f*>0, y si y sólo si el problema de decisión no tiene solución.

Variantes

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

Diferentes cortes

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. El resultado es uno de los siguientes:

• (a) Un vector a una distancia de como máximo ε de K, o --
• (b) Una matriz definida positiva A y un punto a tal que el elipsoide E( A , a ) contiene 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 del elipsoide de corte profundo , ^{[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 probar 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 poco profundo y un número R tal que S(0, R ) contiene 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 }$

Diferentes elipsoides

También hay 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 contiene 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 épsilon es la precisión):

• El método circunscrito requiere iteraciones, donde cada iteración consiste en encontrar un hiperplano de separación 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 de separación y encontrar un nuevo elipsoide inscrito. Encontrar un elipsoide inscrito requiere algo de tiempo . ${\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 de separación, 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}$

Métodos relacionados

• El método del centro de gravedad es un método conceptualmente más simple que requiere menos pasos. Sin embargo, cada paso es computacionalmente costoso, 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.

Notas

1. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419
2. L. Lovász : una teoría algorítmica de números, gráficas y convexidad , Serie de conferencias regionales CBMS-NSF en matemáticas aplicadas 50, SIAM, Filadelfia, Pensilvania, 1986.
3. V. Chandru y MRRao, Programación lineal, Capítulo 31 del Manual de algoritmos y teoría de la computación , editado por MJ Atallah , CRC Press 1999, 31-1 a 31-37.
4. V. Chandru y MRRao, Programación entera, Capítulo 32 del Manual de algoritmos y teoría de la computación , editado por MJAtallah, CRC Press 1999, 32-1 a 32-45.
5. "MIT 6.854 Primavera de 2016 Conferencia 12: De la separación a la optimización y viceversa; Método elipsoide - YouTube". www.youtube.com . Archivado desde el original el 22 de diciembre de 2021 . Consultado el 3 de enero de 2021 .
6. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .^{[ enlace muerto permanente ]}
7. Newman, DJ; Primak, ME (1 de diciembre de 1992). "Complejidad de métodos de elipsoides circunscritos e inscritos para resolver modelos económicos de equilibrio". Matemáticas Aplicadas y Computación . 52 (2): 223–231. doi :10.1016/0096-3003(92)90079-G. ISSN  0096-3003.
8. https://elibrary.ru/item.asp?id=38308898
9. Primak, YO; Kheyfets, BL (1 de junio de 1995). "Una modificación del método del elipsoide inscrito". Modelado Matemático e Informático . 21 (11): 69–76. doi :10.1016/0895-7177(95)00080-L. ISSN  0895-7177.

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, 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 

enlaces externos

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