Worst-case iteration count of Wolfe’s minimum-norm-point method

Wolfe’s method finds the point closest to the origin in the convex hull of a finite set. It updates a small active set by adding an improving point and dropping points as needed. How does the worst-case number of iterations depend on the rule that chooses which point to add?

Why it matters and what counts as progress

Why it matters: The minimum-norm-point problem appears in geometric and optimisation algorithms. Iteration bounds reveal whether a rule that works well in practice can still take exponentially many steps.

What counts as progress: Prove an iteration bound for a specified rule or give a family of inputs that forces many steps. A reduction can also transfer bounds between this method and another algorithm.

How the problem developed

  1. 1974 · Algorithm [3]

    Philip Wolfe Introduced the active-set method for finding a minimum-norm point in a convex hull.

  2. 2017 · Exponential example [3]

    Jesús A. De Loera, Jamie Haddock and Luis Rademacher Showed that the minimum-norm insertion rule can require exponentially many iterations.

  3. 9 Nov 2026 · Simplex reduction [1][2]

    Yann Disser and Nils Mosis with Claude Opus 5.5 Transferred lower bounds from simplex pivots to Wolfe insertions, including an exponential bound for the original linopt rule.

AI contribution

Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method

Yann Disser, Nils Mosis

Disser and Mosis give a polynomial-time reduction from bounded, nondegenerate linear programs with nn variables and mm equality constraints to minimum-norm-point instances on n+1n+1 integer points in dimension m+1m+1. The reduction matches sequences of simplex pivots with sequences of Wolfe insertions. It transfers an exponential lower bound from Dantzig’s pivot rule to Wolfe’s original linopt rule.

AI involvementAI-centered
ImportanceNotable
Technical verificationFormal (Lean 4 + human)
Human understandingExplained
Paper date:

Sources

  1. Disser and Mosis’s reduction from simplex to Wolfe iterations
  2. Lean 4 verification archive
  3. De Loera, Haddock and Rademacher, The Minimum Euclidean-Norm Point on a Convex Polytope
Publication history