The Frank-Wolfe Method

Frank-Wolfe minimizes a smooth function over a convex set using only linear subproblems, never projecting back onto the set.

Projection-free optimization

Projected gradient methods keep iterates feasible by projecting after each step, but projection can be expensive, for example onto the nuclear-norm ball or a large polytope. The Frank-Wolfe method, also called the conditional gradient method, avoids projection entirely. It only ever solves a linear minimization over the feasible set, which is often far cheaper than projection.

The iteration

At x_k, linearize the objective and find the feasible vertex that minimizes the linear approximation: s_k = argmin_{s in C} grad f(x_k)^T s. Then move toward that vertex with a step size gamma_k in [0,1]: x_{k+1} = (1 - gamma_k) x_k + gamma_k s_k. Because the update is a convex combination of feasible points, the iterate stays feasible automatically, and a common step size is gamma_k = 2/(k+2).

import numpy as np

def frank_wolfe(grad_f, lmo, x0, iters=200):
    # lmo(g) returns argmin_{s in C} g^T s (the linear oracle)
    x = x0
    for k in range(iters):
        s = lmo(grad_f(x))
        gamma = 2.0/(k+2)
        x = (1-gamma)*x + gamma*s
    return x

Structured, sparse iterates

Each step adds one vertex (an atom) to the solution, so after k steps the iterate is a combination of at most k vertices. Over an L1 ball the vertices are signed unit basis vectors, so iterates are sparse; over the nuclear-norm ball the atoms are rank-one, so iterates are low rank. This makes Frank-Wolfe attractive when structured, interpretable solutions are wanted and the linear oracle is cheap.

Convergence and limits

Frank-Wolfe converges at O(1/k) for smooth convex objectives and comes with a built-in duality gap grad f(x_k)^T (x_k - s_k) that certifies how close the current point is to optimal. Its weakness is that iterates can zig-zag toward a solution lying on a face of the set, slowing progress; away-step and pairwise variants remove atoms as well as add them to fix this and can achieve linear convergence on polytopes.