Linear and nonlinear semidefinite relaxations of some NP-hard problems

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Zhu, Tao

Contributors dc:contributor

• Peng, Jiming
• Nedich, Angelia
• Beck, Carolyn L.
• Kolla, Alexandra

• Non-deterministic Polynomial-time hard (NP-hard) problems
• Semidefinite Relaxation
• Quasi-convex Relaxation
• Nonlinear Semidefinite Relaxation
• Worst-case Linear Optimization
• Quadratic Assignment Problem

Statement dc:rights

• Copyright 2013 Tao Zhu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/45327

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/45327