Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2306.15288 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929507113369600 |
|---|---|
| author | Zhang, Richard Y. |
| author_facet | Zhang, Richard Y. |
| contents | If a sparse semidefinite program (SDP), specified over $n\times n$ matrices and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with small treewidth, then chordal conversion will sometimes allow an interior-point method to solve the SDP in just $O(m+n)$ time per-iteration, which is a significant speedup over the $Ω(n^{3})$ time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by an $O(1)$ treewidth in $G$ that is independent of $m$ and $n$, as a diagonal SDP would have treewidth zero but can still necessitate up to $Ω(n^{3})$ time per-iteration. Instead, we construct an extended aggregate sparsity graph $\bar{G}\supseteq G$ by forcing each constraint matrix $A_{i}$ to be its own clique in $G$. We prove that a small treewidth in $\bar{G}$ does indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time per-iteration, to $ε$-accuracy in at most $O(\sqrt{m+n}\log(1/ε))$ iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-$k$-CUT relaxation, the Lovász theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_15288 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth Zhang, Richard Y. Optimization and Control If a sparse semidefinite program (SDP), specified over $n\times n$ matrices and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with small treewidth, then chordal conversion will sometimes allow an interior-point method to solve the SDP in just $O(m+n)$ time per-iteration, which is a significant speedup over the $Ω(n^{3})$ time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by an $O(1)$ treewidth in $G$ that is independent of $m$ and $n$, as a diagonal SDP would have treewidth zero but can still necessitate up to $Ω(n^{3})$ time per-iteration. Instead, we construct an extended aggregate sparsity graph $\bar{G}\supseteq G$ by forcing each constraint matrix $A_{i}$ to be its own clique in $G$. We prove that a small treewidth in $\bar{G}$ does indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time per-iteration, to $ε$-accuracy in at most $O(\sqrt{m+n}\log(1/ε))$ iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-$k$-CUT relaxation, the Lovász theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience. |
| title | Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2306.15288 |