Mixed-Integer Nonconvex Quadratic Optimization Relaxations and Performance Analysis
Technical Report,15 Jul 2012,14 Jul 2016
Stanford University Stanford United States
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.