A One-Factorization Predictor-Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding
Abstract
In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that avoids this second factorization, retains the corrector after the arc step, and uses only one KKT factorization per iteration. The key is a three-term decomposition of the complementarity mismatch at the selected point on the arc, which allows the correction to be assembled from linear-system solutions using the factorization at the current iterate. We also propose a curvature-amplified variant (CA-OFAS) that amplifies the second-order arc term. The proposed methods are formulated with a homogeneous self-dual embedding. For a wide long-step neighborhood, we prove that both methods reduce the homogeneous complementarity and residuals below ε in O(n log(1/ε)) iterations for an n-by-n SDP matrix variable. Numerical experiments show that the one-factorization structure and the correction after the arc step are associated with reductions in computation time. Compared with the Mehrotra-type method, CA-OFAS reduces the geometric-mean computation time by 17% on SDPLIB and 13% on neural network verification SDP problems.
Related
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
- A robust multi-step predictor-corrector method for solving fractional order biological models
- Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
- High-Order Predictor–Corrector Schemes for the Simultaneous Computation of Polynomial Roots with Known Multiplicities: Order Analysis and the Role of a Scalar-Derived Correction Factor
- Comparing SGLD and a fixed-noise predictor-corrector adaptation in canonical joint energy-based models on CIFAR-10
BibTeX
@misc{yamashita2026onefactorization,
title = {{A One-Factorization Predictor-Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding}},
author = {Makoto Yamashita and Yaguang Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34275},
eprint = {2609.34275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34275},
}
RIS
TY - UNPB
TI - A One-Factorization Predictor-Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding
AU - Makoto Yamashita
AU - Yaguang Yang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34275
UR - https://arxiv.org/abs/2609.34275
AB - In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that avoids this second factorization, retains the corrector after the arc step, and uses only one KKT factorization per iteration. The key is a three-term decomposition of the complementarity mismatch at the selected point on the arc, which allows the correction to be assembled from linear-system solutions using the factorization at the current iterate. We also propose a curvature-amplified variant (CA-OFAS) that amplifies the second-order arc term. The proposed methods are formulated with a homogeneous self-dual embedding. For a wide long-step neighborhood, we prove that both methods reduce the homogeneous complementarity and residuals below ε in O(n log(1/ε)) iterations for an n-by-n SDP matrix variable. Numerical experiments show that the one-factorization structure and the correction after the arc step are associated with reductions in computation time. Compared with the Mehrotra-type method, CA-OFAS reduces the geometric-mean computation time by 17% on SDPLIB and 13% on neural network verification SDP problems.
ER -