[SOLVED] Constraint of cvxpy: How to constrain only some elements of the variable to be nonzero?

Constraint of cvxpy: How to constrain only some elements of the variable to be nonzero?

I have a variable made of 961 elements. And I have a constraint like this: only 8 elements of the variable are nonzero, and the others are 0. I don't know how to express this constraint in cvxpy. I tried this:

import cvxpy as cp
K = cp.Variable(961, integer=Ture)    
s = 0    
constraint = [cp.sum([s+1 for t in K if t!=0])==8]

But I got the following error:

Exception: Cannot evaluate the truth value of a constraint or chain constraints, e.g., 1 >= x >= 0.

Solution

Let's look at this mathematically.

Problem: You have integer variables x[i] ∈ {0,1,2,...,N} and you want to allow only K of them to be nonzero.

We can do this by introducing a parallel binary variable b[i] ∈ {0,1} that indicates whether x[i] is pinned to zero. I use the convention:

  b[i] = 0 => x[i] = 0
  b[i] = 1 => x[i] ∈ {0,1,2,...,N}

This can be written simply as a set of constraints:

  x[i] <= N*b[i]
  sum(i,b[i]) = K

If you want to use the slightly different definition:

  b[i] = 0 => x[i] = 0
  b[i] = 1 => x[i] ∈ {1,2,...,N}

then we need:

  x[i] <= N*b[i]
  x[i] >= b[i]
  sum(i,b[i]) = K

If the integer variables are: x[i] ∈ {-N,...,-2,-1,0,1,2,...,N} then we can do:

  x[i] <= N*b[i]
  x[i] >= -N*b[i]
  sum(i,b[i]) = K

I assume that CVXPY generates the same thing when you say:

  abs(x) <= N*b
  sum(b) == K

(The condition abs(x[i]) >= b[i] is a little bit more messy to linearize in this case).

This should not be too difficult to transcribe into a CVXPY model. Note that we need this explicit upper bound N on x[i]. Make it not too large.