Linear and nonlinear semidefinite relaxations of some NP-hard problems

Zhu, Tao

Permalink

https://hdl.handle.net/2142/45327 Copy

Description

Title

Linear and nonlinear semidefinite relaxations of some NP-hard problems

Author(s)

Zhu, Tao

Issue Date

2013-08-22T16:36:44Z

Director of Research (if dissertation) or Advisor (if thesis)

Peng, Jiming

Doctoral Committee Chair(s)

Peng, Jiming

Committee Member(s)

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

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2013-08

Permalink

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

Copyright and License Information

Copyright 2013 Tao Zhu

Owning Collections