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.
Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida