Dimension reduction for semidefinite programs via Jordan algebras
We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal–dual pair over a lower-dimensional symmetric cone—na...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129071 |
| _version_ | 1826195121939415040 |
|---|---|
| author | Permenter, Frank Noble Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Permenter, Frank Noble Parrilo, Pablo A. |
| author_sort | Permenter, Frank Noble |
| collection | MIT |
| description | We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal–dual pair over a lower-dimensional symmetric cone—namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also show that minimizing rank optimizes the direct-sum decomposition of the algebra into simple ideals, yielding an optimal “block-diagonalization” of the SDP. Finally, we give combinatorial versions of our algorithm that execute at reduced computational cost and illustrate effectiveness of an implementation on examples. Through the theory of Jordan algebras, the proposed method easily extends to linear and second-order-cone programming and, more generally, symmetric cone optimization. |
| first_indexed | 2024-09-23T10:07:31Z |
| format | Article |
| id | mit-1721.1/129071 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:07:31Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1290712022-09-26T15:52:49Z Dimension reduction for semidefinite programs via Jordan algebras Permenter, Frank Noble Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal–dual pair over a lower-dimensional symmetric cone—namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also show that minimizing rank optimizes the direct-sum decomposition of the algebra into simple ideals, yielding an optimal “block-diagonalization” of the SDP. Finally, we give combinatorial versions of our algorithm that execute at reduced computational cost and illustrate effectiveness of an implementation on examples. Through the theory of Jordan algebras, the proposed method easily extends to linear and second-order-cone programming and, more generally, symmetric cone optimization. 2021-01-06T14:59:03Z 2021-01-06T14:59:03Z 2019-03 2016-12 2020-09-24T21:02:25Z Article http://purl.org/eprint/type/JournalArticle 1436-4646 https://hdl.handle.net/1721.1/129071 Permenter, Frank and Pablo A. Parrilo, "Dimension reduction for semidefinite programs via Jordan algebras." Mathematical Programming 181, 1 (March 2019): 51–84 doi. 10.1007/s10107-019-01372-5 ©2019 Authors en https://dx.doi.org/10.1007/s10107-019-01372-5 Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Permenter, Frank Noble Parrilo, Pablo A. Dimension reduction for semidefinite programs via Jordan algebras |
| title | Dimension reduction for semidefinite programs via Jordan algebras |
| title_full | Dimension reduction for semidefinite programs via Jordan algebras |
| title_fullStr | Dimension reduction for semidefinite programs via Jordan algebras |
| title_full_unstemmed | Dimension reduction for semidefinite programs via Jordan algebras |
| title_short | Dimension reduction for semidefinite programs via Jordan algebras |
| title_sort | dimension reduction for semidefinite programs via jordan algebras |
| url | https://hdl.handle.net/1721.1/129071 |
| work_keys_str_mv | AT permenterfranknoble dimensionreductionforsemidefiniteprogramsviajordanalgebras AT parrilopabloa dimensionreductionforsemidefiniteprogramsviajordanalgebras |