On Quadratic Integer Programming

Question

I have the quadratic integer program over $\mathbb{Z}^n$

$\displaystyle\min_{z \in \mathbb{Z}^n} \Phi (z) = \frac{1}{2} z^T Q z - r^T z + s$

subject to $G z = h$, and $z_i \in \{0,1,2,\dots, b_i\}$ for all $i \in \{1,2,\dots,n\}$, where $Q$ is symmetric positive-definite. Moreover, $G, h$ are integer-valued and, thus, I suppose that $\{z \in \mathbb{Z}^n : G z = h\}$ defines a sublattice of $\mathbb{Z}^n$.

Let us suppose we solve the relaxed quadratic program over $\mathbb{R}^n$

$\displaystyle\min_{x \in \mathbb{R}^n} \Psi (x) = \frac{1}{2} x^T Q x - r^T x + s$

subject to $G x = h$, and $0 \leq x_i \leq b_i$ for all $i \in \{1,2,\dots,n\}$. Let $x_{opt} \in \mathbb{R}^n$ be the minimizer of $\Psi$. We can define an $n$-cube (in $\mathbb{Z}^n$) containing $x_{opt}$ by taking the floor/ceil of each component of $x_{opt}$. We intersect this $n$-cube with the integer sublattice defined by $G z = h$, and evaluate $\Phi$ at all points of this intersection. Let $z^{\ast}$ be the point in such intersection that minimizes $\Phi$. Let $z_{opt}$ be the minimizer of the original quadratic integer program. Can we say that $z_{opt} = z^*$? I know nothing of integer programming, so I preemptively apologize if my question is silly / elementary...

In other words, can one solve a quadratic integer program by solving a relaxed quadratic real program, and then searching in the neighborhood of the real solution? This seems to work for $n = 1$ and $n = 2$... but it also seems too good to be true in general. If in general $z_{opt} \neq z^{\ast}$, can we (at least) quantify how sub-optimal $z^{\ast}$ is?

Any feedback will be most welcome!

Answer 1

The relaxed quadratic programming problem is a red herring. It is true that quadratic programming over $\mathbb{R}$ with linear inequalities can be solved in practice, for one reason because it is a special case of convex programming. But in the stated question, the inequality $0 \le x_i \le b_i$ came from nowhere. The correct relaxation is even simpler: You should just minimize $\Phi(z)$ over all of $\mathbb{R}^n$, and the minimum is directly at $z_0 = Q^{-1}r$.

After that, Mitch is roughly correct. The question as stated is exactly the closest vector problem, which is related to the shortest vector problem that Mitch mentions. The constant $s$ is not important. The question is to find the integer lattice point $z$ which is the closest to $z_0$ in the metric defined by $Q$. If you like, you can change distance to Euclidean distance, and change the lattice from the standard integer lattice to something else, by applying the operator $Q^{-1/2}$. $L = Q^{-1/2}(\mathbb{Z}^n)$ is a certain lattice, and you are looking for the point which is the closest in Euclidean distance to $Q^{-1/2}(z_0)$.

In any fixed dimension $n$, the closest and shortest vector problems can be solved in polynomial time. There are various lattice reduction algorithms that only search polynomially many points.

If the dimension $n$ is a parameter, then the situation is very different. For many purposes, people are happy with just a close vector or a short vector, not necessarily the closest or shortest one. The problem varies greatly in difficulty depending on how close is good enough, or equivalently whether there are few lattice points that stick out as much closer than all of the others. Close vector is intuitively harder than short vector, but there is a theoretical result that they are roughly equivalent in difficulty. Taking the strictest possible requirements, finding a close vector is NP-hard. There are intermediate levels of closeness, given by some tolerance that grows with $n$, that seem hard but are probably not NP-hard. Other levels of closeness can be done in polynomial time. There are lots of papers on the these two problems, and the Wikipedia page that Mitch mentions is a pretty good review: The GapCVP section addresses the approximate versions of the question that I mention briefly here.

One weakness of the Wikipedia page is that it has more to say about hardness than practical algorithms. But it does mention two important algorithms: Lenstra-Lenstra-Lovasz and Ajtai-Kumar-Sivakumar.

Answer 2

I don't think you can hope to find a good approximation this way. Consider the special case where $r=0$ and $s=0$. Then, the first problem seems to be equivalent to finding the shortest vector in an integer lattice. The second problem is trivial, the solution being $x=0$. The shortest vector problem is believed to be hard and no good approximation algorithms are known. All known algorithms find approximations that degrade polynomially in the dimension.

See, e.g.,

http://en.wikipedia.org/wiki/Lattice_problem

or one of the many great articles on lattice-based cryptography.