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

Yann Disser, Nils Mosis

math.OC Nov 9, 2026 · v2 cs.DS

Read PDF arXiv abstract Code

TL;DR

The main theorem, corollaries and all numbered supporting statements were formally verified in Lean 4, with the artifact archived on Zenodo.

Abstract

Wolfe's method computes the point of minimum Euclidean norm in the convex hull of finitely many points. The method is parameterized by an insertion rule and it has been an open problem whether Wolfe's original rule guarantees a polynomial number of iterations (De Loera, Haddock, and Rademacher; STOC'18). We resolve this question by proving an exponential lower bound. In fact, we establish a tight connection to the simplex method for linear programming that allows us to transfer many lower bounds for simplex pivot rules to corresponding insertion rules of Wolfe's method. These include not only Wolfe's linopt rule via Dantzig's pivot rule, but also many other classical, randomized and history-based rules. As a corollary, we obtain the first exponential example for the Lawson-Hanson algorithm for nonnegative least squares, as well as PSPACE-hardness of deciding whether the linopt rule ever uses a given point.

Problem

It was open whether Wolfe's minimum-norm-point method with Wolfe's original linopt insertion rule runs in a polynomial number of iterations. The question was posed by De Loera, Haddock, and Rademacher at STOC'18.

Approach

A linear program satisfying integrality, boundedness and nondegeneracy is transformed into a minimum-norm-point instance. Simplex executions on the LP then correspond one-to-one with executions of Wolfe's method on the new instance. This correspondence carries lower bounds for simplex pivot rules over to the matching insertion rules of Wolfe's method. The main theorem, corollaries and supporting statements were formally verified in Lean 4.

Results

Wolfe's linopt rule takes exponentially many iterations, through Dantzig's pivot rule. Exponential or subexponential lower bounds also follow for least-index, least-inserted, round-robin and random insertion rules. Corollaries give the first exponential example for the Lawson-Hanson nonnegative least squares algorithm, and PSPACE-hardness of deciding whether linopt ever uses a given point.

Insertion rule	Pivot rule	Lower bound
linopt	Dantzig	Ω(2^{n/2})
least-index	Bland	Ω(2^{n/2})
least inserted	Zadeh	2^{Ω(n)}
round-robin	Cunningham	2^{Ω(n)}
random	Random-Edge	2^{Ω̃(n^{1/4})}

Insertion rules and transferred lower bounds (partial)

Papers With

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