Linear and nonlinear semidefinite relaxations of some NP-hard problems

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

Zhu, Tao

关键词: Non-deterministic Polynomial-time hard (NP-hard) problems;    Semidefinite Relaxation;    Quasi-convex Relaxation;    Nonlinear Semidefinite Relaxation;    Worst-case Linear Optimization;    Quadratic Assignment Problem;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/45327/Tao_Zhu.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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 procedureto 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.