<p>In <a href="http://ecommons.library.cornell.edu/bitstream/1813/6939/1/90-1099.pdf" rel="nofollow">Quadratic Programming is in NP</a>, 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.</p>

<p>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$. </p>

<p>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.</p>

<p>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$.</p>

<p>So that should reduce your question to the following one:</p>

<p>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$?</p>

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

CC BY-SA 3.0
2015-01-07T23:42:25.193Z
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
CC BY-SA 3.0
2015-01-07T16:55:33.380Z
2015-01-08T08:37:00.160Z
2015-01-08T08:37:00.160Z
Nicolas Perrin
<p>I am interested in a quadratic program of the form</p>

<p>$$ \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. </p>

<p>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$?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2015-01-04T15:48:14.963Z
Do you know anything about $Q$?
Peter Shor 
CC BY-SA 3.0
2015-01-05T07:01:32.607Z
In my case it is *not* positive semidefinite. What else can help?
Guy
<np><convex-optimization><quadratic>
Bounds on the size of the solution of a quadratic program
Guy
# Bounds on the size of the solution of a quadratic program

(Asked by: username_0 on 2015-01-04)

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!

**Tags:** np, convex-optimization, quadratic

> **Comments:**
> **username_1**: Do you know anything about $Q$?  
> **username_0**: In my case it is *not* positive semidefinite. What else can help?  

---

## 1 answers

### Answer by username_2 on 2015-01-07. Score: 6

In [Quadratic Programming is in NP](http://ecommons.library.cornell.edu/bitstream/1813/6939/1/90-1099.pdf), 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 username_3, it is of course useless to consider more than $n$ linear equations.

> **Comments:**
> **username_3**: 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.  

---

