HALO-LP: A Homogeneous All-Shifted Non-Interior-Point Method for Linear Programming
Authors: Jose Rojas, Ana Aguilar, Eusebio Bugarin
Organizations: Robot Motor Intelligence (RoMI) Lab – Heriot-Watt University, U.K. · Department of Electrical and Electronic Engineering, Tecnológico Nacional de México/I.T. Ensenada, Ensenada, B.C., Mexico.
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.
Figures & tables
Fig. 1: Warm-starting performance on perturbed instances of the Netlib test set for different perturbation magnitudes: (a) δ=0.001 , (b) δ=0.01 , and (c) δ=0.1 .
Case
HALO-LP
ProxQP
Clarabel
FBstab
Gurobi
Optimal
✓5
✓14
✓5
✓5
✓5
Primal infeas.
✓4
✓17
✓6
✓7
✓3
Dual infeas.
✓4
×692
✓6
✓6
✓4
TABLE I: Status agreement and solver-reported iterations on characterized LP problems. A check mark indicates correct classification.
Fig. 2: Unitree B1 walking using SLP with HALO-LP. (a) Snapshots of the optimized motion. (b) Optimized and reference forward CoM position. (c) Vertical contact forces at the four feet.
Fig. 3: ANYmal-C trotting using SLP with HALO-LP. (a) Snapshots of the optimized motion. (b) Optimized and reference forward CoM position. (c) Vertical contact forces at the four feet.
Interior-point methods (IPMs) are among the most widely used algorithms for constrained optimization, yet their Newton-based search directions require costly second-order information and large linear-system solves. Learning to optimize offers cheaper updates learned from data, but the singular behavior of logarithmic barriers near constraint boundaries makes IPMs highly sensitive to perturbations, complicating both warm starting and learning reliable updates. We introduce pdLIP, an IPM for smooth nonlinear programs that integrates learned preconditioning with pdProj, an all-shifted primal-dual projected-search IPM. A shared coordinate-wise recurrent network predicts a positive diagonal preconditioner that scales the right-hand side of the reduced Newton system for the primal step, and the remaining slack and multiplier directions are recovered analytically. The learned iterations avoid Hessian evaluations and Newton-system solves, using only first-order and coordinate-wise operations amenable to GPU parallelization. Training is self-supervised, with a loss based on a penalty-barrier merit function and the residual of perturbed optimality conditions, requiring neither target directions nor precomputed solutions. Primal and dual shifts mitigate the barrier's sensitivity to perturbations near constraint boundaries, enabling effective warm starting. Across four classes of 200-dimensional convex and nonconvex constrained problems, pdLIP warm starts reduce pdProj refinement iterations by 63-67% compared with cold starts at the same KKT residual tolerance of 10−8, with negligible warm-start generation cost relative to the subsequent pdProj solve. Improvements persist on box-constrained QPs with 1000 variables and extend to applications including portfolio optimization, support vector machines, and a nonlinear control example.
Abhinav Madabhushi, Jialin Liu, Minxin Zhang
Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida
Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of 1.9-5.6 and achieves up to a 16.0× speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs 3×-400× larger than the largest training instances, including Transport LPs with 10.24 million variables.
Large-scale linear programs with millions of variables and constraints strain time and memory budgets. First-order methods such as the primal-dual hybrid gradient scale to this regime because they avoid matrix factorizations, but they require many iterations. Learned accelerators can reduce these iterations, yet fewer iterations do not guarantee a shorter solve. Learning inference also takes time, and running the accelerator longer trades solver time for inference time. Existing unrolled accelerators handle this trade-off poorly: each layer processes every variable and constraint, the predicted iterates still need solver refinement, and every instance runs the same layers. We therefore ask: What neural accelerator design achieves end-to-end speedups on large-scale linear programs across sizes and target accuracies? We introduce AHEAD, an accelerator that predicts step sizes for first-order linear programming solvers while keeping their update rules. Its weight-shared predictor reads compact solver statistics and rescales the primal and dual step sizes, so each warm-start iteration stays inexpensive and a short warm-start phase hands the solver a warm start. A learned handoff policy sets the number of warm-start iterations for each instance and target accuracy, after which the solver finishes under its own termination criterion. On packing linear programs with up to 107 variables, AHEAD achieves 6.5--11.6× end-to-end speedups over Gurobi's first-order solver from a cold start, including on instances of unseen sizes and distributions. The gains extend to PageRank linear programs and hold across difficulty levels and target accuracies.
Sihao Liu, Zhichao Hou, Huayue Gu +4
North Carolina State University · Kennesaw State University · Nokia Applied Research