Método de subgradiente

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

• tamaño de paso constante,${\displaystyle \alpha _{k}=\alpha .}$
• longitud de paso constante,${\displaystyle \alpha _ {k}=\gamma /\lVert g^{(k)}\rVert _ {2},}$lo cual da${\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${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}$dónde$${\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 iterar el método; los tamaños de paso no dependen de las iteraciones previas. 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. Una discusión extensa de las reglas de tamaño de paso para métodos de subgradiente, incluidas las versiones incrementales, se encuentra en los libros de Bertsekas ^{[ 1 ]} y de Bertsekas, Nedic y Ozdaglar. ^{[ 2 ]}

Para subgradientes de longitud de paso constante y escalados con 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 un resultado de Shor . ^{[ 3 ]}

Estos métodos clásicos de subgradiente 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 sencillos y se pueden adaptar fácilmente para aprovechar la estructura especial del problema en cuestión.

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

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

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

El método del subgradiente puede extenderse para resolver el problema con restricciones de desigualdad.

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

dónde${\displaystyle f_{i}}$son convexas. El algoritmo toma la misma forma que el caso sin restricciones. $${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$ dónde${\displaystyle \alpha _{k}>0}$es un tamaño de paso, y${\displaystyle g^{(k)}}$es un subgradiente de la función objetivo o de una de las funciones de restricción en${\displaystyle x.\ }$ Llevar $${\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}}}$$ dónde${\displaystyle \partial f}$denota el subgradiente de${\displaystyle f.\ }$ Si el punto actual es factible, el algoritmo utiliza un subgradiente objetivo; si el punto actual no es factible, el algoritmo elige un subgradiente de cualquier restricción violada.