Accession Number:



Mixed-Integer Nonconvex Quadratic Optimization Relaxations and Performance Analysis

Descriptive Note:

Technical Report,15 Jul 2012,14 Jul 2016

Corporate Author:

Stanford University Stanford United States

Personal Author(s):

Report Date:


Pagination or Media Count:



This project considers a class of general quadratic optimization problems involving both integer and continuous variables. These problems are strongly motivated by applications in optimal and dynamic resource management, cardinality constrained quadratic programs, and the matrix completion problems with non-convex regularity. The project addresses a fundamental question how to efficiently solve these problems, such as to find a provably high quality approximate solution or to fast find a local solution with probable structure. Given the non-convex nature of these problems, two relaxation approaches are considered one is based on convex semidefinite relaxation SDR, while the other is based on quasi-convex relaxations QCR. In contrast to the classical mixed integer nonlinear programming approaches, no convexity is assumed for sub-problems when some integer variables are fixed. For the cardinality constrained QP problems, a QCR approach is proposed based on non-convex regularization. Compared to the known L1 relaxation, this relaxation gives better performance in practice. Below are selected highlight accomplishments made from the project.

Subject Categories:

Distribution Statement: