A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
Abstract
Semidefinite programming (SDP) is an important class of convex optimization problems with wide applications in practice. In this paper, we study a solution-selection question for first-order methods for solving SDPs: Can a first-order method provably select a strictly complementary solution when one exists, and a maximally complementary solution otherwise? We propose Triangular Log-Det PDHG (TriLog-PDHG), a primal-dual hybrid gradient method equipped with a triangular log-determinant Bregman kernel. We show that TriLog-PDHG converges to a KKT point for any fixed positive shift and to a maximally complementary solution for every sufficiently small positive shift. When a strictly complementary solution exists, the unshifted method provably selects a strictly complementary KKT point and enjoys a global linear convergence rate. Under the same condition, we further develop an averaged and adaptively restarted variant that accelerates convergence. Numerical experiments on classical examples and SDPLIB instances illustrate the complementarity-selection and convergence properties predicted by the theory.
Related
- Fast Randomized Entropically Regularized Semidefinite Programming
- Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- Inexact PDHG for Large-Scale Semidefinite Programming
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
BibTeX
@misc{ding2026triangular,
title = {{A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence}},
author = {Lijun Ding and Jinwen Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03638},
eprint = {2611.03638},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03638},
}
RIS
TY - UNPB
TI - A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
AU - Lijun Ding
AU - Jinwen Yang
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03638
UR - https://arxiv.org/abs/2611.03638
AB - Semidefinite programming (SDP) is an important class of convex optimization problems with wide applications in practice. In this paper, we study a solution-selection question for first-order methods for solving SDPs: Can a first-order method provably select a strictly complementary solution when one exists, and a maximally complementary solution otherwise? We propose Triangular Log-Det PDHG (TriLog-PDHG), a primal-dual hybrid gradient method equipped with a triangular log-determinant Bregman kernel. We show that TriLog-PDHG converges to a KKT point for any fixed positive shift and to a maximally complementary solution for every sufficiently small positive shift. When a strictly complementary solution exists, the unshifted method provably selects a strictly complementary KKT point and enjoys a global linear convergence rate. Under the same condition, we further develop an averaged and adaptively restarted variant that accelerates convergence. Numerical experiments on classical examples and SDPLIB instances illustrate the complementarity-selection and convergence properties predicted by the theory.
ER -