El algoritmo de Frank-Wolfe es un iterativo de primer orden optimización algoritmo para constreñido convexa optimización . También conocido como el método de gradiente condicional , [1] algoritmo de gradiente reducido y el algoritmo de combinación convexa , el método fue propuesto originalmente por Marguerite Frank y Philip Wolfe en 1956. [2] En cada iteración, el algoritmo de Frank-Wolfe considera una aproximación lineal de la función objetivo, y se mueve hacia un minimizador de esta función lineal (asumida en el mismo dominio).
Planteamiento del problema
Suponer es un conjunto convexo compacto en un espacio vectorial yes una convexa , diferenciable función real . El algoritmo de Frank-Wolfe resuelve el problema de optimización
- Minimizar
- sujeto a .
Algoritmo
- Inicialización: Let , y deja ser cualquier punto en .
- Paso 1. Subproblema de radiogoniometría: encontrar resolviendo
- Minimizar
- Sujeto a
- (Interpretación: Minimice la aproximación lineal del problema dada por la aproximación de Taylor de primer orden de alrededor .)
- Paso 2. Determinación del tamaño de paso: Establecer , o alternativamente encontrar que minimiza sujeto a .
- Paso 3. Actualización: deje , dejar y vaya al paso 1.
Propiedades
Si bien los métodos de la competencia, como el descenso de gradiente para la optimización restringida, requieren un paso de proyección hacia el conjunto factible en cada iteración, el algoritmo de Frank-Wolfe solo necesita la solución de un problema lineal sobre el mismo conjunto en cada iteración, y automáticamente permanece en el factible colocar.
La convergencia del algoritmo de Frank-Wolfe es sublineal en general: el error en la función objetivo al óptimo es después de k iteraciones, siempre que el gradiente sea Lipschitz continuo con respecto a alguna norma. La misma tasa de convergencia también se puede mostrar si los subproblemas solo se resuelven aproximadamente. [3]
Las iteraciones del algoritmo siempre se pueden representar como una combinación convexa escasa de los puntos extremos del conjunto factible, lo que ha contribuido a la popularidad del algoritmo para la optimización codiciosa escasa en problemas de procesamiento de señales y aprendizaje automático , [4] así como por ejemplo, la optimización de los flujos de costo mínimo en las redes de transporte . [5]
Si el conjunto factible viene dado por un conjunto de restricciones lineales, entonces el subproblema a resolver en cada iteración se convierte en un programa lineal .
Mientras que la tasa de convergencia del peor de los casos con no se puede mejorar en general, se puede obtener una convergencia más rápida para clases de problemas especiales, como algunos problemas fuertemente convexos. [6]
Límites inferiores del valor de la solución y análisis primal-dual
Desde es convexo , para dos puntos cualesquiera tenemos:
Esto también es válido para la solución óptima (desconocida) . Es decir,. El mejor límite inferior con respecto a un punto dado es dado por
El último problema de optimización se resuelve en cada iteración del algoritmo de Frank-Wolfe, por lo tanto, la solución del subproblema de radiogoniometría del -th iteración se puede utilizar para determinar el aumento de los límites inferiores durante cada iteración configurando y
Dichos límites inferiores en el valor óptimo desconocido son importantes en la práctica porque pueden usarse como un criterio de parada y otorgan un certificado eficiente de la calidad de aproximación en cada iteración, ya que siempre .
Se ha demostrado que esta brecha de dualidad correspondiente , que es la diferencia entre y el límite inferior , disminuye con la misma tasa de convergencia, es decir
Notas
- ^ Levitina, ES; Polyak, BT (1966). "Métodos de minimización restringidos". URSS Matemáticas Computacionales y Física Matemática . 6 (5): 1. doi : 10.1016 / 0041-5553 (66) 90114-5 .
- ^ Frank, M .; Wolfe, P. (1956). "Un algoritmo para programación cuadrática". Trimestral de Logística de Investigación Naval . 3 (1–2): 95–110. doi : 10.1002 / nav.3800030109 .
- ^ Dunn, JC; Harshbarger, S. (1978). "Algoritmos de gradiente condicional con reglas de tamaño de paso de bucle abierto" . Revista de Análisis y Aplicaciones Matemáticas . 62 (2): 432. doi : 10.1016 / 0022-247X (78) 90137-3 .
- ^ Clarkson, KL (2010). "Coresets, escasa aproximación codiciosa y el algoritmo de Frank-Wolfe". Transacciones ACM sobre algoritmos . 6 (4): 1–30. CiteSeerX 10.1.1.145.9299 . doi : 10.1145 / 1824777.1824783 .
- ^ Fukushima, M. (1984). "Un algoritmo de Frank-Wolfe modificado para resolver el problema de asignación de tráfico". Investigación sobre transporte Parte B: Metodológica . 18 (2): 169-177. doi : 10.1016 / 0191-2615 (84) 90029-8 .
- ^ Bertsekas, Dimitri (1999). Programación no lineal . Athena Scientific. pag. 215. ISBN 978-1-886529-00-7.
Bibliografía
- Jaggi, Martin (2013). "Revisando Frank-Wolfe: optimización convexa dispersa libre de proyección" . Journal of Machine Learning Research: actas de talleres y conferencias . 28 (1): 427–435. (Documento de descripción general)
- Descripción del algoritmo de Frank-Wolfe
- Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1..
enlaces externos
- Marguerite Frank dando un relato personal de la historia del algoritmo
Ver también
- Métodos de gradiente proximal