Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916463147745280 |
|---|---|
| author | Tang, Tianyun Toh, Kim-Chuan |
| author_facet | Tang, Tianyun Toh, Kim-Chuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices Tang, Tianyun Toh, Kim-Chuan Optimization and Control 90C22, 90C25, 90C35 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. |
| title | Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices |
| topic | Optimization and Control 90C22, 90C25, 90C35 |
| url | https://arxiv.org/abs/2410.23849 |