Frank-Wolfe-algoritme

Het Frank-Wolfe-algoritme, ook bekend als convexe-combinatiealgoritme, is een klassiek algoritme in het operationeel onderzoek (OR). Het werd in 1956 gepresenteerd door Marguerite Frank and Phil Wolfe als een procedure voor het oplossen van kwadratische programmeerproblemen met lineaire randvoorwaarden. Bij elke stap (iteratie) wordt de doelfunctie gelineariseerd en wordt een richting gekozen waarbij de doelfunctie wordt gereduceerd. Het algoritme kan worden gezien als een generalisatie van de simplexmethode voor lineair programmeren.

Probleemformulering

Minimaliseer ${\displaystyle f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }E\mathbf {x} +\mathbf {h} ^{\mathrm {T} }\mathbf {x} }$

met ${\displaystyle \mathbf {x} \epsilon \mathbf {P} }$.

Waarin de n×n matrix E positief-semidefiniet is, h een n×1 vector is, en ${\displaystyle \mathbf {P} }$ een mogelijk gebied definieert door een mix van lineaire ongelijkheden en gelijkheden (bijvoorbeeld Ax ≤ b, Cx = d).

Algoritme

Stap 1. Initialisatie. Laat ${\displaystyle k\leftarrow 0}$ en laat ${\displaystyle x_{0}}$ een punt zijn in ${\displaystyle \mathbf {P} }$.

Stap 2. Convergentietest. Indien ${\displaystyle \nabla f(x_{k})=0}$ stop, het minimum is gevonden.

Stap 3. Richting vinden door benadering van het probleem door vervangen van de functie f door een eerste-order Taylorreeks rond ${\displaystyle x_{k}}$. Los op voor ${\displaystyle {\bar {x}}_{k}}$:

Minimaliseer ${\displaystyle f(x_{k})+\nabla ^{T}f(x_{k}){\bar {x}}_{k}}$

Onder voorwaarde ${\displaystyle {\bar {x}}_{k}\epsilon \mathbf {P} }$

(LP) ${\displaystyle x_{k}}$ is vast in stap 3, terwijl de minimalisatie plaatsvindt door de ${\displaystyle {\bar {x}}_{k}}$ te variëren, en is equivalent aan de minimalisatie van ${\displaystyle \nabla ^{T}f(x_{k}){\bar {x}}_{k}}$).

Stap 4. Bepaal de stapgrootte. Vind ${\displaystyle \lambda }$ waarbij ${\displaystyle f(x_{k}+\lambda ({\bar {x}}_{k}-x_{k}))}$ wordt geminimaliseerd onder voorwaarde van ${\displaystyle 0\leq \lambda \leq 1}$. Als ${\displaystyle \lambda =0}$ stop, het minimum is gevonden.

Stap 5. Pas de waarden aan. Laat ${\displaystyle x_{k+1}\leftarrow x_{k}+\lambda ({\bar {x}}_{k}-x_{k})}$, laat ${\displaystyle k\leftarrow k+1}$ en ga naar stap 2.

Opmerkingen

Het algoritme gaat vlot bij de eerste iteraties maar het rendement neemt af naarmate het minimum wordt bereikt. De toepassing van het algoritme vindt onder andere plaats bij verkeersmodellen waarbij iteratief een evenwichtstoedeling van verkeersstromen wordt berekend.

Referenties

• M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), pp. 95–110.
• The Frank-Wolfe algorithm description
• Combined Traffic Signal Control and Traffic Assignment: Algorithms, Implementation and Numerical Results, Chungwon Lee and Randy B. Machemehl, University of Texas at Austin, March 2005