↑ arvau

Wikipedia / Frank–Wolfe algorithm

The Frank–Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in1956. 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

is a compact convex set in a vector space is a convex, differentiable real-valued function. The Frank–Wolfe algorithm solves the optimization problem

  1. .

Algorithm

  1. Initialization:.

    Step 1. Direction-finding subproblem: solving

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

  3. Step 2. Step size determination: .

    Step 3. Update: 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.

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.

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, as well as for example the optimization of minimum–cost flowss in transportation networkss.

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.

can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.

Lower bounds on the solution value, and primal-dual analysis

is convex we have:

is given by

and

.

It has been shown that this corresponding duality gap

Applications

The Frank-Wolfe algorithm can be used to compute a Wardrop equilibrium.

Notes

Bibliography

  • (Overview paper)

  • The Frank–Wolfe algorithm description

  • .

  • Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari and Sebastian Pokutta (2025). Conditional Gradient Methods: From Core Principles to AI Applications, SIAM (MOS-SIAM Series on Optimization), ISBN 978-1-61197-855-1.

See also