CS Paper Radar

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

Yanfei Li, Yuki Matsuno, Jianming Shi

cs.MS math.OCmath.NA ·submitted 2026-09-12 07:01 UTC · v1
theory

Abstract

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.

Comment
26 pages, 3 figures, 5 tables, 3 algorithms

Closest papers

Nearest neighbours by meaning across the whole index.

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

HALO-LP: A Homogeneous All-Shifted Non-Interior-Point Method for Linear Programming

cs.RO ·2026-10-31 ·Jose Rojas, Ana Aguilar, Eusebio Bugarin
similarity 0.62
Abstract

This letter introduces HALO-LP, a novel homogeneous all-shifted non-interior-point method for linear programming (LP). The proposed method combines a homogeneous self-dual (HSD) embedding with all-shifted nonlinear complementarity (NCP) functions and proximal primal-dual regularization, enabling arbitrary primal-dual warm starts without requiring strictly interior iterates. The resulting Newton equations admit a condensation based on a positive-definite matrix that can be efficiently factorized using Cholesky decomposition, while the HSD embedding enables primal and dual infeasibility detection through Farkas certificates. Numerical evaluations on perturbed LP instances derived from the Netlib test set demonstrate state-of-the-art warm-starting performance, outperforming the competing solvers in the evaluated setting. We further validate optimality and infeasibility detection on analytically characterized LP problems. Finally, we demonstrate HALO-LP's applicability to robotic optimal control through sequential linear programming (SLP) for centroidal walking and trotting of quadrupedal robots.

0.30

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

cs.DS math.OC ·2026-11-09 ·Yann Disser, Nils Mosis
theory similarity 0.61
Abstract · v2: Lean formalization archived at https://doi.org/10.5281/zenodo.24136107; author emails; minor corrections

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.

0.29

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

Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning

cs.LG cs.CGmath.OC ·2026-10-03 ·Aoran Zhang, César A. Uribe
theory similarity 0.60
Abstract · 34 pages, 5 figures, 4 tables

The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG achieves a favorable balance of accuracy, objective value, feasibility, and stationarity relative to BAPG variants, projection-based methods, and task-specific baselines. For synthetic and real graph alignment problems, it closely matches the accuracy and objective value of fixed-penalty KL-BAPG while reducing the marginal feasibility gap by 62-99% and the projected stationarity residual by 28-98%. Heterogeneous domain adaptation experiments show a similar pattern: A-KL-BAPG maintains comparable target accuracy and objective values while achieving better feasibility and stationarity than fixed-penalty KL-BAPG.

0.22

Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time

cs.DS math.OC ·2026-10-19 ·Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh
published similarity 0.59
Abstract · This paper is based on the STOC 2024 proceedings paper "A strongly polynomial algorithm for linear programs with at most two nonzero entries…

Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.

0.30

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

cs.CG ·2026-10-14 ·Bahman Kalantari
benchmark similarity 0.59
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

Local LMO is Secretly a Projection Method!

cs.LG math.OC ·2026-09-27 ·Peter Richtárik, Ammar Mahran
similarity 0.59
Abstract

The local linear minimization oracle (Ferris and Zavriev, 1996; arXiv:2605.08850), or Local LMO, solves constrained convex problems without having to compute a projection: it minimizes a linear model over the intersection of the feasible set with a ball around the current iterate. We show that, whenever the ball radius does not exceed the Polyak radius, the Local LMO step is the Euclidean projection of the current iterate onto the intersection of the feasible set with a half-space that separates the iterate from the solution set; this projection is nonetheless computable by a linear oracle alone. We demonstrate that Local LMO belongs to a broader family of projection methods which may be indexed by the depth of the localizing half-space. For objectives with $\vartheta$-Hölder continuous gradient, every method from this family whose half-space lies sufficiently deep drives the best of its first $K$ iterates to optimality at the universal rate $\mathcal{O}(K^{-(1+\vartheta)/2})$, matching the non-accelerated universal gradient method of Nesterov (2015). Run at the Polyak radius, Local LMO attains the same rate when the constrained optima are also unconstrained ($\|\nabla f(x_\star)\| = 0$), and the rate $\mathcal{O}(K^{-1/(2-\vartheta)})$ otherwise.

0.50