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.
Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis
原文摘要
We prove that, for every fixed $ε\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\vec c^{\top}\vec x$ subject to linear constraints, regardless of the pivot rule used. Our lower bound therefore holds for objectives arbitrarily close to the linear case $ε=0$, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. The special case $ε=1$ yields a lower bound in convex quadratic maximization. This improves on the best previously known lower bound [IPCO 2025] requiring polynomial objectives of degree $ω(\log d)$ in dimension $d$ and firmly resolves the open question of whether a constant degree suffices. Our result is based on a novel extended formulation, recursively constructed using deformed products. Its key feature is that it projects onto a polygonal approximation of a parabola while preserving all of its exponentially many vertices. We define a convex objective with a single non-linear variable that forces the active-set method to follow the parabolic boundary of this projection, without allowing any shortcuts along chords corresponding to edges of its full-dimensional preimage.