How to express this constraint in CVX?

MIDCP
1

A matrix \bf A of size N\times N is also given. \bf A is a binary matrix.

The optimization variable is \bf U (of size M\times N). It is a binary integer variable.

The constraint I have is

{\bf uAu'}=0,\hspace{1mm}\forall u

where \bf u is a row vector of \bf U

How can I write this constraint in CVX DCP format?

2

I don’t understand what
{\bf tAt'}=0,\hspace{1mm}\forall t
means.

t is a CVX variable. Any candidate (primal feasible) solution will have one specific value of t . And of course the t which is the CVX variable is a scalar, not a vector.

Your constraint
sum(T.*repmat(c,M,1))>=t.*d;
constrains what values t can have, and it must holf for any candidate (primal feasible) solution. And that makes sense.

Is the t in
{\bf tAt'}=0,\hspace{1mm}\forall t
a different t than the CVX variable which is the objective function?

3

Sorry, I used wrong identifier. T should be written as U, and the constraint tAt' should be replaced with uAu'.

4

If we didn’t worry about DCP compliance, the constraints could be written

for i=1:m:
  U(i,:)*A*U(i,:)' == 0
end

However, those constraints are all non-convex as written. Because U is binary, U(i,:)*A*U(i,:)' can be linearized. To do so, you can do the following, which should work, but I’m not sure is the best or fastest way of doing this.

Introduce another binary variable for every product term U(i,j)*(U(k,l). Call that B(i,j,k,l). Substitute B(i,j,k,l).for each instance of U(i,j)*U(k,l). Then add the constraints

B(i,j,k,l) <= U(i,j)
B(i,j,k,l) <= U(k,l)
B(i,j,k,l) >= U(i,j) + U(k,l) - 1

I think you really only need (M*N)*(M*N -1)/2 of these variables due to symmetry and that square terms (i.e., of the form U*i,j)*U(i,j) ) can be replaced by the non-squared variable without adding variables or constraints.

Anyhow, it might get a bit messy, but I leave you to deal with the mess and to determine any efficient vectorized ways of implementing this. Converting from a Binary QP to a MILP is a standard thing, so that’s basically what you have to do (pretend the left hand side of the quadratic equality constraint is the objective function). Keep in mind though that your optimization variable is a matrix, not a vector.

Edit: I leave you to determine whether there is a better way of dealing with the requirement stated at the end of the edited version of your most recent post. I wouldn’t be surprised if there were a much nicer way, requiring many fewer variables and constraints.

5

It will be a mess as I have a very large system, for example, N is around 100 and M is around 300.

I was thinking of an alternative formulation of the last constraint.
Let \rm ind gives the position of ones in the vector \bf u, then we can formulate the last constraint as

\rm for\hspace{1mm} i=1:m
\rm ind=find(U(i,:)==1)
\sum {\bf U(i,:)A}(\rm ind,:)==0
\rm end

Is it possible to express this as a constraint?

Or, do you have any other suggestion?

6

I think you could do that by introducing enough binary variables. i;m not the expert in the best way of using binary variables to handle this kind of problem.

One thing you can do is to start with a small scale problem, ideally M and N in the single digits. Try out one or more approaches on that. Then if you see what works and scales to larger problems, move up toward the problem you really want to solve. It may be that no matter what you do, you can not solve the problem you want before the sun dies.