Los métodos de subgrado son métodos iterativos para resolver problemas de minimización convexa . Desarrollado originalmente por Naum Z. Shor y otros en las décadas de 1960 y 1970, los métodos de subgrado son convergentes cuando se aplican incluso a una función objetivo no diferenciable. Cuando la función objetivo es diferenciable, los métodos de sub-gradiente para problemas no restringidos 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 el doble de funciones convexas continuamente diferenciables. Sin embargo, el método de Newton no logra converger en problemas que tienen torceduras 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 subgrado 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 subgrado se aplican a menudo a problemas a gran escala con técnicas de descomposición. Estos métodos de descomposición a menudo permiten un método distribuido simple para un problema.
Reglas clásicas de subgrado
Dejar ser una función convexa con dominio. Un método de subgradiente clásico itera
dónde denota cualquier subgrado de a , y es el iterar de . Si es diferenciable, entonces su único subgrado es el vector de gradiente sí mismo. Puede suceder que no es una dirección de descenso para a . Por lo tanto, mantenemos una lista que realiza un seguimiento del valor de función objetivo más bajo encontrado hasta ahora, es decir
Reglas de tamaño de paso
Los métodos de subgrado utilizan muchos tipos diferentes de reglas de tamaño de paso. Este artículo señala cinco reglas clásicas de tamaño de paso para las que se conocen las pruebas de convergencia :
- Tamaño de paso constante,
- Longitud de paso constante, , lo que da
- Tamaño de paso sumable cuadrado pero no sumable, es decir, cualquier tamaño de paso satisfactorio
- Disminución no acumulable, es decir, cualquier tamaño de paso satisfa
- Longitudes de paso decrecientes no sumables, es decir , dónde
Para las cinco reglas, los tamaños de paso se determinan "fuera de línea", antes de que se repita el método; los tamaños de los pasos no dependen de las iteraciones anteriores. Esta propiedad "fuera de línea" de los métodos de subgrado 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 las funciones diferenciables satisfacen las condiciones suficientes de Wolfe para la convergencia, donde los tamaños de paso normalmente dependen de el punto actual y la dirección de búsqueda actual. En los libros de Bertsekas [1] y de Bertsekas, Nedic y Ozdaglar se ofrece una amplia discusión de las reglas de tamaño de paso para métodos de subgrado, incluidas las versiones incrementales . [2]
Resultados de convergencia
Para subgradientes de longitud de paso constante y escalados que tienen una norma euclidiana igual a uno, el método de subgrado converge a una aproximación arbitrariamente cercana al valor mínimo, es decir
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 pueden adaptarse fácilmente para aprovechar la estructura especial del problema en cuestión.
Métodos de agrupación y proyección de subgrados
Durante la década de 1970, Claude Lemaréchal y Phil Wolfe propusieron "métodos combinados " de descenso para problemas de minimización convexa. [6] El significado del término "métodos combinados" ha cambiado significativamente desde entonces. Kiwiel proporcionó versiones modernas y análisis de convergencia completo. [7] Los métodos de agrupación 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 subgradientes" de Boris T. Polyak (1969). Sin embargo, existen problemas en los que los métodos combinados ofrecen pocas ventajas sobre los métodos de proyección de subgradientes. [4] [5]
Optimización con restricciones
Subgradiente proyectado
Una extensión del método de subgradiente es el método de subgradiente proyectado , que resuelve el problema de optimización restringida
- minimizar sujeto a
dónde es un conjunto convexo . El método de subgradiente proyectado usa la iteración
dónde es la proyección en y es cualquier subgrado de a
Limitaciones generales
El método de subgrado se puede extender para resolver el problema restringido por desigualdad
- minimizar sujeto a
dónde son convexas. El algoritmo toma la misma forma que el caso sin restricciones
dónde es un tamaño de paso, y es un subgradiente del objetivo o una de las funciones de restricción en Llevar
dónde denota el subdiferencial de. Si el punto actual es factible, el algoritmo usa un subgradiente objetivo; si el punto actual no es factible, el algoritmo elige un subgradiente de cualquier restricción violada.
Referencias
- ^ Bertsekas, Dimitri P. (2015). Algoritmos de optimización convexa (Segunda ed.). Belmont, MA .: Athena Scientific. ISBN 978-1-886529-28-1.
- ^ Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis convexo y optimización (Segunda ed.). Belmont, MA .: Athena Scientific. ISBN 1-886529-45-0.
- ^ La convergencia aproximada del método de subgradiente de tamaño de paso constante (escalado) se establece en el ejercicio 6.3.14 (a) en Bertsekas (página 636): Bertsekas, Dimitri P. (1999). Programación no lineal (Segunda ed.). 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.
- ^ a b 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 Schloß Dagstuhl, del 15 al 19 de mayo de 2000 . Apuntes de conferencias en Ciencias de la Computación. 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 .
- ^ a b Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (agosto de 2007). "Relajación lagrangiana a través de métodos de subgradiente ballstep" . Matemáticas de la investigación operativa . 32 (3): 669–686. doi : 10.1287 / moor.1070.0261 . Señor 2348241 .
- ^ Bertsekas, Dimitri P. (1999). Programación no lineal (Segunda ed.). Cambridge, MA .: Athena Scientific. ISBN 1-886529-00-0.
- ^ Kiwiel, Krzysztof (1985). Métodos de descenso para optimización no diferenciable . Berlín: Springer Verlag . pag. 362. ISBN 978-3540156420. Señor 0797754 .
Otras lecturas
- 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 convexo y optimización (Segunda ed.). 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, Nueva Jersey: Princeton University Press . págs. xii + 454. ISBN 978-0691119151. Señor 2199043 .
enlaces externos
- EE364A y EE364B , secuencia de curso de optimización convexa de Stanford.