When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

2024/11/24 by Wenzhi Gao, Gao, Wenzhi, Huikang Liu +5
Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2411.16015

openalex publication_date 2024/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence. The stability of the primal scaling matrix makes it possible to accelerate each primal IPM step using fast preconditioned iterative solvers for the normal equations. Crucially, we identify properties of the central path that make it possible to stabilize the normal equations. Experiments on benchmark datasets demonstrate the efficiency of primal IPM and showcase its potential for practical applications in linear optimization and beyond.

Related

• Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems
• Dual Interior Point Optimization Learning
• Primal-Dual Interior-Point Methods for Domain-Driven Formulations
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Proximal stabilized Interior Point Methods for quadratic programming and low-frequency-updates preconditioning techniques