Introduction

Imagine you want to minimize a smooth function over a constrained set โ€” say, pick the best portfolio of stocks subject to a budget. The standard gradient-descent recipe says: step opposite the gradient, then project back onto the feasible region. Easy to say, brutal to do โ€” projecting onto complicated sets is itself an expensive optimization problem.

In 1956, Marguerite Frank and Philip Wolfe proposed a radical shortcut: instead of projecting, ask a simpler question. Where in the feasible set does the linear approximation of the objective reach its minimum? That is just a linear program over the constraint set โ€” often trivially solved by inspection. Then blend the current point toward that vertex. No projection, ever.

The resulting algorithm โ€” variously called Frank-Wolfe, the conditional gradient method, or the linearized Bregman method โ€” trades a slower convergence rate for an enormous structural gift: the expensive projection oracle is simply not needed. When the feasible set has special structure (a simplex, a spectrahedron, a flow polytope), the linear subproblem can be solved in near-linear time while a full projection would cost orders of magnitude more.

Frank-Wolfe was largely forgotten for decades once interior-point methods arrived, but its revival in the 2000s and 2010s โ€” driven by machine learning workloads that involve nuclear-norm balls, traffic assignment, and structured sparsity โ€” placed it back at the frontier of large-scale optimization.

Watch It Zig-Zag

Below is Frank-Wolfe running on a quadratic objective minimized over a triangle (a 2-simplex). The shaded ellipses are level curves of the loss; the triangle is the feasible region. Each iteration finds the vertex of the triangle where the gradient points most steeply downward, then moves toward it with a fixed step size.

<div class="controls">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to end</button>
  <button id="reset" type="button" class="ghost">Reset</button>
  <span id="info" class="info"></span>
</div>
<canvas id="canvas" width="400" height="360"></canvas>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.info { font-size: .85rem; color: #555; margin-left: .3rem; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 8px; max-width: 100%; }
.log { font: .8rem/1.55 ui-monospace, monospace; color: #444; max-height: 100px;
       overflow-y: auto; margin-top: .4rem; background: #f6f8fa; border-radius: 6px;
       padding: .35rem .6rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Frank-Wolfe (conditional gradient) on a quadratic objective
// over the 2-simplex (triangle) in 2D.
//
// Objective: f(x,y) = (x - tx)^2 + (y - ty)^2  (distance from target)
// Feasible set: triangle with vertices A,B,C in canvas coords.
// FW step: s_k = argmin_{v in {A,B,C}} <grad f(x_k), v>   (linear oracle)
//          x_{k+1} = x_k + gamma * (s_k - x_k),  gamma = 2/(k+2)

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Triangle vertices in canvas space (pixel coords)
const VA = [200, 30];
const VB = [30,  330];
const VC = [370, 330];
const VERTS = [VA, VB, VC];

// Target point (minimizer of f inside or near feasible region)
let target = [220, 230];
let dragging = false;

// State
let iterates = [];   // each: {x, y}
let lsFw = [];       // each: {sx, sy} the Frank-Wolfe vertex chosen
let iter = 0;
const MAX_ITER = 20;

function reset() {
  // Start at centroid of triangle
  const x0 = (VA[0] + VB[0] + VC[0]) / 3;
  const y0 = (VA[1] + VB[1] + VC[1]) / 3;
  iterates = [{x: x0, y: y0}];
  lsFw = [];
  iter = 0;
  document.getElementById('log').textContent = '';
  updateInfo();
  draw();
}

function grad(px, py) {
  // gradient of (px-tx)^2 + (py-ty)^2
  return [2*(px - target[0]), 2*(py - target[1])];
}

function linearOracle(gx, gy) {
  // argmin_{v in VERTS} <g, v> = argmin gx*vx + gy*vy
  let best = null, bestVal = Infinity;
  for (const [vx, vy] of VERTS) {
    const val = gx * vx + gy * vy;
    if (val < bestVal) { bestVal = val; best = [vx, vy]; }
  }
  return best;
}

function doStep() {
  if (iter >= MAX_ITER) { updateInfo(); return; }
  const cur = iterates[iterates.length - 1];
  const [gx, gy] = grad(cur.x, cur.y);
  const [sx, sy] = linearOracle(gx, gy);
  const gamma = 2 / (iter + 2);   // standard FW step size
  const nx = cur.x + gamma * (sx - cur.x);
  const ny = cur.y + gamma * (sy - cur.y);
  lsFw.push({sx, sy});
  iterates.push({x: nx, y: ny});
  iter++;
  const gap = (cur.x-target[0])**2+(cur.y-target[1])**2;
  const logEl = document.getElementById('log');
  logEl.textContent += fmt('iter %iter%: FW vertex=(%sx%,%sy%)  ฮณ=%gamma%  gap=%gap%', { iter: iter, sx: sx.toFixed(0), sy: sy.toFixed(0), gamma: gamma.toFixed(3), gap: gap.toFixed(1) }) + "\n";
  logEl.scrollTop = logEl.scrollHeight;
  updateInfo();
  draw();
}

function runAll() {
  while (iter < MAX_ITER) doStep();
}

function updateInfo() {
  const cur = iterates[iterates.length - 1];
  const gap = (cur.x-target[0])**2+(cur.y-target[1])**2;
  const el = document.getElementById('info');
  if (iter >= MAX_ITER) el.textContent = fmt('Done (%MAX_ITER% iters) ยท gap=%gap%', { MAX_ITER: MAX_ITER, gap: gap.toFixed(1) });
  else el.textContent = iter === 0 ? 'At start โ€” press Step or Run' : fmt('Iter %iter% ยท gap=%gap%', { iter: iter, gap: gap.toFixed(1) });
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function drawLevelCurves() {
  // Draw ellipses = circles centred on target (since f is isotropic in canvas coords)
  ctx.save();
  ctx.strokeStyle = 'rgba(100,160,210,0.35)';
  ctx.lineWidth = 1;
  for (const r of [30, 60, 100, 150, 210, 280]) {
    ctx.beginPath();
    ctx.arc(target[0], target[1], r, 0, 2*Math.PI);
    ctx.stroke();
  }
  ctx.restore();
}

function drawTriangle() {
  ctx.save();
  ctx.beginPath();
  ctx.moveTo(VA[0], VA[1]);
  ctx.lineTo(VB[0], VB[1]);
  ctx.lineTo(VC[0], VC[1]);
  ctx.closePath();
  ctx.fillStyle = 'rgba(29,53,87,0.06)';
  ctx.fill();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  ctx.stroke();
  ctx.restore();
  // Label vertices
  ctx.save();
  ctx.font = 'bold 13px system-ui';
  ctx.fillStyle = '#1d3557';
  ctx.textAlign = 'center';
  ctx.fillText('A', VA[0], VA[1]-10);
  ctx.fillText('B', VB[0]-14, VB[1]+4);
  ctx.fillText('C', VC[0]+14, VC[1]+4);
  ctx.restore();
}

function drawPath() {
  if (iterates.length < 2) return;
  ctx.save();
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  ctx.moveTo(iterates[0].x, iterates[0].y);
  for (let i = 1; i < iterates.length; i++) {
    ctx.lineTo(iterates[i].x, iterates[i].y);
  }
  ctx.stroke();
  ctx.restore();
}

function drawIterates() {
  for (let i = 0; i < iterates.length; i++) {
    const {x, y} = iterates[i];
    const isLast = i === iterates.length - 1;
    ctx.beginPath();
    ctx.arc(x, y, isLast ? 6 : 4, 0, 2*Math.PI);
    ctx.fillStyle = isLast ? '#e63946' : 'rgba(230,57,70,0.5)';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.2;
    ctx.stroke();
  }
}

function drawFWArrows() {
  // Draw faint arrows from each iterate toward the chosen FW vertex
  ctx.save();
  ctx.strokeStyle = 'rgba(0,120,80,0.5)';
  ctx.lineWidth = 1;
  for (let i = 0; i < lsFw.length; i++) {
    const {x, y} = iterates[i];
    const {sx, sy} = lsFw[i];
    ctx.beginPath();
    ctx.moveTo(x, y);
    ctx.lineTo(sx, sy);
    ctx.stroke();
    // arrowhead
    const ang = Math.atan2(sy-y, sx-x);
    const tip = [sx, sy];
    ctx.beginPath();
    ctx.moveTo(tip[0], tip[1]);
    ctx.lineTo(tip[0]-10*Math.cos(ang-0.35), tip[1]-10*Math.sin(ang-0.35));
    ctx.lineTo(tip[0]-10*Math.cos(ang+0.35), tip[1]-10*Math.sin(ang+0.35));
    ctx.closePath();
    ctx.fillStyle = 'rgba(0,120,80,0.4)';
    ctx.fill();
  }
  ctx.restore();
}

function drawTarget() {
  // Draw a star symbol at target
  const [tx, ty] = target;
  ctx.save();
  ctx.fillStyle = '#f4a261';
  ctx.strokeStyle = '#e76f51';
  ctx.lineWidth = 1.5;
  const r1 = 10, r2 = 5, n = 5;
  ctx.beginPath();
  for (let i = 0; i < 2*n; i++) {
    const r = i % 2 === 0 ? r1 : r2;
    const ang = (Math.PI * i / n) - Math.PI/2;
    const px = tx + r * Math.cos(ang);
    const py = ty + r * Math.sin(ang);
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  }
  ctx.closePath();
  ctx.fill();
  ctx.stroke();
  ctx.restore();
}

function draw() {
  ctx.clearRect(0, 0, W, H);
  drawLevelCurves();
  drawTriangle();
  drawFWArrows();
  drawPath();
  drawIterates();
  drawTarget();
}

// โ”€โ”€ Drag target โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function ptInTriangle(px, py) {
  // Check if point is inside (or near) triangle using barycentric coords
  const [ax,ay]=VA, [bx,by]=VB, [cx,cy]=VC;
  const d0=(px-bx)*(ay-by)-(ax-bx)*(py-by);
  const d1=(px-cx)*(by-cy)-(bx-cx)*(py-cy);
  const d2=(px-ax)*(cy-ay)-(cx-ax)*(py-ay);
  return (d0>=0&&d1>=0&&d2>=0)||(d0<=0&&d1<=0&&d2<=0);
}

canvas.addEventListener('mousedown', e => {
  const r = canvas.getBoundingClientRect();
  const mx = (e.clientX - r.left) * (W/r.width);
  const my = (e.clientY - r.top) * (H/r.height);
  const [tx, ty] = target;
  if (Math.hypot(mx-tx, my-ty) < 18) { dragging = true; }
});
canvas.addEventListener('mousemove', e => {
  if (!dragging) return;
  const r = canvas.getBoundingClientRect();
  const mx = (e.clientX - r.left) * (W/r.width);
  const my = (e.clientY - r.top) * (H/r.height);
  target = [mx, my];
  reset();
});
canvas.addEventListener('mouseup', () => { dragging = false; });
canvas.addEventListener('mouseleave', () => { dragging = false; });

// Touch support
canvas.addEventListener('touchstart', e => {
  e.preventDefault();
  const r = canvas.getBoundingClientRect();
  const t = e.touches[0];
  const mx = (t.clientX - r.left) * (W/r.width);
  const my = (t.clientY - r.top) * (H/r.height);
  const [tx, ty] = target;
  if (Math.hypot(mx-tx, my-ty) < 24) dragging = true;
}, {passive:false});
canvas.addEventListener('touchmove', e => {
  e.preventDefault();
  if (!dragging) return;
  const r = canvas.getBoundingClientRect();
  const t = e.touches[0];
  const mx = (t.clientX - r.left) * (W/r.width);
  const my = (t.clientY - r.top) * (H/r.height);
  target = [mx, my];
  reset();
}, {passive:false});
canvas.addEventListener('touchend', () => { dragging = false; });

document.getElementById('step').addEventListener('click', doStep);
document.getElementById('run').addEventListener('click', runAll);
document.getElementById('reset').addEventListener('click', reset);

reset();
Result
Console

Notice the zig-zag pattern: because each step is attracted to a vertex of the feasible polytope, the iterates bounce between corners before settling near the true minimum. This is Frank-Wolfe's signature behavior โ€” and also its main weakness: the zig-zagging slows convergence compared to gradient descent with projection. The trade-off is that each step costs far less.

Press Reset to restart from the initial point, or drag the target point (the star) to explore different optima. Compare linear programming to see why finding a vertex of a polytope is so cheap.

The Real Complexity

Frank-Wolfe belongs firmly in the solved camp: its convergence is fully understood, with both upper and lower bounds tight.

  • Convergence rate: O(1/k)O(1/k). After k iterations, the suboptimality gap is at most O(Lยทdiam2diam^{2}/k), where L is the Lipschitz constant of the gradient and diam is the diameter of the feasible set. Proved by Frank and Wolfe in their 1956 paper and tightened by subsequent work.
  • Each iteration costs one gradient evaluation plus one linear minimization over the feasible set โ€” the linear oracle. For polytopes this is an LP with structure; for a simplex it reduces to finding the minimum-gradient coordinate; for a spectrahedron it is a leading eigenvector computation.
  • Slower than projected gradient descent. Standard projected gradient descent achieves O(1/k)O(1/k) too, but with a smaller constant โ€” and accelerated variants reach O(1/k2)O(1/k^{2}). Frank-Wolfe cannot be accelerated beyond O(1/k)O(1/k) for general convex objectives without further assumptions (a proven lower bound).
  • Away-step and pairwise variants (Lacoste-Julien & Jaggi, 2015) achieve linear convergence (exponential in k) on strongly convex problems with polytope constraints, recovering the speed advantage while keeping the projection-free property.
  • Sparsity of iterates. Because each step moves toward a vertex, Frank-Wolfe solutions are always sparse convex combinations of at most k+1 vertices after k steps. This is not just a nicety โ€” in machine learning it means structured, interpretable solutions automatically.

The algorithm's status: solved and well-characterized. The open questions are about tighter constants, fine-grained oracle complexity, and whether gap-free analysis extends to non-convex settings.

Where It Matters

Frank-Wolfe's projection-free nature is decisive whenever the feasible set is easier to optimize a linear function over than to project onto:

  • Traffic assignment (Beckmann model): Routing traffic on a road network minimizes a separable convex cost. The linear oracle is just shortest-path computation โ€” trivial. Projection onto the flow polytope is far harder. Frank-Wolfe has been the standard solver here since the 1970s.
  • Nuclear-norm regularization (matrix completion): Minimizing over the nuclear-norm ball means the linear oracle is a leading singular-vector computation โ€” O(mn)O(mn) per step. Projection requires full SVD at O(mnยทmin(m,n)). Frank-Wolfe wins by orders of magnitude on large matrices.
  • Structural SVM and learning with structured outputs: The feasible set of valid label assignments defines a combinatorial polytope. Frank-Wolfe's linear oracle is finding the highest-scoring label structure โ€” exactly what a standard decoder does.
  • Video object co-localization: Joint optimization over bounding boxes in multiple frames is a quadratic program whose linear oracle is an easy box search.
  • Neural network compression: Weights constrained to a low-rank or sparse polytope can be optimized with Frank-Wolfe without expensive projection steps.

Whenever you see a constrained optimization problem where the domain has combinatorial or spectral structure, the first question worth asking is: "how hard is the linear subproblem?" If the answer is "easy," Frank-Wolfe is the right tool โ€” even compared to methods like linear programming that handle the global problem at once.

Conclusion

Frank-Wolfe is a masterclass in trading one hard operation for an easier one. By replacing the projection step with a linear minimization โ€” often a hundred times cheaper โ€” it opens up entire classes of large-scale problems that would otherwise be inaccessible.

The zig-zag path is not a bug. It is the geometric signature of an algorithm that lives at the vertices of the feasible set, producing sparse, structured solutions almost for free. When you next encounter a constrained optimization problem where the feasible region has rich combinatorial structure, remember: the best move might not be to project โ€” it might be to ask which direction is cheapest, and just lean that way.

Explore the companion article on linear programming to see why solving a linear subproblem over a polytope is so much cheaper than you might expect.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/frank-wolfe/Content licensed under CC BY-NC 4.0.