Método elipsoidal

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 la resolución de problemas de optimización lineal factibles 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 polinómico en el tamaño de la entrada.

Historia

El método del 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.

El algoritmo elipsoidal, utilizado para resolver problemas de programación lineal con datos racionales, fue estudiado por Leonid Khachiyan . Su logro consistió en demostrar la resolubilidad polinomial de los programas lineales. Este fue un avance significativo desde el punto de vista teórico: el algoritmo estándar para resolver problemas lineales en aquel entonces era el algoritmo simplex , cuyo tiempo de ejecución suele ser lineal con respecto al tamaño del problema, aunque existen ejemplos en los que es exponencial . Por lo tanto, contar con un algoritmo que garantizara la resolución polinomial en todos los casos representó un hito teórico.

El trabajo de Khachiyan demostró, por primera vez, que existen algoritmos para resolver programas lineales con un tiempo de ejecución polinomial. Sin embargo, en la práctica, el algoritmo es bastante lento y de escaso interés práctico, aunque sirvió de inspiración para trabajos posteriores que resultaron ser de mucha mayor utilidad práctica. En concreto, 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 ]} Recién en el siglo XXI han aparecido 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 $f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R}$ a minimizar sobre el vector $x$ (que contiene n variables);
Restricciones de desigualdad convexas de la forma $f_{i}(x)\leqslant 0$ donde las funciones $f_{i}$ son convexas; estas restricciones definen un conjunto convexo $Q$ .
Restricciones de igualdad lineal de la forma $h_{i}(x)=0$ .

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

{\displaystyle {\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\

que contiene un minimizador $x^{*}$ , dónde $P_{(0)}\succ 0$ y $x_{0}$ es el centro de ${\mathcal {E}}$ .

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

"El punto $x$ está en $Q$ ", o -
"El punto $x$ no está en $Q$ y además, aquí hay un hiperplano que separa $x$ de $Q$ ", es decir, un vector $c$ de tal manera que $c\cdot x<c\cdot y$ a pesar de $y\in Q$ .

El resultado del método del elipsoide es uno de los siguientes:

Cualquier punto del politopo $Q$ (es decir, cualquier punto factible), o -
Una prueba de que $Q$ está vacío.

La minimización de una función que es cero en todos los puntos, sujeta a restricciones de desigualdad, equivale al problema de identificar cualquier punto factible. Resulta que cualquier problema de programación lineal puede reducirse a un problema de factibilidad lineal (es decir, minimizar la función cero sujeta a ciertas restricciones lineales de desigualdad e igualdad). Una forma de hacerlo es combinando los programas lineales primal y dual en un solo programa, y añadiendo la restricción (lineal) adicional de que el valor de la solución primal no sea peor que el de la solución dual. ^{[ 6 ]}^{: 84} Otra forma es tratar la función objetivo del programa lineal como una restricción adicional y utilizar la búsqueda binaria para encontrar el valor óptimo. ^{[ 6 ]}^{: 7–8}

Minimización sin restricciones

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

{\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\

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

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\

Nosotros establecimos ${\mathcal {E}}^{(k+1)}$ ser el elipsoide de volumen mínimo que contiene el semielipsoide descrito anteriormente y calcular $x^{(k+1)}$ La actualización la proporciona

{\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

{\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 de que

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

Minimización con restricciones de desigualdad

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

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

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

Si $x^{(k)}$ es inviable y viola la restricción j -ésima, actualice el elipsoide con un corte de viabilidad. Nuestro corte de viabilidad puede ser un subgradiente $g_{j}$ de $f_{j}$ que debe satisfacer

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 temporal del método del elipsoide en el modelo RAM real viene dada por el siguiente teorema. ^{[ 7 ]}^{: Thm.8.3.1}

Consideremos una familia de problemas de optimización convexa de la forma: minimizar f ( x ) con x 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 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 las siguientes suposiciones:

G (la región factible) es:
- Encerrado;
- Tiene un interior no vacío (por lo que existe un punto estrictamente factible);
Dados los datos p , se puede calcular utilizando poly(Size(p)) operaciones aritméticas:
- Un elipsoide que contiene G ;
- Un límite inferior 'MinVol(p) > 0' del volumen G.
Dados los datos p y un punto x en R ⁿ , se puede calcular utilizando poly(Size(p)) operaciones aritméticas:
- Un oráculo de separación para G (es decir: afirmar que x está en G , o devolver un hiperplano que separe 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 estas suposiciones, 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 :

$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:

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

donde V ( p ) es una cantidad que depende de los datos. Intuitivamente, esto significa que el número de operaciones necesarias para cada dígito adicional de precisión es polinómico en Size( p ). En el caso del método del elipsoide, tenemos:

$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 $2(n-1)n\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)$ pasos, y cada paso requiere Poly(Size(p)) operaciones aritméticas.

Rendimiento práctico

El método del elipsoide se utiliza en problemas de baja dimensión, como problemas de localización planar, donde es numéricamente estable . Nemirovsky y BenTal ^{[ 7 ]}^{: 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 un rendimiento deficiente en la práctica .

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 del elipsoide resulta 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 puede utilizarse para demostrar que muchos problemas algorítmicos sobre conjuntos convexos son equivalentes en tiempo polinomial.

Rendimiento en programas lineales

Leonid Khachiyan aplicó el método del elipsoide al caso especial de la 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. Aquí se presenta un esbozo del teorema de Khachiyan. ^{[ 7 ]}^{: Sec.8.4.2}

Paso 1: reducir la optimización a la búsqueda . El teorema de dualidad de la programación lineal dice que podemos reducir el problema de minimización anterior al problema de búsqueda: encontrar x,y tal que Ax ≤ b ; A ^T y = c ; y ≤ 0 ; c ^T x=b ^T y. El primer problema es resoluble si y solo si el segundo problema es resoluble; en caso de que el problema sea resoluble, 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 tal que Rz ≤ r . Multiplicando todos los coeficientes racionales por el denominador común, podemos asumir que todos los coeficientes son enteros.

Paso 2: Reducción de la búsqueda a una verificación de factibilidad . El problema de encontrar z ≥ 0 tal que Rz ≤ r se puede reducir al problema de decisión binaria: "¿ 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 "Ninguno", y hemos terminado. De lo contrario, tomamos la primera restricción de desigualdad R ₁ z ≤ r ₁ ; la reemplazamos por una igualdad R ₁ z = r ₁ ; y aplicamos 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 se puede reducir a un problema de optimización diferente. Definimos 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, basta con resolver el problema de minimización: min _z f ( z ). La función f es convexa (es el máximo de funciones lineales). Denotamos 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 en bits de los datos del problema. Por lo tanto, tenemos un programa convexo acotado, que puede resolverse hasta cualquier precisión ε mediante el método del elipsoide, en tiempo polinomial 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 si f*>0, si y solo si el problema de decisión es irresoluble.

Variantes

El método del elipsoide tiene varias variantes, dependiendo de los cortes exactos que se utilicen en cada paso. ^{[ 1 ]}^{: Sec. 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 a K. La salida es una de las siguientes:

(a) Un vector a una distancia de como máximo ε de 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 $N:=\lceil 5n\log(1/\epsilon )+5n^{2}\log(2R)\rceil$ , 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} .

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 acelera el descubrimiento de que K está vacío. Sin embargo, cuando K no está vacío, existen ejemplos en los que el método de corte central encuentra un punto factible más rápidamente. 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 $N:=\lceil 5n(n+1)^{2}\log(1/\epsilon )+5n^{2}(n+1)^{2}\log(2R)+\log(n+1)\rceil$ y el número de dígitos de precisión requeridos es p := 8 N.

Elipsoides diferentes

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

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. ^{[ 9 ]}
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. ^{[ 10 ]}

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

El método circunscrito requiere $O(n^{2})\ln {\frac {1}{\epsilon }}$ iteraciones, donde cada iteración consiste en encontrar un hiperplano separador y encontrar un nuevo elipsoide circunscrito. Encontrar un elipsoide circunscrito requiere $O(n^{2})$ tiempo.
El método inscrito requiere $O(n)\ln {\frac {1}{\epsilon }}$ iteraciones, donde cada iteración consiste en encontrar un hiperplano separador y encontrar un nuevo elipsoide inscrito. Encontrar un elipsoide inscrito requiere $O(n^{3.5+\delta })$ tiempo para algunos pequeños $\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 $O(n^{t})$ para $t\leq 2.5$ entonces el método circunscrito es más eficiente, pero si $t>2.5$ entonces el método inscrito es más eficiente. ^{[ 8 ]}

Métodos relacionados

El método del centro de gravedad es conceptualmente más sencillo y 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 punto interior también permiten resolver problemas de optimización convexa en tiempo polinomial, pero su rendimiento práctico es mucho mejor que el del método del elipsoide.

Notas

1 2 3 4 5 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, MR 1261419
↑ L. Lovász : Una teoría algorítmica de números, grafos y convexidad , CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Filadelfia, Pensilvania, 1986.
↑ V. Chandru y MRRao, Programación lineal, Capítulo 31 en Algoritmos y teoría de la computación Manual , editado por MJ Atallah , CRC Press 1999, 31-1 a 31-37.
↑ V. Chandru y MRRao, Programación entera, Capítulo 32 en Manual de algoritmos y teoría de la computación , editado por MJAtallah, CRC Press 1999, 32-1 a 32-45.
↑ "MIT 6.854 Primavera 2016 Clase 12: De la separación a la optimización y viceversa; Método del elipsoide - YouTube" . www.youtube.com . 18 de marzo de 2016. Archivado del original el 22 de diciembre de 2021. Consultado el 3 de enero de 2021 .
1 2 Matoušek, Jiří; Gärtner, Bernd (2007). Comprensión y uso de la programación lineal . Universitext. Berlín; Nueva York: Springer. ISBN 978-3-540-30697-9.
1 2 3 Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) . Archivado del original (PDF) el 10 de diciembre de 2023.
1 2 Newman, DJ; Primak, ME (1992-12-01). "Complejidad de los métodos de elipsoide circunscrito e inscrito 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 .
↑ Berkovich, Yudin David; Semenovich, Nemirovsky Arkady. "Complejidad informacional y métodos eficientes para la solución de problemas extremales convexos" . Matekon . 13 (2): 22– 45. ISSN 0025-1127 .
↑ Primak, ME; Kheyfets, BL (1995-06-01). "Una modificación del método del elipsoide inscrito" . Mathematical and Computer Modelling . 21 (11): 69– 76. doi : 10.1016/0895-7177(95)00080-L . ISSN 0895-7177 .

Lecturas adicionales

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 Manual de algoritmos y teoría de la computación , editado por MJAtallah, CRC Press 1999, 31-1 a 31-37.
V. Chandru y MRRao, Programación entera, Capítulo 32 en Manual de algoritmos y teoría de la computación , 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, grafos y convexidad , CBMS-NSF Regional Conference Series in Applied Mathematics 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 , página principal de un curso de Stanford

[:1-1] 1 2 3 4 5 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, MR 1261419

[2] L. Lovász : Una teoría algorítmica de números, grafos y convexidad , CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Filadelfia, Pensilvania, 1986.

[3] V. Chandru y MRRao, Programación lineal, Capítulo 31 en Algoritmos y teoría de la computación Manual , editado por MJ Atallah , CRC Press 1999, 31-1 a 31-37.

[4] V. Chandru y MRRao, Programación entera, Capítulo 32 en Manual de algoritmos y teoría de la computación , editado por MJAtallah, CRC Press 1999, 32-1 a 32-45.

[:0-5] "MIT 6.854 Primavera 2016 Clase 12: De la separación a la optimización y viceversa; Método del elipsoide - YouTube" . www.youtube.com . 18 de marzo de 2016. Archivado del original el 22 de diciembre de 2021. Consultado el 3 de enero de 2021 .

[:3-6] 1 2 Matoušek, Jiří; Gärtner, Bernd (2007). Comprensión y uso de la programación lineal . Universitext. Berlín; Nueva York: Springer. ISBN 978-3-540-30697-9.

[:02-7] 1 2 3 Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) . Archivado del original (PDF) el 10 de diciembre de 2023.

[:2-8] 1 2 Newman, DJ; Primak, ME (1992-12-01). "Complejidad de los métodos de elipsoide circunscrito e inscrito 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 .

[9] Berkovich, Yudin David; Semenovich, Nemirovsky Arkady. "Complejidad informacional y métodos eficientes para la solución de problemas extremales convexos" . Matekon . 13 (2): 22– 45. ISSN 0025-1127 .

[10] Primak, ME; Kheyfets, BL (1995-06-01). "Una modificación del método del elipsoide inscrito" . Mathematical and Computer Modelling . 21 (11): 69– 76. doi : 10.1016/0895-7177(95)00080-L . ISSN 0895-7177 .

[ 2 ]

[ 3 ]

[ 4 ]

[ 9 ]

[ 10 ]