# How can I express these constraints in CVX?

I have a variable which I define as

    variable x(T,T) binary
variable y(T,U) binary


\tau(u) is known which is an integer number (strictly positive)
t=1,2,\cdots, T and u=1,2,\cdots, U

There are many constraints in problem that I can write in CVX.

below are the constraints I am not able to express them in CVX.

1. x_{t,t'}=x_{t',t}, \forall t\neq t'
2. x_{t,t}+x_{t',t'}+x_{t,t'}\le 2, \forall t\neq t'
3. y_{t,u}=x_{\tau(u),t}, \forall u, \forall t\neq \tau(u)

Any support is highly appreciated.

Constraint 1 is the same as declaring x to be symmetric (it also trivially holds for t = t' for any matrix, essentially constraining a scalar to equal itself).
variable x(T,T) binary symmetric

Constraints 2 and 3 can be handled by brute force with double for loops, making use of setdiff.

Here is constraint 2:

for t=1:T
for tprime=setdiff(1:T,t)
x(t,t)+x(tprime,tprime)+x(t,tprime) <= 2
end
end


I believe this can at least be partially vectorized, eliminating the inner for loop, as follows (I advise you to check the correctness of this)

 for t=1:T
x(t,t) + diag(x(setdiff(1:T,t),setdiff(1:T,t)))' + x(t,setdiff(1:T,t)) <= 2
end


Constraint 3 should be a reasonably straightforward modification of the double for loop formulation for constraint 2; and I’ll leave it as an exercise for you. Bonus points for you if you can at least partially vectorize it.

Thanks a lot.
As you suggested, I do the following for constraint 3.
Let, tau_all=[tau_1,tau_2,tau_3, … , tau_U]

for u=1:U
for t=setdiff(tau_all,tau_u)
y(t,u)=x(tau_u,t)
end
end


Would you please confirm if I am doing it correctly.

Thanks Again

You need tau_all(u) instead of tau_u. and == instead of =.

I think you could eliminate the inner for loop using
y(setdiff(tau_all,tau_all(u)),u) == x(tau_all(u),setdiff(tau_all,tau_all(u)))'

Eliminating the inner for loop saves a lot of CVX formulation (computer) time as the dimension increases. But the double for loop is just as “correct”. I don’t see how to eliminate the outer for loop for constraints 2 and 3, but if anyone knows how, they are welcome to post their formulation.

For constraint 1,

variable x(T,T) binary symmetric


is not doing the job as you say it also holds for t=t'.

But I have as you have already seen

x_{t,t'}=x_{t',t}, \forall t\neq t'

How can I do this in CVX?

You are requesting something nonsensical.

When t = t’, that (symmetry) constraint amounts to requiring x_{t,t} = x_{t,t}. How can that not hold? it is just saying that a variable must equal itself, which of course always holds.

So declaring the variable symmetric implements constraint 1 by any mathematically meaningful interpretation. it does not add any constraint beyond what is stated in 1. I.e., it implements constraint 1, and only constraint 1; no more, no less.

The first two are in this link How to deal with these constraints in CVX?.
The last one is the following:

t=1:T;
a=1:T;
u=1:U;
t=t';
a=a';
u=u';
fir_cons=(repmat(a,1,U)==tau(repmat(u',T,1)));%au
sec_cons=(repmat(a,1,T)~=repmat(t',T,1));%at
sum_cons=repmat(fir_cons,[1,1,T]).*permute(repmat(sec_cons,[1,1,U]),[1 3 2]);%aut
permute(sum_cons,[3 2 1]).*(repmat( y , 1, 1, T ) - permute( repmat( x , 1, 1, U ), [ 2 3 1 ]))==0;


By the way, if conditions like ‘t~=tau(u)’ are removed and there just exists several layers of loops, I think most constraints(if not all) can be vectorized much easier.