Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks!

share|improve this question
1  
What do you mean by "destroys the linearity"? –  anon Jul 13 '11 at 18:01
    
I mean there's no way to represent it as a linear program any more. –  npforce Jul 13 '11 at 18:28

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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