# A Semidefinite Programming Method for Integer Convex Quadratic Minimization

arXiv: https://arxiv.org/abs/1504.07672 · HTML: https://mlsanity.com/paper/1504.07672/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2015.

## Built on by (most cited first, 2 of 2)

- [Pruning vs Quantization: Which is Better?](https://mlsanity.com/paper/2307.02973/) (2023)
- [CDQuant: Greedy Coordinate Descent for Accurate LLM Quantization](https://mlsanity.com/paper/2406.17542/) (2024)

## Abstract (arXiv)

We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice bf Zn. 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.