A Max-Cut-specific graph neural network predicts primal- and dual-feasible SDP solutions in linearithmic time, cutting bounding costs in exact branch-and-bound by up to 10.6 times versus a commercial SDP solver while training without any solved SDP labels.
A Tuning-Free Primal-Dual Splitting Algorithm for Large-Scale Semidefinite Programming
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
This paper proposes and analyzes a tuning-free variant of Primal-Dual Hybrid Gradient (PDHG), and investigates its effectiveness for solving large-scale semidefinite programming (SDP). The core idea is based on the combination of two seemingly unrelated results: (1) the equivalence of PDHG and Douglas-Rachford splitting (DRS); (2) the asymptotic convergence of non-stationary DRS. This combination provides a unified approach to analyze the convergence of generic adaptive PDHG, including the proposed tuning-free algorithm and various existing ones. Numerical experiments are conducted to show the performance of our algorithm, highlighting its superior convergence speed and robustness in the context of SDP.
years
2026 2representative citing papers
PDHG converges locally linearly for SDP under strict complementarity or primal-dual nondegeneracy, and can converge sublinearly when both fail.
citing papers explorer
-
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
A Max-Cut-specific graph neural network predicts primal- and dual-feasible SDP solutions in linearithmic time, cutting bounding costs in exact branch-and-bound by up to 10.6 times versus a commercial SDP solver while training without any solved SDP labels.
-
Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming
PDHG converges locally linearly for SDP under strict complementarity or primal-dual nondegeneracy, and can converge sublinearly when both fail.