# Bounds on the size of the solution of a quadratic program

I am interested in a quadratic program of the form

$$\min x^T Q x$$ $$s.t.$$ $$Ax \leq b$$ where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $A$ has $2^n$ rows, and $Q$ has $poly(n)$ rows.

Is it true that if there is a minimal solution to the program, then there is one of size that is polynomial in $n$ and $\phi$?

Thanks!

• Do you know anything about $Q$? – Peter Shor Jan 4 '15 at 15:48
• In my case it is not positive semidefinite. What else can help? – Guy Jan 5 '15 at 7:01

In Quadratic Programming is in NP, it is shown that a slight variant of this problem (QPL) is in NP. The question can be formulated as follows: does there exist a point $x \in \mathbb{R}^n$ such that $Ax \leq b$ and $x^T Q x \leq K$, where $K$ is a rational number. In the section 2 of this paper, they prove that, when the minimum exists, then there is a minimum $x^*$ with a polynomial number of digits. Their proof is independent from $K$, so it directly applies to your formulation.

The claim that $x^*$ has a polynomial number of digits is not enough, since you want the solution to be polynomial in $\varphi$ and $n$.

In their proof, they define $x^*$ as a particular global minimum with the maximum number of active inequalities, and then, they construct a nonsingular system of linear equations and show that $x^*$ (or a projection of $x^*$) is its unique solution. Thanks to a theorem by Edmonds they conclude that $x^*$ has a polynomial number of digits.

Since the system has a unique solution, $x^*$ is also the solution to a subsystem consisting of $n$ of the equations. At first sight, the projection of $x^*$ does not seem to be a problem, and all the coefficients of these equations can be kept integer and polynomial in $\varphi$.

So that should reduce your question to the following one:

For systems of linear equations $Cx=d$ (where $C$ is a $n\times n$ integer matrix, and the maximal entry in $C$ and $d$ is $\varphi$) with a unique solution $x^*$, is it true that $x^*$ is polynomial in $n$ and $\varphi$?

EDIT. As pointed out by Kristoffer Arnsfelt Hansen, it is of course useless to consider more than $n$ linear equations.

• If $x$ is the unique solution to $Cx=d$, then obviously $x$ is also the unique solution to a subsystem consisting of $n$ of the equations. – Kristoffer Arnsfelt Hansen Jan 7 '15 at 23:42