Algorisme de Frank-Wolfe

L'algorisme de Frank-Wolfe és un algorisme iteratiu d'optimització de primer ordre per a l'optimització convexa restringida. També conegut com a mètode de gradient condicional,^[1] algorisme de gradient reduït i algorisme de combinació convexa, el mètode va ser proposat originalment per Marguerite Frank i Philip Wolfe a 1956.^[2] En cada iteració, l'algorisme de Frank-Wolfe considera una aproximació lineal de la funció objectiu i es mou cap a un minimitzador d'aquesta funció lineal (pres sobre el mateix domini).

Suposem ${\displaystyle {\mathcal {D}}}$ és un conjunt convex compacte en un espai vectorial i ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }$ és una funció convexa i diferenciable amb valors reals. L'algorisme de Frank-Wolfe resol el problema d'optimització

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

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

Inicialització: Deixeu ${\displaystyle k\leftarrow 0}$, i deixeu ${\displaystyle \mathbf {x} _{0}\!}$ ser qualsevol punt en ${\displaystyle {\mathcal {D}}}$.

Pas 1. Subproblema de radiogoniometria: Trobar ${\displaystyle \mathbf {s} _{k}}$ resolent

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

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

(Interpretació: Minimitzar l'aproximació lineal del problema donat per l'aproximació de Taylor de primer ordre de ${\displaystyle f}$ al voltant ${\displaystyle \mathbf {x} _{k}\!}$ obligat a quedar-se dins ${\displaystyle {\mathcal {D}}}$.)

Pas 2. Determinació de la mida del pas: Establir ${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$, o alternativament trobar ${\displaystyle \alpha }$ que minimitza ${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$ subjecte a ${\displaystyle 0\leq \alpha \leq 1}$.

Pas 3. Actualització: Deixeu ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$, deixem ${\displaystyle k\leftarrow k+1}$ i aneu al pas 1.

Mentre que els mètodes competidors, com ara el descens de gradient per a l'optimització restringida, requereixen un pas de projecció cap al conjunt factible en cada iteració, l'algorisme de Frank-Wolfe només necessita la solució d'un problema convex sobre el mateix conjunt en cada iteració i es manté automàticament al conjunt factible.

La convergència de l'algorisme de Frank-Wolfe és sublineal en general: l'error de la funció objectiu a l'òptim és ${\displaystyle O(1/k)}$ després de k iteracions, sempre que el gradient sigui continu de Lipschitz respecte a alguna norma. La mateixa taxa de convergència també es pot demostrar si els subproblemes només es resolen aproximadament.^[3]

Les iteracions de l'algorisme sempre es poden representar com una combinació convexa dispersa dels punts extrems del conjunt factible, cosa que ha contribuït a la popularitat de l'algorisme per a l'optimització voraç dispersa en problemes d'aprenentatge automàtic i processament de senyals,^[4] així com, per exemple, l'optimització de fluxos de cost mínim en xarxes de transport.^[5]

Si el conjunt factible ve donat per un conjunt de restriccions lineals, aleshores el subproblema a resoldre en cada iteració esdevé un programa lineal.

Mentre que la taxa de convergència del pitjor dels casos amb ${\displaystyle O(1/k)}$ no es pot millorar en general, es pot obtenir una convergència més ràpida per a classes de problemes especials, com ara alguns problemes fortament convexos.^[6]

Des de ${\displaystyle f}$ és convex, per a dos punts qualssevol ${\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}}$ tenim:

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

Això també és vàlid per a la solució òptima (desconeguda) ${\displaystyle \mathbf {x} ^{*}}$ És a dir, ${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$ El millor límit inferior respecte a un punt donat ${\displaystyle \mathbf {x} }$ ve donat per

${\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}}}$

Aquest darrer problema d'optimització es resol en cada iteració de l'algorisme de Frank-Wolfe, per tant, la solució ${\displaystyle \mathbf {s} _{k}}$ del subproblema de la radiogoniometria ${\displaystyle k}$ La iteració -èsima es pot utilitzar per determinar límits inferiors creixents ${\displaystyle l_{k}}$ durant cada iteració establint ${\displaystyle l_{0}=-\infty }$ i

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

Aquests límits inferiors del valor òptim desconegut són importants a la pràctica perquè es poden utilitzar com a criteri d'aturada i donen un certificat eficient de la qualitat de l'aproximació en cada iteració, ja que sempre ${\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}$.

L'algorisme de Frank-Wolfe es pot utilitzar per calcular un equilibri de Wardrop.