Files in this item

FilesDescriptionFormat

application/pdf

application/pdfTao_Zhu.pdf (469kB)
(no description provided)PDF

Description

Title:Linear and nonlinear semidefinite relaxations of some NP-hard problems
Author(s):Zhu, Tao
Director of Research:Peng, Jiming
Doctoral Committee Chair(s):Peng, Jiming
Doctoral Committee Member(s):Nedich, Angelia; Beck, Carolyn L.; Kolla, Alexandra
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Non-deterministic Polynomial-time hard (NP-hard) problems
Semidefinite Relaxation
Quasi-convex Relaxation
Nonlinear Semidefinite Relaxation
Worst-case Linear Optimization
Quadratic Assignment Problem
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.
Issue Date:2013-08-22
URI:http://hdl.handle.net/2142/45327
Rights Information:Copyright 2013 Tao Zhu
Date Available in IDEALS:2013-08-22
Date Deposited:2013-08


This item appears in the following Collection(s)

Item Statistics