Mixed-Integer Nonconvex Quadratic Optimization Relaxations and Performance Analysis
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 11, 2016
- Accession Number
- AD1018669
Entities
People
- Yinyu Ye
Organizations
- Stanford University