Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices

2024/10/31 by Tianyun Tang, Tang, Tianyun, Kim-Chuan Toh +1 · 2 citations
Computer Science · Engineering · Mathematics · #90C22 #90C25 #90C35 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2410.23849

openalex publication_date 2024/10/31 · openalex created_date 2024/11/14 · openalex updated_date 2026/07/28

Abstract

Semidefinite programming (SDP) problems are challenging to solve because of their high dimensionality. However, solving sparse SDP problems with small tree-width are known to be relatively easier because: (1) they can be decomposed into smaller multi-block SDP problems through chordal conversion; (2) they have low-rank optimal solutions. In this paper, we study more general SDP problems whose coefficient matrices have sparse plus low-rank (SPLR) structure. We develop a unified framework to convert such problems into sparse SDP problems with bounded tree-width. Based on this, we derive rank bounds for SDP problems with SPLR structure, which are tight in the worst case.

Cited by

• Convex relaxation approaches for high-dimensional optimal transport
• cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming

Related

• Barrier and penalty methods for low-rank semidefinite programming with application to truss topology design
• Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity
• Sparse PSD approximation of the PSD cone