Frank–Wolfe algorithm explained

The Frank–Wolfe algorithm is an 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 towards a minimizer of this linear function (taken over the same domain).

Problem statement

Suppose

l{D}

is a compact convex set in a vector space and

f\colonl{D}\toR

is a convex, differentiable real-valued function. The Frank–Wolfe algorithm solves the optimization problem

Minimize

f(x)

subject to

x\inl{D}

.

Algorithm

Initialization: Let

k\leftarrow0

, and let

x0

be any point in

l{D}

.

Step 1. Direction-finding subproblem: Find

sk

solving

Minimize

sT\nablaf(xk)

Subject to

s\inl{D}

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

f

around

xk

constrained to stay within

l{D}

.)

Step 2. Step size determination: Set

\alpha\leftarrow

2
k+2
, or alternatively find

\alpha

that minimizes

f(xk+\alpha(sk-xk))

subject to

0\le\alpha\le1

.

Step 3. Update: Let

xk+1\leftarrowxk+\alpha(sk-xk)

, let

k\leftarrowk+1

and go 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 convex 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 in the objective function to the optimum is

O(1/k)

after k iterations, so long as the gradient is Lipschitz continuous with respect to some norm. The same convergence rate can also be shown if the sub-problems are only solved approximately.[3]

The iterations 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, and primal-dual analysis

Since

f

is convex, for any two points

x,y\inl{D}

we have:

f(y)\geqf(x)+(y-x)T\nablaf(x)

This also holds for the (unknown) optimal solution

x*

. That is,

f(x*)\gef(x)+(x*-x)T\nablaf(x)

. The best lower bound with respect to a given point

x

is given by

\begin{align} f(x*)&\gef(x)+(x*-x)T\nablaf(x)\ &\geqminy\left\{f(x)+(y-x)T\nablaf(x)\right\}\\ &=f(x)-xT\nablaf(x)+minyyT\nablaf(x) \end{align}

The latter optimization problem is solved in every iteration of the Frank–Wolfe algorithm, therefore the solution

sk

of the direction-finding subproblem of the

k

-th iteration can be used to determine increasing lower bounds

lk

during each iteration by setting

l0=-infty

and

lk:=max(lk,f(xk)+(sk-

T
x
k)

\nablaf(xk))

Such lower bounds on the unknown optimal value are important in practice because they can be used as a stopping criterion, and give an efficient certificate of the approximation quality in every iteration, since always

lk\leqf(x*)\leqf(xk)

.

It has been shown that this corresponding duality gap, that is the difference between

f(xk)

and the lower bound

lk

, decreases with the same convergence rate, i.e.

f(xk)-lk=O(1/k).

Bibliography

External links

See also

Notes and References

  1. Levitin . E. S. . Polyak . B. T. . 10.1016/0041-5553(66)90114-5 . Constrained minimization methods . USSR Computational Mathematics and Mathematical Physics . 6 . 5 . 1 . 1966 .
  2. Frank . M. . Wolfe . P. . 10.1002/nav.3800030109 . An algorithm for quadratic programming . Naval Research Logistics Quarterly . 3 . 1–2 . 95–110 . 1956 .
  3. Dunn . J. C. . Harshbarger . S. . 10.1016/0022-247X(78)90137-3 . Conditional gradient algorithms with open loop step size rules . Journal of Mathematical Analysis and Applications . 62 . 2 . 432 . 1978 . free .
  4. Clarkson . K. L. . Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm . 10.1145/1824777.1824783 . ACM Transactions on Algorithms . 6 . 4 . 1–30 . 2010 . 10.1.1.145.9299 .
  5. Fukushima . M. . A modified Frank-Wolfe algorithm for solving the traffic assignment problem . 10.1016/0191-2615(84)90029-8 . Transportation Research Part B: Methodological . 18 . 2 . 169–177. 1984 .
  6. Book: Bertsekas, Dimitri . Nonlinear Programming. 1999. 215. Athena Scientific. 978-1-886529-00-7.