Wolfe's minimum norm point method linked to simplex method shows exponential behavior
Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method
Data Structures and Algorithms
Summary
This paper studies a mathematical method called Wolfe's method, used to find the closest point within a shape formed by other points. The authors answer a long-standing question about whether this method always finishes quickly by showing that, in some cases, it can take an extremely long time to finish. They closely connect Wolfe's method to another well-known approach in optimization called the simplex method and use this link to prove new limits on how fast Wolfe's method can work. The results also reveal the complexity of deciding some behaviors of the method, impacting related algorithms in data fitting.
What this means in practice
- •For optimization algorithm designers: Avoid choosing certain Wolfe's method rules that can cause exponentially long runtimes when designing optimization procedures.
- •For software engineers using numerical solvers: Recognize when using Lawson-Hanson algorithms for data fitting might face worst-case exponential iteration counts due to Wolfe’s method behavior.
A theory result. No direct application yet.
Authors
Yann Disser, Nils Mosis
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.