Basis selection for SOS programs via facial reduction and polyhedral approximations
We develop a monomial basis selection procedure for sum-of-squares (SOS) programs based on facial reduction. Using linear programming and polyhedral approximations, the proposed technique finds a face of the SOS cone containing the feasible set of a given SOS program. The identified face in turn ide...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121514 |
| _version_ | 1811085413190729728 |
|---|---|
| author | Permenter, Frank Noble Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Permenter, Frank Noble Parrilo, Pablo A. |
| author_sort | Permenter, Frank Noble |
| collection | MIT |
| description | We develop a monomial basis selection procedure for sum-of-squares (SOS) programs based on facial reduction. Using linear programming and polyhedral approximations, the proposed technique finds a face of the SOS cone containing the feasible set of a given SOS program. The identified face in turn identifies a set of monomials that can be used to convert the SOS program into a semidefinite program (SDP). The technique can be viewed as a generalization of standard parsing algorithms for monomial basis selection. As we illustrate with examples, the proposed method can lead to smaller SDPs that are simpler to solve. |
| first_indexed | 2024-09-23T13:09:11Z |
| format | Article |
| id | mit-1721.1/121514 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:09:11Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1215142022-09-28T12:16:08Z Basis selection for SOS programs via facial reduction and polyhedral approximations Permenter, Frank Noble Parrilo, Pablo A. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Laboratory for Information and Decision Systems We develop a monomial basis selection procedure for sum-of-squares (SOS) programs based on facial reduction. Using linear programming and polyhedral approximations, the proposed technique finds a face of the SOS cone containing the feasible set of a given SOS program. The identified face in turn identifies a set of monomials that can be used to convert the SOS program into a semidefinite program (SDP). The technique can be viewed as a generalization of standard parsing algorithms for monomial basis selection. As we illustrate with examples, the proposed method can lead to smaller SDPs that are simpler to solve. 2019-07-08T15:49:59Z 2019-07-08T15:49:59Z 2015-02 2019-06-28T18:23:56Z Article http://purl.org/eprint/type/JournalArticle 0191-2216 https://hdl.handle.net/1721.1/121514 Permenter, Frank and Pablo a. Parrilo. "Basis selection for SOS programs via facial reduction and polyhedral approximations." In Proceedings of the IEEE Conference on Decision and Control, 53rd (February 2015). en 10.1109/CDC.2014.7040427 Proceedings of the IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Permenter, Frank Noble Parrilo, Pablo A. Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title | Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title_full | Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title_fullStr | Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title_full_unstemmed | Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title_short | Basis selection for SOS programs via facial reduction and polyhedral approximations |
| title_sort | basis selection for sos programs via facial reduction and polyhedral approximations |
| url | https://hdl.handle.net/1721.1/121514 |
| work_keys_str_mv | AT permenterfranknoble basisselectionforsosprogramsviafacialreductionandpolyhedralapproximations AT parrilopabloa basisselectionforsosprogramsviafacialreductionandpolyhedralapproximations |