Algoritmo de Frank-Wolfe

Algoritmo de optimización

El algoritmo de Frank-Wolfe es un algoritmo de optimización iterativo 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 avanza hacia un minimizador de esta función lineal (asumida en el mismo dominio).

Planteamiento del problema

Supongamos que es un conjunto convexo compacto en un espacio vectorial y es una función convexa y diferenciable de valor real . 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 radiogoniometría: encontrar solución ${\displaystyle \mathbf {s} _{k}}$

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

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

Paso 2. Determinación del tamaño del paso: establezca o, alternativamente, busque el que se minimice 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. Actualización: Deja , deja y ve 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 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 automáticamente permanece en el conjunto 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 se resuelven sólo de forma 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 contribuido a la popularidad del algoritmo para la optimización codiciosa dispersa en problemas de procesamiento de señales y aprendizaje automático , ^[4] así como por ejemplo, la optimización de flujos de costo mínimo en las redes de transporte . ^[5]

Si el conjunto factible está 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 del 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 dual primario

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) . Eso es, . El mejor límite inferior con respecto a un punto dado está 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 radiogoniometría de la -ésima iteración 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 pueden usarse como criterio de parada y dan un certificado eficiente de la calidad de la aproximación en cada iteración, desde 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. Levitina, ES; Polyak, BT (1966). "Métodos de minimización restringidos". Matemática Computacional 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". Logística de investigación naval trimestral . 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 y Aplicaciones Matemáticas . 62 (2): 432. doi : 10.1016/0022-247X(78)90137-3 .
4. Clarkson, KL (2010). "Coresets, aproximación escasa y 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. 
5. 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.
6. Bertsekas, Dimitri (1999). Programación no lineal . Atenas científica. pag. 215.ISBN​ 978-1-886529-00-7.

Bibliografía

• Jaggi, Martín (2013). "Revisando a Frank-Wolfe: optimización convexa dispersa sin proyecciones". Revista de investigación sobre aprendizaje automático: actas de talleres y conferencias . 28 (1): 427–435.(Documento general)
• La 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://condicional-gradients.org/: un estudio de los algoritmos de Frank-Wolfe.
• Marguerite Frank dando un relato personal de la historia del algoritmo.

Ver también

• Métodos de gradiente proximal