Inexact PDHG for Large-Scale Semidefinite Programming
Abstract
First-order methods, such as the primal-dual hybrid gradient (PDHG) method, have recently been explored for large-scale semidefinite programming (SDP). However, exact projections can be computationally prohibitive, motivating inexact projections using conditional gradient methods. Although computationally cheap and projection-free, these methods typically converge sublinearly. Recent variants, such as Spectrahedron Frank-Wolfe (Garber, 2026), achieve linear convergence in expectation near the optimal face of the spectrahedron. We develop an inexact PDHG framework with tractable spectrahedral projections using two techniques: (i) adaptive error tolerances that avoid unnecessary inner iterations while guaranteeing convergence, and (ii) a heuristic spectral warm start based on the Lanczos algorithm that accelerates Spectrahedron Frank-Wolfe by initializing near the optimal face. We establish an O(1/t) convergence rate for PDHG in the presence of projection errors and estimate the total number of inner iterations required for convergence. Experiments on large-scale SDP instances demonstrate that combining spectral warm starts with Spectrahedron Frank-Wolfe outperforms Lanczos-based inexact projections.
Related
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
- An Adaptive, Parallel, and Inexact Newton Method for Large-scale Nonlinear Optimal Control
- Fast Randomized Entropically Regularized Semidefinite Programming
- H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
BibTeX
@misc{prakhya2026inexact,
title = {{Inexact PDHG for Large-Scale Semidefinite Programming}},
author = {Karthik Prakhya and Zimeng Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37998},
eprint = {2610.37998},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37998},
}
RIS
TY - UNPB
TI - Inexact PDHG for Large-Scale Semidefinite Programming
AU - Karthik Prakhya
AU - Zimeng Wang
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37998
UR - https://arxiv.org/abs/2610.37998
AB - First-order methods, such as the primal-dual hybrid gradient (PDHG) method, have recently been explored for large-scale semidefinite programming (SDP). However, exact projections can be computationally prohibitive, motivating inexact projections using conditional gradient methods. Although computationally cheap and projection-free, these methods typically converge sublinearly. Recent variants, such as Spectrahedron Frank-Wolfe (Garber, 2026), achieve linear convergence in expectation near the optimal face of the spectrahedron. We develop an inexact PDHG framework with tractable spectrahedral projections using two techniques: (i) adaptive error tolerances that avoid unnecessary inner iterations while guaranteeing convergence, and (ii) a heuristic spectral warm start based on the Lanczos algorithm that accelerates Spectrahedron Frank-Wolfe by initializing near the optimal face. We establish an O(1/t) convergence rate for PDHG in the presence of projection errors and estimate the total number of inner iterations required for convergence. Experiments on large-scale SDP instances demonstrate that combining spectral warm starts with Spectrahedron Frank-Wolfe outperforms Lanczos-based inexact projections.
ER -