How to deal with these constraints in CVX?

MIDCP
1

This question is connected to my previous topic How can I express these constraints in CVX?

The model changed slightly!

The constraints have become too complex for me to put in CVX. The constraints are as follows

  1. x_{t,t''} \ge x_{t,t'} + x_{t',t''} - 1\quad \forall t,t',t'' \ni t\neq t' \,\&\, t' \neq t'' \,\&\, t \neq t''.

  2. x_{t,t} + x_{t',t'} + x_{t,t'}\le 2 \quad\forall t < t'.

Any help!

2

Just write it down using matlab.

for t=1:T
for t1=1:T
for t2=1:T
if (t~=t1)&&(t~=t2)&&(t2~=t1)
x(t,t2) >= x(t,t1) + x(t1,t2) -1;
end
end
end
end

Tha same for the second one.

3

I mean is there any way without using the inner and or outer for loops as proposed in the linked post?

The second one is not same! It is not \forall t \neq t', instead it is \forall t < t'. Of course I can put the condition if (t<tā€™)

4

I meaned the similar logic applies to the second one. If x is binary(then the constraints like" tā€™~=t " can be removed), then maybe the following works for the first constraint:

repmat(x,[1, 1 ,T ]) >= permute(repmat(x,[1 ,1 ,T]) + permute(repmat(x,[1 ,1 ,T]) ,[3 1 2]) , [1 3 2])-1;

Many of those can be vetorized by a home-made string processing program automatically ļ¼ˆsorry, Iā€™m not sure since it seems the ā€œrepmat()ā€ is not overloaded by the CVX developer, but CVX didnā€™t error it. If repmat() can duplicate variables as a convex function itself, that would be good?). I donā€™t know the second one.

5

repmat can be applied to CVX variables and expressions.

1 Like
6

Any suggestions for the second constraint so that I do not need to use the inner if condition!

7

Use the similar logic of the first one. you need to use diag() and maybe a - to minus itself so as to obey the rule t~=tā€™. sorry i donā€™t have my computer around to write it down. i guess it will work(because it is still linear with a minus). happy christmas.
(by the way, i guess if cvx could detect an expression minus itself and set it as 0, that would be more convenient for vectorizing many more kinds of constraints, because convex expression minus itself is not recognized as convex in cvx.)

Note:by moderator: Changed ā€œcanā€ to could, just to make clear to other readers that CVX will not detect an expression minus itself and treat it as 0

8

Try replace the second constraint with the following:

x_temp=repmat(diag(x),[1 T]) + permute(repmat(diag(x),[1 T]), [2 1]) + x ;
x_temp-diag(x_temp) <= 2;

It might work.