Algoritmo de Frank-Wolfe

El algoritmo de Frank-Wolfe es un algoritmo iterativo de optimización de primer orden para la optimización convexa con restricciones . 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 (tomada sobre el mismo dominio). 

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

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

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

Inicialización: Deje${\displaystyle k\leftarrow 0}$y dejar${\displaystyle \mathbf {x} _{0}\!}$ser cualquier punto en${\displaystyle {\mathcal {D}}}$.

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

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${\displaystyle f}$alrededor${\displaystyle \mathbf {x} _{k}\!}$obligado a permanecer dentro${\displaystyle {\mathcal {D}}}$.)

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

Paso 3. Actualización: Deje${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$, dejar${\displaystyle k\flecha izquierda k+1}$y vaya al Paso 1.

Mientras que otros métodos, como el descenso de gradiente para la optimización con restricciones, requieren un paso de proyección hacia atrás al 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 al óptimo es${\displaystyle O(1/k)}$después de k iteraciones, siempre que el gradiente sea Lipschitz continuo con respecto a alguna norma. La misma tasa de convergencia también puede demostrarse si los subproblemas se resuelven solo de forma aproximada. ^{[ 3 ]}

Las iteraciones del algoritmo siempre pueden representarse 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 voraz dispersa 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 con${\displaystyle O(1/k)}$En general, no se puede mejorar, pero se puede obtener una convergencia más rápida para clases de problemas especiales, como algunos problemas fuertemente convexos. ^{[ 6 ]}

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

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

Esto también se aplica a la solución óptima (desconocida).${\displaystyle \mathbf {x} ^{*}}$. Eso es,${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$. El mejor límite inferior con respecto a un punto dado${\displaystyle \mathbf {x} }$es dado por

${\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} \en 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${\displaystyle \mathbf {s} _{k}}$del subproblema de localización de direcciones del${\displaystyle k}$La -ésima iteración se puede utilizar para determinar límites inferiores crecientes.${\displaystyle l_{k}}$durante cada iteración mediante la configuración${\displaystyle l_{0}=-\infty }$y

${\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 pueden utilizarse como criterio de parada 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${\ Displaystyle f (\ mathbf {x} _ {k})}$y el límite inferior${\displaystyle l_{k}}$, disminuye con la misma tasa de convergencia, es decir ${\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).}$

El algoritmo de Frank-Wolfe se puede utilizar para calcular un equilibrio de Wardrop .

• Jaggi, Martin (2013). "Revisitando Frank–Wolfe: Optimización convexa dispersa sin proyección" . Journal of Machine Learning Research: Workshop and Conference Proceedings . 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..
• Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari y Sebastian Pokutta (2025). Métodos de gradiente condicional: desde los principios básicos hasta las aplicaciones de IA , SIAM (MOS-SIAM Series on Optimization), ISBN 978-1-61197-855-1.

• https://conditional-gradients.org/ : un estudio de los algoritmos de Frank-Wolfe.
• Marguerite Frank ofrece un relato personal de la historia del algoritmo.

• Métodos de gradiente proximal