3
$\begingroup$

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<u_1, \cdots, u_n<1$

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.

$\endgroup$
  • $\begingroup$ What exactly is the decision version? $\endgroup$ – François G. Dorais Jun 29 '15 at 23:48
  • $\begingroup$ given some threshold $\lambda$, to check whether the minimum is less then $\lambda$. $\endgroup$ – maomao Jun 30 '15 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.