I have a linear program where the variables are n vectors. Now I'd like to impose an extra constraint that k (k<=n) of the n vectors are linearly independent, or the matrix with the n vectors as rows has rank k. It seems to me that this constraint destroys the linearity. Is there any existing theory dealing with this kind of problem?


  • 1
    $\begingroup$ What do you mean by "destroys the linearity"? $\endgroup$ – anon Jul 13 '11 at 18:01
  • $\begingroup$ I mean there's no way to represent it as a linear program any more. $\endgroup$ – npforce Jul 13 '11 at 18:28

Let $k = 1$. Then all your vectors are multiples of the same vector. Number them $v_0,\ldots,v_n$. Add the constraints $v_{00} = 1$ and $v_{i0} = v_{0i}$. The rank constraint implies that $v_{ij}/v_{i0} = v_{0j}/v_{00}$ and so $v_{ij} = v_{i0} v_{0j} = v_{i0} v_{j0}$. Put $x_i = v_{i0}$, so that . We thus have a quadratically constrained quadratic program, which is NP-hard to optimize. The reason is that we can simulate zero/one integer programming by adding the constraint $x_i^2 = x_i$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.