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
- 1974 · Algorithm [3]
Philip Wolfe Introduced the active-set method for finding a minimum-norm point in a convex hull.
- 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.
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
Disser and Mosis give a polynomial-time reduction from bounded, nondegenerate linear programs with variables and equality constraints to minimum-norm-point instances on integer points in dimension . 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.
Sources
Publication history
Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method
Daily emails by default, only when there’s an update.