A Semidefinite Programming Method for Integer Convex Quadratic Minimization

Abstract

We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice ${\mathbf{Z}}^n$. We present a simple semidefinite programming (SDP) relaxation for obtaining a nontrivial lower bound on the optimal value of the problem. By interpreting the solution to the SDP relaxation probabilistically, we obtain a randomized algorithm for finding good suboptimal solutions, and thus an upper bound on the optimal value. The effectiveness of the method is shown for numerical problem instances of various sizes.

25 pages, 3 figures; to appear in Optimization Letters (OPTL)

References in corpus (1)

• Supersparse Linear Integer Models for Optimized Medical Scoring Systems

Cited by in corpus (8)

• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Bounds on quantum evolution complexity via lattice cryptography
• Integrability and complexity in quantum spin chains
• QArray: a GPU-accelerated constant capacitance model simulator for large quantum dot arrays
• SDP-based branch-and-bound for non-convex quadratic integer optimization
• Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints
• An SDP Relaxation for the Sparse Integer Least Squares Problem
• Evaluating Data-driven Performances of Mixed Integer Bilinear Formulations for Book Placement Planning