Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/43800 |
| _version_ | 1824457821015506944 |
|---|---|
| author | Yeung, Sai Hei |
| author2 | Robert M. Freund. |
| author_facet | Robert M. Freund. Yeung, Sai Hei |
| author_sort | Yeung, Sai Hei |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008. |
| first_indexed | 2024-09-23T08:45:20Z |
| format | Thesis |
| id | mit-1721.1/43800 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:45:20Z |
| publishDate | 2008 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/438002022-01-13T07:54:53Z Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems Projective Re-Normalization method on semidefinite programming feasibility problems Yeung, Sai Hei Robert M. Freund. 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, 2008. Includes bibliographical references (p. 75-76). In this thesis, we study the Projective Re-Normalization method (PRM) for semidefinite programming feasibility problems. To compute a good normalizer for PRM, we propose and study the advantages and disadvantages of a Hit & Run random walk with Dikin ball dilation. We perform this procedure on an ill-conditioned two dimensional simplex to show the Dikin ball Hit & Run random walk mixes much faster than standard Hit & Run random walk. In the last part of this thesis, we conduct computational testing of the PRM on a set of problems from the SDPLIB [3] library derived from control theory and several univariate polynomial problems sum of squares (SOS) problems. Our results reveal that our PRM implementation is effective for problems of smaller dimensions but tends to be ineffective (or even detrimental) for problems of larger dimensions. by Sai Hei Yeung. S.M. 2008-12-11T18:29:36Z 2008-12-11T18:29:36Z 2008 2008 Thesis http://hdl.handle.net/1721.1/43800 261488559 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 76 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Computation for Design and Optimization Program. Yeung, Sai Hei Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title | Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title_full | Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title_fullStr | Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title_full_unstemmed | Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title_short | Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems |
| title_sort | analysis of the projective re normalization method on semidefinite programming feasibility problems |
| topic | Computation for Design and Optimization Program. |
| url | http://hdl.handle.net/1721.1/43800 |
| work_keys_str_mv | AT yeungsaihei analysisoftheprojectiverenormalizationmethodonsemidefiniteprogrammingfeasibilityproblems AT yeungsaihei projectiverenormalizationmethodonsemidefiniteprogrammingfeasibilityproblems |