Algoritmo de Frank-Wulf

El algoritmo de Frank-Wulff [1] es un algoritmo iterativo de optimización de primer orden para la optimización convexa con restricciones . El algoritmo también se conoce como método de gradiente condicional [2] , método de gradiente reducido y algoritmo de combinación convexa . El método fue propuesto originalmente por Marguerite Frank y Philip Wolf en 1956 [3] . En cada iteración, el algoritmo de Frank-Wulff considera una aproximación lineal de la función objetivo y se mueve en la dirección de minimizar esta función lineal (en el mismo conjunto de soluciones factibles).

Planteamiento del problema

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

Minimizar

{\ estilo de visualización f (\ mathbf {x})}

proporcionado _

\mathbf {x} \in {\mathcal {D))

Algoritmo

Inicialización: Sea y sea un punto en .

{\ estilo de visualización k \ flecha izquierda 0}

{\ estilo de visualización \ mathbf {x} _ {0} \!}

\mathcal{D}

Paso 1. Subtarea de búsqueda de dirección: Find , resolviendo el problema

{\ estilo de visualización \ mathbf {s} _ {k}}

Minimizar

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

bajo condiciones

\mathbf {s} \in {\mathcal {D))

(Interpretación: minimizamos la aproximación lineal del problema obtenida por la aproximación de Taylor de primer orden de la función cerca de ).

F

{\ estilo de visualización \ mathbf {x} _ {k} \!}

Paso 2. Determinación del tamaño del paso: Sea , o, alternativamente, encuentre , que se minimiza bajo la condición .

{\ estilo de visualización \ gamma \ flecha izquierda {\ frac {2} {k + 2}}}

\gama

f(\mathbf {x}_{k}+\gamma (\mathbf {s}_{k}-\mathbf {x}_{k}))

0 \leqslant \gamma \leqslant 1

Paso 3. Recálculo: Establezca y vaya al paso 1.

\mathbf {x}_{k+1}\flecha izquierda \mathbf {x}_{k}+\gamma (\mathbf {s}_{k}-\mathbf {x}_{k})

{\ estilo de visualización k \ flecha izquierda k + 1}

Propiedades

Mientras que los métodos de la competencia, como el descenso de gradiente para la optimización restringida, requieren que cada iteración se proyecte en un conjunto de valores permitidos, el algoritmo de Frank-Wulf solo necesita resolver un problema de programación lineal en el mismo conjunto en cada iteración, por lo que la solución siempre permanece en el conjunto de soluciones factibles.

La convergencia del algoritmo de Frank-Wulf es generalmente sublineal: el error de la función objetivo con respecto al valor óptimo es después de k iteraciones, siempre que el gradiente sea Lipschitz continuo en alguna norma. La misma convergencia se puede mostrar si los subproblemas se resuelven solo aproximadamente [4] . ${\ estilo de visualización O (1/k)}$

Las iteraciones del algoritmo siempre se pueden representar como una combinación convexa no densa de puntos extremos del conjunto de soluciones factibles, lo que ha ayudado a la popularidad del algoritmo para problemas de optimización codiciosos dispersos en aprendizaje automático y procesamiento de señales [5] , como así como para encontrar flujos de costo mínimo en las redes de transporte [6] .

Si el conjunto de soluciones factibles está dado por un conjunto de desigualdades lineales, entonces el subproblema resuelto en cada iteración se convierte en un problema de programación lineal .

Aunque la tasa de convergencia del caso más desfavorable para el caso general no se puede mejorar, se pueden obtener tasas de convergencia más altas para problemas especiales como los problemas estrictamente convexos [7] . ${\ estilo de visualización O (1/k)}$

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

Como la función es convexa , para dos puntos cualesquiera tenemos: $F$ $\mathbf {x} ,\mathbf {y} \in {\mathcal {D))$

f(\mathbf {y} )\geqslant 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 considerando un punto viene dado por la fórmula ${\ estilo de visualización \ mathbf {x} ^ {*}}$ $f(\mathbf {x} ^{*})\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f (\mathbf{x})$ $\mathbf{x}$

{\begin{alineado}f(\mathbf {x} ^{*})&\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} ) ^{T}\nabla f(\mathbf {x} )\\&\geqslant \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{alineado))

Este último problema se resuelve en cada iteración del algoritmo de Frank-Wulff, por lo que la solución al subproblema de encontrar la dirección en la i-ésima iteración se puede usar para determinar límites inferiores crecientes en cada iteración asignando y ${\ estilo de visualización \ mathbf {s} _ {k}}$ $k$ ${\ Displaystyle l_ {k}}$ $l_{0}=-\infty$

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 sobre el valor óptimo desconocido son muy importantes en la práctica, ya que pueden usarse como criterio para detener el algoritmo y dar un indicador efectivo de la calidad de la aproximación en cada iteración, ya que siempre . $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x}_{k})$

Se ha demostrado que la brecha de dualidad , que es la diferencia entre y el límite inferior , disminuye al mismo ritmo, es decir ${\ estilo de visualización f (\ mathbf {x} _ {k})}$ ${\ Displaystyle l_ {k}}$ $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Notas

↑ El algoritmo fue desarrollado por Margarita Frank y Philip Wolf, por lo que el nombre Algoritmo Frank-Wulf , que es ampliamente utilizado en la literatura rusa , es erróneo.
↑ Levitin, Polyak, 1966 , p. 787-823.
↑ Frank y Wolfe, 1956 , pág. 95–110.
↑ Dunn y Harshbarger 1978 , pág. 432.
↑ Clarkson, 2010 , pág. 1–30.
↑ Fukushima, 1984 , pág. 169–177.
↑ Bertsekas, 1999 , pág. 215.

Literatura

Levitina E.S., Polyak B.T. Métodos de minimización en presencia de restricciones // Zh. Vychisl. Matemáticas. y estera física.- 1966.- V. 6 , núm. 5 . - doi : 10.1016/0041-5553(66)90114-5 .
Frank M., Wolfe P. Un algoritmo para programación cuadrática // Naval Research Logistics Quarterly. - 1956. - T. 3 , núm. 1–2 . — S. 95–110 . -doi : 10.1002/ nav.3800030109 .
Dunn JC, Harshbarger S. Algoritmos de gradiente condicional con reglas de tamaño de paso de ciclo abierto // Journal of Mathematical Analysis and Applications. - 1978. - T. 62 , núm. 2 . - art. 432 . - doi : 10.1016/0022-247X(78)90137-3 .
Clarkson KL Coresets, escasa aproximación codiciosa y el algoritmo Frank-Wolfe // Transacciones ACM en algoritmos. - 2010. - T. 6 , núm. 4 . — S. 1–30 . -doi : 10.1145/ 1824777.1824783 .
Un algoritmo de Frank-Wolfe modificado para resolver el problema de asignación de tráfico // Investigación de Transporte Parte B: Metodológica. - 1984. - T. 18 , núm. 2 . - doi : 10.1016/0191-2615(84)90029-8 .
Dimitri Bertsekas. programación no lineal. - Athena Scientific, 1999. - Pág. 215. - ISBN 978-1-886529-00-7 .
Martín Jaggi. Revisión de Frank–Wolfe: optimización convexa dispersa sin proyección // Journal of Machine Learning Research: actas de talleres y conferencias. - 2013. - T. 28 , núm. 1 . — S. 427–435 . (Artículo de revisión)
Descripción del algoritmo de Frank-Wulf
Jorge Nocedal, Stephen J. Wright. Optimización numérica. — 2do. - Berlín, Nueva York: Springer-Verlag , 2006. - ISBN 978-0-387-30303-1 .
Fukushima, M. (1984). "Un algoritmo de Frank-Wolfe modificado para resolver el problema de asignación de tráfico". Transporte Investigación Parte B: Metodológica . 18 (2): 169-177. DOI : 10.1016/0191-2615(84)90029-8 .

Enlace

Marguerite Frank dando un relato personal de la historia del algoritmo

Véase también

Método de gradiente proximal

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial