cs.ROOct 31, 2026

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.

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.

Figures & tables

Explore similar work

CardsList
  1. Learned Preconditioning for a Primal-Dual Interior-Point Method

    Sep 28, 2026Abhinav Madabhushi, Jialin Liu, Minxin ZhangPrimal-Dual OptimizationLearning to Optimize

  2. Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

    Oct 1, 2026Jinhwan Sul, Alex Oshin, Evangelos A. TheodorouPrimal-Dual OptimizationReinforcement Learning

  3. AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

    Oct 26, 2026Sihao Liu, Zhichao Hou, Huayue Gu +4Learning to OptimizeLinear Programming