Escala afín

Algoritmo para resolver problemas de programación lineal

El método de escala afín es un método de puntos interiores , lo que significa que forma una trayectoria de puntos estrictamente dentro de la región factible de un programa lineal (a diferencia del algoritmo simplex , que recorre las esquinas de la región factible).

En optimización matemática , el escalamiento afín es un algoritmo para resolver problemas de programación lineal . En concreto, se trata de un método de puntos interiores , descubierto por el matemático soviético II Dikin en 1967 y reinventado en Estados Unidos a mediados de los años 1980.

Historia

El escalamiento afín tiene una historia de múltiples descubrimientos . Fue publicado por primera vez por II Dikin en el Instituto de Sistemas de Energía de la Academia Rusa de Ciencias (Instituto de Energía de Siberia, Academia de Ciencias de la URSS en ese momento) en la Doklady Akademii Nauk SSSR de 1967 , seguido por una prueba de su convergencia en 1974. ^[1] El trabajo de Dikin pasó en gran medida desapercibido hasta el descubrimiento en 1984 del algoritmo de Karmarkar , el primer algoritmo práctico de tiempo polinomial para programación lineal. La importancia y complejidad del método de Karmarkar impulsó a los matemáticos a buscar una versión más simple.

Varios grupos idearon entonces, de forma independiente, una variante del algoritmo de Karmarkar. ER Barnes en IBM , ^[2] un equipo dirigido por RJ Vanderbei en AT&T , ^[3] y varios otros reemplazaron las transformaciones proyectivas que Karmarkar utilizaba por otras afines . Después de unos años, se comprendió que los "nuevos" algoritmos de escalado afín eran, de hecho, reinvenciones de los resultados de Dikin, obtenidos con décadas de antigüedad. ^{[1] [4]} De los redescubridores, sólo Barnes y Vanderbei et al. lograron producir un análisis de las propiedades de convergencia del escalado afín. Karmarkar, que también había ideado el escalado afín en este período de tiempo, creyó erróneamente que convergía tan rápidamente como su propio algoritmo. ^{[5] : 346}

Algoritmo

El escalamiento afín funciona en dos fases: la primera encuentra un punto factible desde el cual comenzar a optimizar, mientras que la segunda realiza la optimización real manteniéndose estrictamente dentro de la región factible.

Ambas fases resuelven programas lineales en forma de igualdad, a saber:

minimizar c ⋅ x

sujeto a Ax = b , x ≥ 0 .

Estos problemas se resuelven utilizando un método iterativo , que conceptualmente procede trazando una trayectoria de puntos estrictamente dentro de la región factible de un problema, calculando los pasos de descenso de gradiente proyectados en una versión reescalada del problema y luego escalando el paso de nuevo al problema original. El escalado garantiza que el algoritmo pueda continuar realizando pasos grandes incluso cuando el punto en consideración esté cerca del límite de la región factible. ^{[5] : 337}

Formalmente, el método iterativo en el corazón del escalamiento afín toma como entradas A , b , c , una estimación inicial x ⁰ > 0 que es estrictamente factible (es decir, Ax ⁰ = b ), una tolerancia ε y un tamaño de paso β . Luego procede iterando ^{[1] : 111}

• Sea D _k la matriz diagonal con x ^k en su diagonal.
• Calcular un vector de variables duales :

  ${\displaystyle w^{k}=(AD_{k}^{2}A^{\operatorname {T} })^{-1}AD_{k}^{2}c.}$

• Calcular un vector de costos reducidos , que mida la holgura de las restricciones de desigualdad en el dual:

  ${\displaystyle r^{k}=c-A^{\operatorname {T} }w^{k}.}$

• Si y , la solución actual x ^k es ε -óptima. ${\displaystyle r^{k}>0}$ ${\displaystyle \mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon }$
• Si , el problema no tiene límites. ${\displaystyle -D_{k}r^{k}\geq 0}$
• Actualizar ${\displaystyle x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}}$

Inicialización

La fase I, la inicialización, resuelve un problema auxiliar con una variable adicional u y utiliza el resultado para derivar un punto inicial para el problema original. Sea x ⁰ un punto arbitrario estrictamente positivo; no necesita ser factible para el problema original. La inviabilidad de x ⁰ se mide mediante el vector

${\displaystyle v=b-Ax^{0}}$.

Si v = 0 , x ⁰ es factible. Si no lo es, la fase I resuelve el problema auxiliar.

minimizar u

sujeto a Ax + uv = b , x ≥ 0 , u ≥ 0 .

Este problema tiene la forma correcta para su solución mediante el algoritmo iterativo anterior, ^[a] y

${\displaystyle {\begin{pmatrix}x^{0}\\1\end{pmatrix}}}$

es un punto inicial factible para ello. Resolviendo el problema auxiliar se obtiene

${\displaystyle {\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}}$.

Si u ^* = 0 , entonces x ^* ≥0 es factible en el problema original (aunque no necesariamente estrictamente interior), mientras que si u ^* > 0 , el problema original es inviable. ^{[5] : 343}

Análisis

Si bien es fácil de enunciar, el escalamiento afín resultó difícil de analizar. Su convergencia depende del tamaño del paso, β . Para tamaños de paso β ≤ ⁠2/3Se ha demostrado que la variante de escala afín de Vanderbei converge, mientras que para β > 0,995 , se conoce un problema de ejemplo que converge a un valor subóptimo. ^{[5] : 342} Se ha demostrado que otras variantes del algoritmo exhiben un comportamiento caótico incluso en problemas pequeños cuando β > ⁠2/3⁠ . ^{[6] [7]}

Notas

1. La estructura del problema auxiliar permite cierta simplificación de las fórmulas. ^{[5] : 344}

Referencias

1. Vanderbei, RJ; Lagarias, JC (1990). "Resultado de convergencia de II Dikin para el algoritmo de escalamiento afín". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. Vol. 114. Providence, RI: American Mathematical Society. págs. 109–119. doi :10.1090/conm/114/1097868. MR  1097868.
2. Barnes, Earl R. (1986). "Una variación del algoritmo de Karmarkar para resolver problemas de programación lineal". Programación matemática . 36 (2): 174–182. doi :10.1007/BF02592024. S2CID  27590019.
3. Vanderbei, Robert J.; Meketon, Marc S.; Freedman, Barry A. (1986). "Una modificación del algoritmo de programación lineal de Karmarkar" (PDF) . Algorithmica . 1 (1–4): 395–407. doi :10.1007/BF01840454. S2CID  779577.
4. Bayer, DA; Lagarias, JC (1989). "La geometría no lineal de la programación lineal I: trayectorias de escalado afín y proyectivo" (PDF) . Transactions of the American Mathematical Society . 314 (2): 499. doi : 10.1090/S0002-9947-1989-1005525-6 .
5. Vanderbei, Robert J. (2001). Programación lineal: fundamentos y extensiones . Springer Verlag. págs. 333–347.
6. Bruin, H.; Fokkink, RJ; Gu, G.; Roos, C. (2014). "Sobre el comportamiento caótico del algoritmo de escalado afín primal-dual para optimización lineal" (PDF) . Chaos . 24 (4): 043132. arXiv : 1409.6108 . Bibcode :2014Chaos..24d3132B. doi :10.1063/1.4902900. PMID  25554052. S2CID  21505124.
7. Castillo, Ileana; Barnes, Earl R. (2006). "Comportamiento caótico del algoritmo de escalamiento afín para programación lineal". SIAM J. Optim . 11 (3): 781–795. doi :10.1137/S1052623496314070.

Lectura adicional

• Adler, Ilan; Monteiro, Renato DC (1991). "Comportamiento limitante de las trayectorias continuas de escalamiento afín para problemas de programación lineal" (PDF) . Programación matemática . 50 (1–3): 29–51. doi :10.1007/bf01594923. S2CID  15748327.
• Saigal, Romesh (1996). "Una prueba simple de un método de escalamiento afín primario" (PDF) . Annals of Operations Research . 62 : 303–324. doi :10.1007/bf02206821. hdl : 2027.42/44263 . S2CID  : 14046399.
• Tseng, Paul; Luo, Zhi-Quan (1992). "Sobre la convergencia del algoritmo de escalamiento afín" (PDF) . Programación matemática . 56 (1–3): 301–319. CiteSeerX  10.1.1.94.7852 . doi :10.1007/bf01580904. hdl :1721.1/3161. S2CID  13714272.

Enlaces externos

• "15.093 Métodos de optimización, lección 21: El algoritmo de escalamiento afín" (PDF) . MIT OpenCourseWare . 2009.
• Mitchell, John (noviembre de 2010). "Métodos de puntos interiores". Instituto Politécnico Rensselaer .
• "Lección 6: Método del punto interior" (PDF) . NCTU OpenCourseWare . Archivado desde el original (PDF) el 2016-10-11 . Consultado el 2016-02-06 .