<p>Motivated by the mean-variance optimization, I came up with the following question: Given</p>

<ul>
<li>$n$ integers $a_1, \cdots, a_n$;</li>
<li>$n$ lower bounds $0&lt;\ell_1, \cdots, \ell_n&lt;1$</li>
<li>$n$ upper bounds $0&lt;u_1, \cdots, u_n&lt;1$</li>
</ul>

<p>The problem is to solve</p>

<ul>
<li>minimize $\sum_{i=1}^n a_i^2 x_i- (\sum_{i=1}^n a_i x_i)^2$</li>
<li>subject to $\sum_{i=1}^n x_i=1$ and 
         $\ell_i \leq x_i\leq u_i$ for all $1\leq i\leq n$.</li>
</ul>

<p>For the complexity consideration, let's consider the decision version of the problem. Obviously this is a quadratic programming problem, so it is in NP. However, I do not know whether it is NP-hard. (My conjecture is, yes, it is.)</p>

<p>The intuition is that the (linear) constraints give exponentially many vertices, and it appears that one has to (and only needs to) compare them one by one, hence obstructs a polynomial-time algorithm. But I do not know how to show this formally. Any hints are appreciated. </p>

CC BY-SA 3.0
2015-06-29T23:48:31.997Z
What exactly is the decision version?
François G. Dorais
CC BY-SA 3.0
2015-06-30T08:36:49.633Z
given some threshold $\lambda$, to check whether the minimum is less then $\lambda$.
maomao
<np-hardness><optimization>
NP-hardness of a quadratic programming problem
maomao
# NP-hardness of a quadratic programming problem

(Asked by: username_0 on 2015-06-29)

Motivated by the mean-variance optimization, I came up with the following question: Given

* $n$ integers $a\_1, \cdots, a\_n$;
* $n$ lower bounds $0<\ell\_1, \cdots, \ell\_n<1$
* $n$ upper bounds $0

The problem is to solve

* minimize $\sum\_{i=1}^n a\_i^2 x\_i- (\sum\_{i=1}^n a\_i x\_i)^2$
* subject to $\sum\_{i=1}^n x\_i=1$ and
  $\ell\_i \leq x\_i\leq u\_i$ for all $1\leq i\leq n$.

For the complexity consideration, let's consider the decision version of the problem. Obviously this is a quadratic programming problem, so it is in NP. However, I do not know whether it is NP-hard. (My conjecture is, yes, it is.)

The intuition is that the (linear) constraints give exponentially many vertices, and it appears that one has to (and only needs to) compare them one by one, hence obstructs a polynomial-time algorithm. But I do not know how to show this formally. Any hints are appreciated.

**Tags:** np-hardness, optimization
> **Comments:**
> **username_1**: What exactly is the decision version?  
> **username_0**: given some threshold $\lambda$, to check whether the minimum is less then $\lambda$.  

---

## 0 answers

