Frank–Wolfe algorithm: Difference between revisions

Revision as of 22:58, 23 October 2013

Revision as of 22:42, 13 November 2013

Line 10:

[[File:Frank-Wolfe-Algorithm.png|thumbnail|right|A step of the Frank-Wolfe algorithm]]

:''Initialization.:'' Let <math>k \leftarrow 0</math>, and let <math>\mathbf{x}_0 \!</math> be any point in <math>\mathcal{D}</math>.

:'''Step 1.''' ''Direction-finding subproblem.:'' Find <math>\mathbf{s}_k</math> solving

::Minimize <math> \mathbf{s}^T, \nabla f(\mathbf{x}_k)</math>

::Subject to <math>\mathbf{s} \in \mathcal{D}</math>

:''(Interpretation: Minimize the linear approximation of the problem given by the first-order [[Taylor series|Taylor approximation]] of <math>f</math> around <math>\mathbf{x}_k \!</math>). ''

:'''Step 2.''' ''Step size determination.:'' Set <math>\gamma \leftarrow \frac{2}{k+2}</math>, or alternatively find <math>\gamma</math> that minimizes <math> f(\mathbf{x}_k+\gamma(\mathbf{s}_k -\mathbf{x}_k))</math> subject to <math>0 \le \gamma \le 1</math> .

:'''Step 3.''' ''Update.:'' Let <math>\mathbf{x}_{k+1}\leftarrow \mathbf{x}_k+\gamma(\mathbf{s}_k-\mathbf{x}_k)</math>, let <math>k \leftarrow k+1</math> and go back to Step 1.

==Properties==