Algoritmo de Frank-Wolfe

Algoritmo de optimización

El algoritmo de Frank-Wolfe es un algoritmo iterativo de optimización de primer orden para optimización convexa restringida . También conocido como método de gradiente condicional , ^[1] algoritmo de gradiente reducido y 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 (asumido sobre el mismo dominio).

Planteamiento del problema

Supongamos que es un conjunto convexo compacto en un espacio vectorial y es una función real convexa y diferenciable . El algoritmo de Frank-Wolfe resuelve el problema de optimización ${\displaystyle {\mathcal {D}}}$ ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }$

Minimizar ${\displaystyle f(\mathbf {x} )}$

sujeto a . ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$

Algoritmo

Un paso del algoritmo de Frank-Wolfe

Inicialización: Sea , y sea cualquier punto en . ${\displaystyle k\leftarrow 0}$ ${\displaystyle \mathbf {x} _{0}\!}$ ${\displaystyle {\mathcal {D}}}$

Paso 1. Subproblema de búsqueda de dirección: encontrar la solución ${\displaystyle \mathbf {s} _{k}}$

Minimizar ${\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}$

Sujeto a ${\displaystyle \mathbf {s} \in {\mathcal {D}}}$

(Interpretación: Minimizar la aproximación lineal del problema dada por la aproximación de Taylor de primer orden de alrededor de restringida a permanecer dentro de .) ${\displaystyle f}$ ${\displaystyle \mathbf {x} _{k}\!}$ ${\displaystyle {\mathcal {D}}}$

Paso 2. Determinación del tamaño del paso: Establezca , o alternativamente encuentre aquel que minimice el sujeto a . ${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$ ${\displaystyle \alpha }$ ${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$ ${\displaystyle 0\leq \alpha \leq 1}$

Paso 3. Actualizar: Deje , deje y vaya al Paso 1. ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$ ${\displaystyle k\leftarrow k+1}$

Propiedades

Mientras que los métodos competitivos, como el descenso de gradiente para la optimización restringida, requieren un paso de proyección hacia atrás hasta el conjunto factible en cada iteración, el algoritmo de Frank-Wolfe solo necesita la solución de un problema convexo sobre el mismo conjunto en cada iteración y permanece automáticamente en el conjunto factible.

La convergencia del algoritmo de Frank-Wolfe es sublineal en general: el error en la función objetivo hacia el óptimo se da 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 demostrar si los subproblemas se resuelven solo de manera aproximada. ^[3] ${\displaystyle O(1/k)}$

Las iteraciones del algoritmo siempre se pueden representar como una combinación convexa dispersa de los puntos extremos del conjunto factible, lo que ha ayudado a la popularidad del algoritmo para la optimización dispersa y codiciosa en problemas de aprendizaje automático y procesamiento de señales , ^[4] así como, por ejemplo, la optimización de flujos de costo mínimo en 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 .

Si bien la tasa de convergencia en el peor de los casos 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] ${\displaystyle O(1/k)}$

Límites inferiores del valor de la solución y análisis primal-dual

Como es convexo , para dos puntos cualesquiera tenemos: ${\displaystyle f}$ ${\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}}$

${\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$

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 viene dado por ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}$

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 búsqueda de dirección de la iteración -ésima se puede utilizar para determinar límites inferiores crecientes durante cada iteración estableciendo y ${\displaystyle \mathbf {s} _{k}}$ ${\displaystyle k}$ ${\displaystyle l_{k}}$ ${\displaystyle l_{0}=-\infty }$

${\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))}$

Estos límites inferiores del valor óptimo desconocido son importantes en la práctica porque se pueden utilizar como criterio de detención y proporcionan un certificado eficiente de la calidad de la aproximación en cada iteración, ya que siempre . ${\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}$

Se ha demostrado que esta brecha de dualidad correspondiente , es decir, la diferencia entre y el límite inferior , disminuye con la misma tasa de convergencia, es decir, ${\displaystyle f(\mathbf {x} _{k})}$ ${\displaystyle l_{k}}$ ${\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).}$

Notas

1. Levitin, ES; Polyak, BT (1966). "Métodos de minimización restringida". Matemáticas computacionales y física matemática de la URSS . 6 (5): 1. doi :10.1016/0041-5553(66)90114-5.
2. Frank, M.; Wolfe, P. (1956). "Un algoritmo para programación cuadrática". Naval Research Logistics Quarterly . 3 (1–2): 95–110. doi :10.1002/nav.3800030109.
3. Dunn, JC; Harshbarger, S. (1978). "Algoritmos de gradiente condicional con reglas de tamaño de paso de bucle abierto". Revista de análisis matemático y aplicaciones . 62 (2): 432. doi : 10.1016/0022-247X(78)90137-3 .
4. Clarkson, KL (2010). "Conjuntos de núcleos, aproximación ávida dispersa y el algoritmo Frank-Wolfe". ACM Transactions on Algorithms . 6 (4): 1–30. CiteSeerX 10.1.1.145.9299 . doi :10.1145/1824777.1824783. 
5. Fukushima, M. (1984). "Un algoritmo de Frank-Wolfe modificado para resolver el problema de asignación de tráfico". Investigación en transporte, parte B: Metodología . 18 (2): 169–177. doi :10.1016/0191-2615(84)90029-8.
6. Bertsekas, Dimitri (1999). Programación no lineal . Athena Scientific. pág. 215. ISBN 978-1-886529-00-7.

Bibliografía

• Jaggi, Martin (2013). "Revisitando Frank–Wolfe: Optimización convexa dispersa sin proyección". Journal of Machine Learning Research: Actas de talleres y congresos . 28 (1): 427–435.(Documento de resumen)
• 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

• https://conditional-gradients.org/: un estudio de los algoritmos de Frank-Wolfe.
• Marguerite Frank nos cuenta su historia personal sobre el algoritmo

Véase también

• Métodos de gradiente proximal