betaFeedback

WorksMathematics

Strongly Monotone Central Path Equations for Quadratic Cone Programs

Abstract

We introduce a canonical central path for the homogeneous embedding of quadratic cone programs, defined by strongly monotone equations whose modulus is the barrier parameter. We prove that the path exists uniquely, is smooth, and lies on a sphere of fixed radius. Under mild regularity assumptions, its limit points recover optimal solutions or certificates of infeasibility. Exploiting the fact that the embedding operator has a closed-form resolvent, we derive Josephy-Newton steps that retain the nonlinear embedding equations and linearize only the complementarity conditions. Each step reduces to quasi-definite linear system solves and a scalar quadratic. Using this, we derive a new predictor-corrector interior-point method with a surrogate formulation that allows the predictor and corrector to share a single sparse factorization. We provide an open-source implementation, cpo3, for linear and quadratic programs. On 675 instances from eight benchmark collections, with presolve and crossover disabled, cpo3 achieves the highest verified solve count (631) and the lowest penalized shifted geometric mean runtime among the tested open-source and commercial solvers. It is the only tested solver to solve all 138 Maros-Meszaros instances to high accuracy. Moreover, we establish Euclidean and local-norm error bounds that motivate a warm-start heuristic for the proposed algorithm, yielding up to 2.3x median runtime speedup over cold starts on perturbed Netlib and Maros-Meszaros problems.

Paper details

vlnc:W_5vp7qty5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…