# Approximation algorithms for integer convex quadratic programs over a linear subspace

Consider the problem

$$\min_x \frac{1}{2} x^\top Q x + c^\top x \qquad \text{s.t.}\\ Ax=b\\ x \in \mathbb{Z}^n$$ where $$Q$$ is a positive (semi)definite matrix.

Clearly, feasibility can be decided in polynomial time. Given that the problem is feasible, are there (poly-time) approximate algorithms for this problem?

The problems is equivalent to the closest vector problem (CVP). This is because $$Ax=b, x\in \mathbb{Z}^n$$ is a lattice.

And the quadratic $$\frac{1}{2} x^\top Q x + c^\top x$$ can be written as $$\frac{1}{2}(x-d)^\top Q(x-d) - d^\top d$$ for a suitable choice of $$d$$ and the constant $$-d^\top d$$ can be dropped. Now, minimising $$\frac{1}{2}(x-d)^\top Q(x-d)$$ over a lattice (in this case $$Ax=b, x\in \mathbb{Z}^n$$ is basically the CVP, with a distance metric given by the positive definite matrix $$Q$$.

Thus, any approximation algorithm applicable for CVP is applicable here.

You might also want to note, no constant factor approximation is known for CVP. There are many approximation algorithms where the approximation factor depends on $$n$$, for example Babai's algorithm. Some notes are here.

There are numerous research papers on solving (mixed) integer quadratic programs (MIQP) such as paper #1, paper #2 and paper #3. These papers also give you pointers to various existing approaches for dealing with the same.

The modern optimization toolboxes (such as MATLAB and Gurobi) also support MIQP formulations.

• Yes, but as stated in the question, I am looking for poly-time approximation algorithms. For example, if the optimal objective value is $f^*$, then I need a poly-time algorithm which guarantees a solution with objective value $\hat{f} = k f^*$. Both the papers you have mentioned, as well as Gurobi/CPLEX etc provide exact solutions, which take exponential time in the worst case due to NP-hardness results. Commented Jun 3 at 9:43
• As I said, you can explore the related papers. You may end up finding works such as this Commented Jun 3 at 10:55