Método elipsoide

El método del elipsoide es un algoritmo para encontrar un punto que se encuentra en la intersección de conjuntos convexos. Desarrollado por A. S. Nemirovsky y llevado a la implementación algorítmica por L. G. Khachiyan en el Centro de Computación de la Academia de Ciencias de la URSS.

Descripción del algoritmo

Primero, se elige una bola grande que contiene la intersección de conjuntos convexos. El método de construcción de esta bola depende del problema. Además, en cada paso hay un elipsoide especificado por el centro y los vectores . El elipsoide contiene puntos para los cuales . Tenga en cuenta que el mismo elipsoide se puede especificar de varias maneras. Si el centro de este elipsoide pertenece a todos los conjuntos convexos, entonces se encuentra el punto requerido. De lo contrario, existe un hiperplano , que pasa por el punto , tal que uno de los conjuntos se encuentra completamente a un lado de él. Luego se puede pasar de la base original a otra base paralela y dirigida hacia el conjunto. Pongamos ahora , , en . Este nuevo elipsoide contiene la mitad del antiguo y tiene un volumen menor. Por lo tanto, el volumen del elipsoide disminuye exponencialmente con un aumento en el número de pasos, y el punto deseado se encontrará en pasos, donde es el volumen de la bola original y es el volumen del área de intersección. El tiempo total de ejecución del algoritmo es igual a , donde es el número de conjuntos, es el tiempo para comprobar si un punto pertenece a un conjunto. $v$ ${\displaystyle v_{1},v_{2},\dots,v_{n}\en \mathbb {R} ^{n))$ $v+c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}$ $c_{1}^{2}+c_{2}^{2}+\cdots +c_{n}^{2}\leqslant 1$ $\Pi$ $v$ $v_{i}$ $\tau,w_{2},\puntos w_{n}$ $Wisconsin}$ $\Pi$ $\tau$ $v'=v+{\frac{\tau}{n+1}}$ $v'_{1}={\frac {n\tau}{n+1}}$ $v'_{i}=w_{i}{\frac {n}{{\sqrt {n^{2}-1))))$ $i\geq 2$ $O(n^{2}\log(V_{1}/V_{2}))$ $V_{1}$ $V_{2}$ $O(Ntn^{2}\log(V_{1}/V_{2}))$ $norte$ $t$

Aplicación a un problema de programación lineal

Si en un problema de programación lineal fue posible construir una bola que contenga la solución deseada, entonces puede resolverse por el método del elipsoide. Para hacer esto, primero encontramos algún punto dentro de la pelota que satisfaga las restricciones del problema. Dibujamos un hiperplano a través de él , donde es la función objetivo, y encontramos un punto en la intersección de los hiperplanos original y nuevo (a partir del elipsoide actual). Hacemos lo mismo con el nuevo punto encontrado. El proceso converge a la solución óptima a una tasa exponencial (ya que el volumen del elipsoide disminuye con esta tasa). $tu$ $f(x)<f(u)$ $F$

Eficiencia del método

El algoritmo polinomial teóricamente podría convertirse en el nuevo estándar, sin embargo, en la práctica, el algoritmo Khachiyan debe usarse con precaución: hay problemas con un tamaño de 50 variables que requieren más de 24 mil iteraciones del método Khachiyan, mientras que el número de mucho iteraciones más simples del método simplex en tales casos se calculan cientos o incluso decenas [1] [2] . Sin embargo, hay ejemplos de problemas para los cuales los algoritmos de esta clase funcionan cientos de veces más eficientemente que las implementaciones estándar del método simplex.

Notas

↑ Nikolenko, 2005 .
↑ Schreiver, 1991 , pág. 264.

Literatura

SA Ashmanov. Programación lineal. - M. : Edición principal de literatura física y matemática, 1981. - S. 288-289.
A. Schreiver. Teoría de la programación lineal y entera, v1. - M. : "Mir", 1991. - ISBN 5-03-002754-8 .
S. Nikolenko. Teoría y práctica de la complejidad // Computerra. - M. : Revista LLC "Computerra", 2005. - Edición. 31 .

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock Método Powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial