Algoritmo de Frank – Wolfe
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).
Suponga que es un conjunto convexo compacto en un espacio vectorial y es una función convexa diferenciable de valor real . El algoritmo de Frank-Wolfe resuelve el problema de optimización
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 continuo de Lipschitz 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 dispersa 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 .
