東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Linear and nonlinear semidefinite re...

Zhu, Tao.

Linked to FindBook

Google Book

Amazon

博客來

Linear and nonlinear semidefinite relaxations of some NP-hard problems.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Linear and nonlinear semidefinite relaxations of some NP-hard problems./
Author:	Zhu, Tao.
Description:	114 p.
Notes:	Source: Dissertation Abstracts International, Volume: 75-07(E), Section: B.
Contained By:	Dissertation Abstracts International75-07B(E).
Subject:	Operations Research. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3614760
ISBN:	9781303803611

Linear and nonlinear semidefinite relaxations of some NP-hard problems.
Zhu, Tao.

Linear and nonlinear semidefinite relaxations of some NP-hard problems. - 114 p.

Source: Dissertation Abstracts International, Volume: 75-07(E), Section: B.

Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2013.

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.

ISBN: 9781303803611Subjects--Topical Terms:

626629
Operations Research.

Linear and nonlinear semidefinite relaxations of some NP-hard problems.
LDR:02844nam a2200313 4500 001 1960639
005 20140623111242.5
008 150210s2013 ||||||||||||||||| ||eng d
020 $a 9781303803611
035 $a (MiAaPQ)AAI3614760
035 $a AAI3614760
040 $a MiAaPQ $c MiAaPQ
100 1 $a Zhu, Tao. $3 1951895
245 1 0 $a Linear and nonlinear semidefinite relaxations of some NP-hard problems.
300 $a 114 p.
500 $a Source: Dissertation Abstracts International, Volume: 75-07(E), Section: B.
500 $a Adviser: Jiming Peng.
502 $a Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2013.
520 $a 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.
520 $a 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.
520 $a 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 alpha and the CQCR model with alpha = 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.
590 $a School code: 0090.
650 4 $a Operations Research. $3 626629
650 4 $a Computer Science. $3 626642
650 4 $a Applied Mathematics. $3 1669109
690 $a 0796
690 $a 0984
690 $a 0364
710 2 $a University of Illinois at Urbana-Champaign. $b Industrial&Enterprise Sys Eng. $3 2096335
773 0 $t Dissertation Abstracts International $g 75-07B(E).
790 $a 0090
791 $a Ph.D.
792 $a 2013
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3614760