Método de subgradiente

Los métodos de subgradiente son métodos de optimización convexa que utilizan subderivadas . Originalmente desarrollados por Naum Z. Shor y otros en los años 1960 y 1970, los métodos de subgradiente son convergentes cuando se aplican incluso a una función objetivo no diferenciable. Cuando la función objetivo es diferenciable, los métodos de subgradiente para problemas sin restricciones utilizan la misma dirección de búsqueda que el método de descenso más pronunciado .

Los métodos de subgradiente son más lentos que el método de Newton cuando se aplican para minimizar funciones convexas diferenciables dos veces de forma continua. Sin embargo, el método de Newton no logra converger en problemas que tienen puntos de inflexión no diferenciables.

En los últimos años, se han sugerido algunos métodos de punto interior para problemas de minimización convexa, pero los métodos de proyección de subgradiente y los métodos de descenso de paquetes relacionados siguen siendo competitivos. Para problemas de minimización convexa con un gran número de dimensiones, los métodos de proyección de subgradiente son adecuados, porque requieren poco almacenamiento.

Los métodos de proyección de subgradientes se aplican a menudo a problemas de gran escala con técnicas de descomposición. Dichos métodos de descomposición suelen permitir un método distribuido simple para un problema.

Reglas clásicas de subgradiente

Sea una función convexa con dominio Un método de subgradiente clásico itera donde denota cualquier subgradiente de en y es el iterado de Si es diferenciable, entonces su único subgradiente es el vector de gradiente en sí. Puede suceder que no sea una dirección de descenso para en Por lo tanto, mantenemos una lista que realiza un seguimiento del valor de función objetivo más bajo encontrado hasta ahora, es decir ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \mathbb {R} ^{n}.}$ $${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$ ${\displaystyle g^{(k)}}$ ${\displaystyle f\ }$ ${\displaystyle x^{(k)},\ }$ ${\displaystyle x^{(k)}}$ ${\displaystyle k^{th}}$ ${\displaystyle x.}$ ${\displaystyle f\ }$ ${\displaystyle \nabla f}$ ${\displaystyle -g^{(k)}}$ ${\displaystyle f\ }$ ${\displaystyle x^{(k)}.}$ ${\displaystyle f_{\rm {best}}\ }$ $${\displaystyle f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}.}$$

Reglas de tamaño de paso

Los métodos de subgradiente utilizan muchos tipos diferentes de reglas de tamaño de paso. En este artículo se indican cinco reglas clásicas de tamaño de paso para las que se conocen pruebas de convergencia:

• Tamaño de paso constante, ${\displaystyle \alpha _{k}=\alpha .}$
• Longitud de paso constante, lo que da ${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}$ ${\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}$
• Tamaño de paso cuadrado sumable pero no sumable, es decir, cualquier tamaño de paso que satisfaga $${\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$$
• Decreciente no sumable, es decir, cualquier tamaño de paso que satisfaga $${\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$$
• Longitudes de paso decrecientes no sumables, es decir, donde ${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}$ $${\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .}$$

Para las cinco reglas, los tamaños de paso se determinan "fuera de línea", antes de que se itere el método; los tamaños de paso no dependen de iteraciones anteriores. Esta propiedad "fuera de línea" de los métodos de subgradiente difiere de las reglas de tamaño de paso "en línea" utilizadas para los métodos de descenso para funciones diferenciables: Muchos métodos para minimizar funciones diferenciables satisfacen las condiciones suficientes de Wolfe para la convergencia, donde los tamaños de paso generalmente dependen del punto actual y de la dirección de búsqueda actual. En los libros de Bertsekas ^[1] y de Bertsekas, Nedic y Ozdaglar ^{[2] se ofrece una discusión extensa de las reglas de tamaño de paso para los métodos de subgradiente, incluidas las versiones incrementales.}

Resultados de convergencia

Para subgradientes escalados y de longitud de paso constante que tienen una norma euclidiana igual a uno, el método de subgradiente converge a una aproximación arbitrariamente cercana al valor mínimo, es decir

${\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }$por resultado de Shor . ^[3]

Estos métodos de subgradiente clásicos tienen un rendimiento deficiente y ya no se recomiendan para uso general. ^{[4] [5]} Sin embargo, todavía se utilizan ampliamente en aplicaciones especializadas porque son simples y se pueden adaptar fácilmente para aprovechar la estructura especial del problema en cuestión.

Métodos de proyección de subgradientes y de haces

Durante la década de 1970, Claude Lemaréchal y Phil Wolfe propusieron "métodos de haz" de descenso para problemas de minimización convexa. ^[6] El significado del término "métodos de haz" ha cambiado significativamente desde entonces. Kiwiel proporcionó versiones modernas y análisis de convergencia completa. ^[7] Los métodos de haz contemporáneos a menudo utilizan reglas de " control de nivel " para elegir tamaños de paso, desarrollando técnicas a partir del método de "proyección de subgradiente" de Boris T. Polyak (1969). Sin embargo, existen problemas en los que los métodos de haz ofrecen pocas ventajas sobre los métodos de proyección de subgradiente. ^{[4] [5]}

Optimización restringida

Subgradiente proyectado

Una extensión del método del subgradiente es el método del subgradiente proyectado , que resuelve el problema de optimización restringida .

minimizar sujeto a ${\displaystyle f(x)\ }$ $${\displaystyle x\in {\mathcal {C}}}$$

donde es un conjunto convexo . El método del subgradiente proyectado utiliza la iteración donde es la proyección sobre y es cualquier subgradiente de en ${\displaystyle {\mathcal {C}}}$ $${\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}$$ ${\displaystyle P}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle g^{(k)}}$ ${\displaystyle f\ }$ ${\displaystyle x^{(k)}.}$

Restricciones generales

El método del subgradiente se puede extender para resolver el problema restringido por desigualdad.

minimizar sujeto a ${\displaystyle f_{0}(x)\ }$ $${\displaystyle f_{i}(x)\leq 0,\quad i=1,\ldots ,m}$$

donde son convexos. El algoritmo toma la misma forma que el caso sin restricciones donde es un tamaño de paso y es un subgradiente de la función objetivo o una de las funciones de restricción en Tome donde denota el subdiferencial de Si el punto actual es factible, el algoritmo usa un subgradiente objetivo; si el punto actual es infactible, el algoritmo elige un subgradiente de cualquier restricción violada. ${\displaystyle f_{i}}$ $${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$ ${\displaystyle \alpha _{k}>0}$ ${\displaystyle g^{(k)}}$ ${\displaystyle x.\ }$ $${\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}$$ ${\displaystyle \partial f}$ ${\displaystyle f.\ }$

Véase también

• Descenso de gradiente estocástico  : algoritmo de optimización

Referencias

1. Bertsekas, Dimitri P. (2015). Algoritmos de optimización convexa (segunda edición). Belmont, MA: Athena Scientific. ISBN 978-1-886529-28-1.
2. Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y optimización convexa (segunda edición). Belmont, MA: Athena Scientific. ISBN 1-886529-45-0.
3. La convergencia aproximada del método de subgradiente de tamaño de paso constante (escalado) se indica en el Ejercicio 6.3.14(a) en Bertsekas (página 636): Bertsekas, Dimitri P. (1999). Programación no lineal (Segunda edición). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.En la página 636, Bertsekas atribuye este resultado a Shor: Shor, Naum Z. (1985). Métodos de minimización para funciones no diferenciables . Springer-Verlag . ISBN 0-387-12763-1.
4. Lemaréchal, Claude (2001). "Relajación lagrangiana". En Michael Jünger y Denis Naddef (ed.). Optimización combinatoria computacional: artículos de la Escuela de primavera celebrada en Schloss Dagstuhl, del 15 al 19 de mayo de 2000. Lecture Notes in Computer Science. Vol. 2241. Berlín: Springer-Verlag. págs. 112–156. doi :10.1007/3-540-45586-8_4. ISBN 3-540-42877-1.Señor 1900016.S2CID 9048698  . ​
5. Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (agosto de 2007). "Relajación lagrangiana mediante métodos de subgradiente ballstep". Matemáticas de la investigación de operaciones . 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241.
6. Bertsekas, Dimitri P. (1999). Programación no lineal (segunda edición). Cambridge, MA: Athena Scientific. ISBN 1-886529-00-0.
7. Kiwiel, Krzysztof (1985). Métodos de descendencia para optimización no diferenciable . Berlín: Springer Verlag . Pág. 362. ISBN. 978-3540156420.Sr. 0797754  .

Lectura adicional

• Bertsekas, Dimitri P. (1999). Programación no lineal . Belmont, MA: Athena Scientific. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y optimización convexa (segunda edición). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (2015). Algoritmos de optimización convexa . Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
• Shor, Naum Z. (1985). Métodos de minimización para funciones no diferenciables . Springer-Verlag . ISBN. 0-387-12763-1.
• Ruszczyński, Andrzej (2006). Optimización no lineal . Princeton, NJ: Princeton University Press . pp. xii+454. ISBN 978-0691119151.Sr. 2199043  .

Enlaces externos

• EE364A y EE364B, secuencia de cursos de optimización convexa de Stanford.