A semidefinite programming method for integer convex quadratic minimization
By Jaehyun Park, Stephen P. Boyd. 2015
60 citations recorded by the source corpus.
We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf{Z}}^n$$\end{document}. 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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
Citations in the corpus
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer (2020, background): “In general, integer quadratic programs are NP-hard [101, 102], so we will require a heuristic strategy that is computationally tractable.”