{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/43800"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/43800","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Yeung, Sai Hei"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Computation for Design and Optimization Program","school":null,"contributors":[],"advisors":["Robert M. Freund."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:20:54Z","subjects":["Computation for Design and Optimization Program."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/43800","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Robert M. Freund."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."]},{"key":"dc:creator","label":"Author","values":["Yeung, Sai Hei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2008-12-11T18:29:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2008-12-11T18:29:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2008"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computation for Design and Optimization Program."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/43800"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008.","Includes bibliographical references (p. 75-76)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Robert M. Freund."],"dc:contributor.department":["Massachusetts Institute of Technology. Computation for Design and Optimization Program"],"dc:contributor.other":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."],"dc:creator":["Yeung, Sai Hei"],"dc:date.accessioned":["2008-12-11T18:29:36Z"],"dc:date.available":["2008-12-11T18:29:36Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008.","Includes bibliographical references (p. 75-76)."],"dc:description.abstract":["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."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/43800"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Computation for Design and Optimization Program."],"dc:title":["Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:54Z"}