Frank–Wolfe algorithm

The Frank–Wolfe algorithm is a simple iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method,^[1] reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956.^[2] In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves slightly towards a minimizer of this linear function (taken over the same domain).

Problem statement

Minimize

f(\mathbf {x} )

subject to

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

.

Where the function f is convex and differentiable, and the domain / feasible set ${\mathcal {D}}$ is convex and bounded.

Algorithm

Initialization. Let

k\leftarrow 0

and let

\mathbf {x} _{0}\!

be any point in

{\mathcal {D}}

.

Step 1. Direction-finding subproblem. Find

\mathbf {s} _{k}

solving

Minimize

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

Subject to

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

Interpretation: Minimize the linear approximation of the problem given by the first-order Taylor approximation of f around

\mathbf {x} _{k}\!

.

Step 2. Step size determination. Set

\gamma \leftarrow {\frac {2}{k+2}}

, or alternatively find

\gamma

that minimizes

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

subject to

0\leq \gamma \leq 1

.

Step 3. Update. Let

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

, let

k\leftarrow k+1

and go back to Step 1.

Properties

While competing methods such as gradient descent for constrained optimization require a projection step back to the feasible set in each iteration, the Frank–Wolfe algorithm only needs the solution of a linear problem over the same set in each iteration, and automatically stays in the feasible set.

The convergence of the Frank–Wolfe algorithm is sublinear in general: the error to the optimum is $O(1/k)$ after k iterations. The same convergence rate can also be shown if the sub-problems are only solved approximately.^[3]

The iterates of the algorithm can always be represented as a sparse convex combination of the extreme points of the feasible set, which has helped to the popularity of the algorithm for sparse greedy optimization in machine learning and signal processing problems,^[4] as well as for example the optimization of minimum–cost flows in transportation networks.^[5]

If the feasible set is given by a set of linear constraints, then the subproblem to be solved in each iteration becomes a linear program.

While the worst-case convergence rate with $O(1/k)$ can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.^[6]

Lower bounds on the solution value

Since $f$ is convex, $f(\mathbf {y} )$ is always above the tangent plane of $f$ at any point $\mathbf {x} \in {\mathcal {D}}$ :

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

This holds in particular for the optimal solution $\mathbf {x} ^{*}$ . The best lower bound with respect to a given point $\mathbf {x}$ is given by

f(\mathbf {x} ^{*})\geq \min _{\mathbf {x} \in D}f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )

The latter optimization problem is solved in every iteration of the Frank-Wolfe algorithm, therefore the solution $\mathbf {s} _{k}$ of the direction-finding subproblem of the $k$ -th iteration can be used to determine increasing lower bounds $u_{k}$ during each iteration by setting $u_{0}=-\infty$ and

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

Notes

^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0041-5553(66)90114-5, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0041-5553(66)90114-5 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1002/nav.3800030109, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1002/nav.3800030109 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0022-247X(78)90137-3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0022-247X(78)90137-3 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1824777.1824783, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1824777.1824783 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0191-2615(84)90029-8, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0191-2615(84)90029-8 instead.
^ Bertsekas, Dimitri (2003). Nonlinear Programming. Athena Scientific. p. 222. ISBN 1-886529-00-0.

Bibliography

Jaggi, Martin (2013). "Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization". Journal of Machine Learning Research: Workshop and Conference Proceedings. 28 (1): 427–435. (Overview paper)
The Frank-Wolfe algorithm description