Low rank decompositions for sum of squares optimization
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/39210 |
| _version_ | 1826207322482933760 |
|---|---|
| author | Sun, Jia Li, S.M. Massachusetts Institute of Technology |
| author2 | Pablo A. Parrilo. |
| author_facet | Pablo A. Parrilo. Sun, Jia Li, S.M. Massachusetts Institute of Technology |
| author_sort | Sun, Jia Li, S.M. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. |
| first_indexed | 2024-09-23T13:47:31Z |
| format | Thesis |
| id | mit-1721.1/39210 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:47:31Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/392102019-04-10T13:49:28Z Low rank decompositions for sum of squares optimization Sun, Jia Li, S.M. Massachusetts Institute of Technology Pablo A. Parrilo. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Computation for Design and Optimization Program. Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. Includes bibliographical references (leaves 77-79). In this thesis, we investigate theoretical and numerical advantages of a novel representation for Sum of Squares (SOS) decomposition of univariate and multivariate polynomials. This representation formulates a SOS problem by interpolating a polynomial at a finite set of sampling points. As compared to the conventional coefficient method of SOS, the formulation has a low rank property in its constraints. The low rank property is desirable as it improves computation speed for calculations of barrier gradient and Hessian assembling in many semidefinite programming (SDP) solvers. Currently, SDPT3 solver has a function to store low rank constraints to explore its numerical advantages. Some SOS examples are constructed and tested on SDPT3 to a great extent. The experimental results demonstrate that the computation time decreases significantly. Moreover, the solutions of the interpolation method are verified to be numerically more stable and accurate than the solutions yielded from the coefficient method. by Jia Li Sun. S.M. 2007-10-19T20:31:37Z 2007-10-19T20:31:37Z 2006 2006 Thesis http://hdl.handle.net/1721.1/39210 85843740 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 79 leaves application/pdf Massachusetts Institute of Technology |
| spellingShingle | Computation for Design and Optimization Program. Sun, Jia Li, S.M. Massachusetts Institute of Technology Low rank decompositions for sum of squares optimization |
| title | Low rank decompositions for sum of squares optimization |
| title_full | Low rank decompositions for sum of squares optimization |
| title_fullStr | Low rank decompositions for sum of squares optimization |
| title_full_unstemmed | Low rank decompositions for sum of squares optimization |
| title_short | Low rank decompositions for sum of squares optimization |
| title_sort | low rank decompositions for sum of squares optimization |
| topic | Computation for Design and Optimization Program. |
| url | http://hdl.handle.net/1721.1/39210 |
| work_keys_str_mv | AT sunjialismmassachusettsinstituteoftechnology lowrankdecompositionsforsumofsquaresoptimization |