Finding sparse, equivalent SDPs using minimal coordinate projections
We present a new method for simplifying SDPs that blends aspects of symmetry reduction with sparsity exploitation. By identifying a subspace of sparse matrices that provably intersects (but doesn't necessarily contain) the set of optimal solutions, we both block-diagonalize semidefinite constra...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121539 |
| _version_ | 1811095834719158272 |
|---|---|
| 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 present a new method for simplifying SDPs that blends aspects of symmetry reduction with sparsity exploitation. By identifying a subspace of sparse matrices that provably intersects (but doesn't necessarily contain) the set of optimal solutions, we both block-diagonalize semidefinite constraints and enhance problem sparsity for many SDPs arising in sums-of-squares optimization. The identified subspace is in analogy with the fixed-point subspace that appears in symmetry reduction, and, as we illustrate, can be found using an efficient combinatorial algorithm that searches over coordinate projections. Effectiveness of the method is illustrated on several examples. |
| first_indexed | 2024-09-23T16:30:07Z |
| format | Article |
| id | mit-1721.1/121539 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:30:07Z |
| publishDate | 2019 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1215392022-10-02T08:10:27Z Finding sparse, equivalent SDPs using minimal coordinate projections Permenter, Frank Noble Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems We present a new method for simplifying SDPs that blends aspects of symmetry reduction with sparsity exploitation. By identifying a subspace of sparse matrices that provably intersects (but doesn't necessarily contain) the set of optimal solutions, we both block-diagonalize semidefinite constraints and enhance problem sparsity for many SDPs arising in sums-of-squares optimization. The identified subspace is in analogy with the fixed-point subspace that appears in symmetry reduction, and, as we illustrate, can be found using an efficient combinatorial algorithm that searches over coordinate projections. Effectiveness of the method is illustrated on several examples. 2019-07-09T15:03:39Z 2019-07-09T15:03:39Z 2015-12 2019-06-28T18:29:26Z Article http://purl.org/eprint/type/ConferencePaper 9781479978861 https://hdl.handle.net/1721.1/121539 Permenter, Frank, and Pablo A. Parrilo. “Finding Sparse, Equivalent SDPs Using Minimal Coordinate Projections.” 2015 54th IEEE Conference on Decision and Control (CDC), Osaka, Japan, 15-18 December 2015, IEEE, 2015, pp. 7274–79. en 10.1109/cdc.2015.7403367 2015 54th IEEE Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE MIT web domain |
| spellingShingle | Permenter, Frank Noble Parrilo, Pablo A. Finding sparse, equivalent SDPs using minimal coordinate projections |
| title | Finding sparse, equivalent SDPs using minimal coordinate projections |
| title_full | Finding sparse, equivalent SDPs using minimal coordinate projections |
| title_fullStr | Finding sparse, equivalent SDPs using minimal coordinate projections |
| title_full_unstemmed | Finding sparse, equivalent SDPs using minimal coordinate projections |
| title_short | Finding sparse, equivalent SDPs using minimal coordinate projections |
| title_sort | finding sparse equivalent sdps using minimal coordinate projections |
| url | https://hdl.handle.net/1721.1/121539 |
| work_keys_str_mv | AT permenterfranknoble findingsparseequivalentsdpsusingminimalcoordinateprojections AT parrilopabloa findingsparseequivalentsdpsusingminimalcoordinateprojections |