CS Paper Radar

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

Yann Disser, Nils Mosis

cs.DS math.OC ·submitted 2026-11-09 16:45 UTC · v2
theory

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.

Comment
v2: Lean formalization archived at https://doi.org/10.5281/zenodo.24136107; author emails; minor corrections

Closest papers

Nearest neighbours by meaning across the whole index.

Spherical Convex Hull Membership: Complexity and Performance of Geometric and Accelerated Methods

cs.CG ·2026-10-14 ·Bahman Kalantari
benchmark similarity 0.65
Abstract · 18 pages, 3 tables

We study the problem of testing membership of the origin in the convex hull of $n$ unit vectors in $\mathbb{R}^m$, seeking a convex combination of norm at most $\varepsilon$ or a strict separating hyperplane. The Spherical Triangle Algorithm (STA) uses nearest-point updates on pivot segments. We first establish a conditional $O(1/\varepsilon)$ iteration bound from accumulated geometric progress, allowing deeper pivots to compensate for shallow ones. A three-point example shows that ordinary STA can require $Θ(\varepsilon^{-2})$ iterations. We show that the same conditional bound holds for STA with Wolfe minimum-norm correction (STA--WMC), provided the averaged geometric progress condition holds for the STA steps taken within this corrected method. We then combine STA, WMC, and the Nemirovski weighted-pivot method (NWP) in a hybrid with unconditional bounds of $O(\sqrt{\log n}/\varepsilon)$ matrix--vector products with the input matrix or its transpose and $O(mn\sqrt{\log n}/\varepsilon)$ arithmetic operations, including corrections. We also give a self-contained derivation of the $O(\sqrt{\log n}/\varepsilon)$ membership iteration bound for entropic Nesterov acceleration. Computationally, we compare five methods---ordinary STA, STA--WMC, the hybrid, standalone NWP, and entropic Nesterov acceleration---on convex-hull queries derived from 14 public benchmark datasets and on 204 controlled synthetic inputs. STA--WMC completes all cases in both comparisons, and the hybrid completes all public-data cases. STA performs well on favorable interior and separation instances; Nesterov acceleration is faster than the STA-based methods on the highest-dimensional random membership tests. The experiments show complementary strengths and distinguish practical performance from worst-case guarantees.

0.26

Newton Steps are Faster for Linear Complementarity Problems

cs.DS math.OC ·2026-11-05 ·Haoyuan Ma, László A. Végh, Adrian Vladu
similarity 0.63
Abstract

Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in their 1991 book, Kojima, Megiddo, Noma, and Yoshise introduced an interior point method (IPM) with running time that is polynomial in the input size, but which depends linearly on a certain parameter called the handicap number of the matrix. Despite the ensuing rich literature on sufficient LCP IPMs, the linear dependence on the handicap number has not been improved since then. We present an IPM whose running time depends on the square root of the handicap number. The algorithm can decrease the duality gap by a constant factor in $O\left(\min\left\{\sqrt{n} (1+κ),n^{9/8}\sqrt{1+κ}\right\}\right)$ iterations. Curiously, this can already be achieved using standard Newton updates. We analyze the IPM in a norm defined by a local weighting, where centralizing Newton steps quadratically converge to the central path, without any dependence on the handicap number. The weights arise from a characterization by Rump (Linear Algebra and Its Applications, 1997, 1998, 2003) of the sign-real spectral radius and its relation to sufficiency; another ingredient of our proof is a new operator norm characterization of the handicap number. Moreover, the connection to Rump's work also enables us to show coNP-completeness of testing sufficiency, and approximation hardness of the handicap number.

0.34

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

cs.LG math.OC ·2026-10-09 ·Sebastian Pokutta
theory similarity 0.62
Abstract

Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.

0.17

Row-Polar LP-Newton for Linear Programming with Corral Repair

cs.MS math.OCmath.NA ·2026-09-12 ·Yanfei Li, Yuki Matsuno, Jianming Shi
theory similarity 0.61
Abstract · 26 pages, 3 figures, 5 tables, 3 algorithms

LP-Newton solves a linear program through a sequence of nearest-point problems. Given an interior feasible point for an inequality-form LP, we construct the compact hull formed by the origin and its normalized constraint rows. Polar LP-Newton (P-LPN) follows the objective ray to the boundary of this row-polar hull, where it recovers a primal-dual optimum or a recession direction proving unboundedness. For rational row-polar data, we prove an outer-iteration bound quadratic in dimension and linear in binary input length, excluding inner Wolfe work. Restarting Wolfe at every outer iteration discards its terminal corral even though the hull is unchanged and the next target lies on the same ray. Corral-repair P-LPN (CR-P-LPN) instead repairs that corral and uses it to start the next projection. Verification over the full hull preserves P-LPN's projections, outer targets, and LP conclusion in exact arithmetic. Experiments in Julia and MATLAB show where repair helps. After common initialization, median P-LPN times across 180 single-LP tests are 1.62 times the corresponding CR-P-LPN times in Julia and 1.55 times in MATLAB. On three problems with 5,000 to 100,000 rows, the corresponding geometric-mean factors are 2.03 and 1.46. A separate end-to-end study includes initialization on 19 application-derived LPs. CR-P-LPN has lower median total time than the faster cold HiGHS mode, either dual simplex or the interior-point method with crossover, on 18 of the 19 workloads in each language. The geometric means of the ratios of HiGHS time to CR-P-LPN time are 4.93 and 3.06. Component comparisons identify terminal-corral reuse as the useful component, whereas candidate-first ordering alone shows no consistent gain. Repair is not always beneficial: it is slower on Klee-Minty tests, and an author-implemented simplex is faster on the retained Netlib models.

0.39

Escaping Degeneracy by Following Shadow Edges

cs.DS math.OC ·2026-10-08 ·Alexander E. Black, Sean Kafer, Laura Sanità
theory similarity 0.60
Abstract · 11 Pages

The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.

0.32

An iterative rounding $2$-approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

cs.DS ·2026-09-03 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
theory similarity 0.59
Abstract

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's by Bafna, Berman and Fujito (1995) and by Becker and Geiger (1996), and this approximation ratio is tight under UGC. The local-ratio algorithms were later interpreted as primal-dual algorithms via an LP relaxation by Chudak, Goemans, Hochbaum, and Williamson (1998). All known $2$-approximation algorithms for FVS have been via local-ratio and primal-dual methods, and in a quest to obtain a new LP rounding algorithm, it was conjectured (Fiorini 2021) that the Strong-Density polyhedron developed by Chudak, Goemans, Hochbaum, and Williamson has an extreme point property: every basic feasible solution to the LP has a variable with value at least $1/2$. We prove this conjecture. We also consider a related Strong-Edge-Density polyhedron and show the same extreme point property. The advantage of this polyhedron is that it admits a polynomial-time separation oracle and also a compact extended formulation. These results lead to polynomial-time iterative rounding $2$-approximation algorithms. The proof of the extreme point property is of independent technical interest and key ideas in the proof were suggested by AI tools.

0.31

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

cs.LG math.OC ·2026-09-20 ·Guy Kornowski
theoryhighly cited similarity 0.59
Abstract · 13 pages

We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.

0.54

A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

cs.DS cs.LGmath.FAmath.OC ·2026-09-24 ·Santosh S. Vempala
theory similarity 0.58
Abstract · toc, figures, fewer logs

We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.

0.54