Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Computation for Design and Optimization Program

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Yeung, Sai Hei

Advisor dc:contributor.advisor

• Robert M. Freund.

• Computation for Design and Optimization Program.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/43800

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/43800