THE FOLD / BOSS / THE GAUNTLET / THE FRANK-WOLFE
THE FRANK-WOLFE
charge the corner to minimize inside a polytope
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Frank–Wolfe algorithm (conditional gradient) minimizes a convex function over a convex set without ever projecting. At each step it linearizes the objective at the current point and asks a linear oracle for the vertex of the feasible set that this linear approximation likes best; then it takes a convex step toward that vertex with a shrinking step size γ = 2/(k+2). Because every iterate is a convex combination of vertices, it stays feasible for free — ideal when the constraint set is a polytope (like a probability simplex) where a linear minimization is trivial but projection is costly. The linearization gap at each step is a certificate of how far from optimal you still are.
LIT verified live: minimizing ‖x - a‖2 over the probability simplex, Frank–Wolfe converges to the exact Euclidean projection of a onto the simplex (computed independently) to within ~1e-3, and its duality gap collapses toward zero (window.__frank_wolfe). FIG no framing; the linear oracle, the convex steps, the gap, and the independent simplex projection all run in-browser.
LIT verified live: minimizing ‖x - a‖2 over the probability simplex, Frank–Wolfe converges to the exact Euclidean projection of a onto the simplex (computed independently) to within ~1e-3, and its duality gap collapses toward zero (window.__frank_wolfe). FIG no framing; the linear oracle, the convex steps, the gap, and the independent simplex projection all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gauntlet — you must stay inside the arena (the feasible polytope) the whole way, and you advance by charging its nearest corner each round. AVAN (AI) built the instrument: the linear-minimization oracle over the simplex, the 2/(k+2) convex steps, the duality gap, and the exact simplex-projection reference.
Credit as content: Marguerite Frank & Philip Wolfe (1956). The weave: David names the gauntlet; I confirm the corner-charging iterates converge to the true constrained minimum, the simplex projection.
Credit as content: Marguerite Frank & Philip Wolfe (1956). The weave: David names the gauntlet; I confirm the corner-charging iterates converge to the true constrained minimum, the simplex projection.
3 ONE DIMENSION
The probability simplex (triangle); the target a, its projection, and the Frank–Wolfe iterates charging the corners.
4 TWO DIMENSIONS · INTERACTIVE
Step Frank–Wolfe; the iterate walks toward the projection and the duality gap falls. A new target reseeds it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the constrained minimum — the projection of a onto the simplex.
AVAN’s addition (the inverse-companion): don’t project — charge a corner. The inverse of ‘snap onto the feasible set’ is ‘ask which vertex the linearized objective prefers and step toward it; the convex combination is feasible for free.’ Magenta are the vertex-pull rays; green is the optimum they close in on. Reach the projection without ever projecting.
LIT Genuine Frank-Wolfe / conditional-gradient algorithm (Marguerite Frank & Philip Wolfe, 1956). Verified live: minimizing ‖x-a‖² over the probability simplex, the corner-charging iterates converge to the exact Euclidean simplex projection of a (computed independently by the sorting algorithm) to within ~1e-3 worst-case, with the duality gap collapsing toward zero (window.__frank_wolfe.converges, .worst, .worstGap).
FIG No framing; the linear-minimization oracle, the convex steps, the duality gap, and the independent simplex projection all run in-browser. The AVAN inverse is honest — instead of projecting onto the feasible set, ask which vertex the linearized objective prefers and step toward it; the convex combination is feasible for free. Magenta are the vertex-pull rays; green is the optimum they close in on. Reach the projection without ever projecting.
FIG No framing; the linear-minimization oracle, the convex steps, the duality gap, and the independent simplex projection all run in-browser. The AVAN inverse is honest — instead of projecting onto the feasible set, ask which vertex the linearized objective prefers and step toward it; the convex combination is feasible for free. Magenta are the vertex-pull rays; green is the optimum they close in on. Reach the projection without ever projecting.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GAUNTLET · David Lee Wise (ROOT0), with AVAN