{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45327"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45327","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Linear and nonlinear semidefinite relaxations of some NP-hard problems","abstract":"Semidefinite relaxation (SDR) is a powerful tool to estimate bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of Quadratic Assignment Problem (QAP) based on matrix splitting. We characterize an optimal subset of all valid matrix splittings and propose a method to find them by solving a tractable auxiliary problem. A new matrix splitting scheme called sum-matrix splitting is also proposed and its numerical performance is evaluated. We next consider the so-called Worst-case Linear Optimization (WCLO) problem which has applications in systemic risk estimation and stochastic optimization. We show that WCLO is NP-hard and a coarse linear SDR is presented. An iterative procedure is introduced to sequentially refine the coarse SDR model and it is shown that the sequence of refined models converge to a nonlinear semidefinite relaxation (NLSDR) model. We then propose a bisection algorithm to solve the NLSDR in polynomial time. Our preliminary numerical results show that the NLSDR can provide very tight bounds, even the exact global solution, for WCLO. Motivated by the NLSDR model, we introduce a new class of relaxation called conditionally quasi-convex relaxation (CQCR). The new CQCR model is obtained by augmenting the objective with a special kind of penalty function. The general CQCR model has an undetermined nonnegative parameter $\\a$ and the CQCR model with $\\a = 0$ (denoted by CQCR(0)) is the strongest of all CQCR models. We next propose an iterative procedure to approximately solve CQCR(0) and a bisection procedure to solve CQCR(0) under some assumption. Preliminary numerical experiments illustrate the proposed algorithms are effective and the CQCR(0) model outperforms classic relaxation models.","abstract_html":"Semidefinite relaxation (SDR) is a powerful tool to estimate bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of Quadratic Assignment Problem (QAP) based on matrix splitting. We characterize an optimal subset of all valid matrix splittings and propose a method to find them by solving a tractable auxiliary problem. A new matrix splitting scheme called sum-matrix splitting is also proposed and its numerical performance is evaluated. We next consider the so-called Worst-case Linear Optimization (WCLO) problem which has applications in systemic risk estimation and stochastic optimization. We show that WCLO is NP-hard and a coarse linear SDR is presented. An iterative procedure is introduced to sequentially refine the coarse SDR model and it is shown that the sequence of refined models converge to a nonlinear semidefinite relaxation (NLSDR) model. We then propose a bisection algorithm to solve the NLSDR in polynomial time. Our preliminary numerical results show that the NLSDR can provide very tight bounds, even the exact global solution, for WCLO. Motivated by the NLSDR model, we introduce a new class of relaxation called conditionally quasi-convex relaxation (CQCR). The new CQCR model is obtained by augmenting the objective with a special kind of penalty function. The general CQCR model has an undetermined nonnegative parameter $\\a$ and the CQCR model with $\\a = 0$ (denoted by CQCR(0)) is the strongest of all CQCR models. We next propose an iterative procedure to approximately solve CQCR(0) and a bisection procedure to solve CQCR(0) under some assumption. Preliminary numerical experiments illustrate the proposed algorithms are effective and the CQCR(0) model outperforms classic relaxation models.","abstract_has_math":true,"creators":["Zhu, Tao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Peng, Jiming","Nedich, Angelia","Beck, Carolyn L.","Kolla, Alexandra"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:36:44Z","date_published":"2013-08-22T16:36:44Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Non-deterministic Polynomial-time hard (NP-hard) problems","Semidefinite Relaxation","Quasi-convex Relaxation","Nonlinear Semidefinite Relaxation","Worst-case Linear Optimization","Quadratic Assignment Problem"],"languages":["en"],"rights":["Copyright 2013 Tao Zhu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45327","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Peng, Jiming","Nedich, Angelia","Beck, Carolyn L.","Kolla, Alexandra"]},{"key":"dc:creator","label":"Author","values":["Zhu, Tao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:36:44Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Non-deterministic Polynomial-time hard (NP-hard) problems","Semidefinite Relaxation","Quasi-convex Relaxation","Nonlinear Semidefinite Relaxation","Worst-case Linear Optimization","Quadratic Assignment Problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Tao Zhu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45327"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Semidefinite relaxation (SDR) is a powerful tool to estimate bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of Quadratic Assignment Problem (QAP) based on matrix splitting. We characterize an optimal subset of all valid matrix splittings and propose a method to find them by solving a tractable auxiliary problem. A new matrix splitting scheme called sum-matrix splitting is also proposed and its numerical performance is evaluated. We next consider the so-called Worst-case Linear Optimization (WCLO) problem which has applications in systemic risk estimation and stochastic optimization. We show that WCLO is NP-hard and a coarse linear SDR is presented. An iterative procedure is introduced to sequentially refine the coarse SDR model and it is shown that the sequence of refined models converge to a nonlinear semidefinite relaxation (NLSDR) model. We then propose a bisection algorithm to solve the NLSDR in polynomial time. Our preliminary numerical results show that the NLSDR can provide very tight bounds, even the exact global solution, for WCLO. Motivated by the NLSDR model, we introduce a new class of relaxation called conditionally quasi-convex relaxation (CQCR). The new CQCR model is obtained by augmenting the objective with a special kind of penalty function. The general CQCR model has an undetermined nonnegative parameter $\\a$ and the CQCR model with $\\a = 0$ (denoted by CQCR(0)) is the strongest of all CQCR models. We next propose an iterative procedure to approximately solve CQCR(0) and a bisection procedure to solve CQCR(0) under some assumption. Preliminary numerical experiments illustrate the proposed algorithms are effective and the CQCR(0) model outperforms classic relaxation models.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-05-03T14:30:54Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Zhu_Tao.pdf: 468600 bytes, checksum: 05188029b0f1cb1f44cddcdea1e5af6b (MD5)","Made available in DSpace on 2013-08-22T16:36:44Z (GMT). No. of bitstreams: 2 Tao_Zhu.pdf: 468600 bytes, checksum: 05188029b0f1cb1f44cddcdea1e5af6b (MD5) license.txt: 4056 bytes, checksum: 560082fd2f7450a0904661aee172ac3c (MD5)"]},{"key":"dc:title","label":"Title","values":["Linear and nonlinear semidefinite relaxations of some NP-hard problems"]}]}],"canonical_facts":{"dc:contributor":["Peng, Jiming","Nedich, Angelia","Beck, Carolyn L.","Kolla, Alexandra"],"dc:creator":["Zhu, Tao"],"dc:date":["2013-08-22T16:36:44Z","2013-08"],"dc:description":["Semidefinite relaxation (SDR) is a powerful tool to estimate bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of Quadratic Assignment Problem (QAP) based on matrix splitting. We characterize an optimal subset of all valid matrix splittings and propose a method to find them by solving a tractable auxiliary problem. A new matrix splitting scheme called sum-matrix splitting is also proposed and its numerical performance is evaluated. We next consider the so-called Worst-case Linear Optimization (WCLO) problem which has applications in systemic risk estimation and stochastic optimization. We show that WCLO is NP-hard and a coarse linear SDR is presented. An iterative procedure is introduced to sequentially refine the coarse SDR model and it is shown that the sequence of refined models converge to a nonlinear semidefinite relaxation (NLSDR) model. We then propose a bisection algorithm to solve the NLSDR in polynomial time. Our preliminary numerical results show that the NLSDR can provide very tight bounds, even the exact global solution, for WCLO. Motivated by the NLSDR model, we introduce a new class of relaxation called conditionally quasi-convex relaxation (CQCR). The new CQCR model is obtained by augmenting the objective with a special kind of penalty function. The general CQCR model has an undetermined nonnegative parameter $\\a$ and the CQCR model with $\\a = 0$ (denoted by CQCR(0)) is the strongest of all CQCR models. We next propose an iterative procedure to approximately solve CQCR(0) and a bisection procedure to solve CQCR(0) under some assumption. Preliminary numerical experiments illustrate the proposed algorithms are effective and the CQCR(0) model outperforms classic relaxation models.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-05-03T14:30:54Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Zhu_Tao.pdf: 468600 bytes, checksum: 05188029b0f1cb1f44cddcdea1e5af6b (MD5)","Made available in DSpace on 2013-08-22T16:36:44Z (GMT). No. of bitstreams: 2 Tao_Zhu.pdf: 468600 bytes, checksum: 05188029b0f1cb1f44cddcdea1e5af6b (MD5) license.txt: 4056 bytes, checksum: 560082fd2f7450a0904661aee172ac3c (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/45327"],"dc:language":["en"],"dc:rights":["Copyright 2013 Tao Zhu"],"dc:subject":["Non-deterministic Polynomial-time hard (NP-hard) problems","Semidefinite Relaxation","Quasi-convex Relaxation","Nonlinear Semidefinite Relaxation","Worst-case Linear Optimization","Quadratic Assignment Problem"],"dc:title":["Linear and nonlinear semidefinite relaxations of some NP-hard problems"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}