Semidefinite Optimization with Linear Constraint


#1

Hi, I am trying to solve a problem of following format
min [ct]{x}
s.t. [A1]{x}={b1}; (Linear Equality Constraint)
[A2]{x}<={b2}; (Linear Inequality Constraint)
[F0] +[F1]* x1+[F2]*x2…+[Fn]*xn >= [0] (SDF constraint)
where {x}={x1 x2 x3…xn}

How to solve this kind of problem ? Can anyone help me with some example ?


(Mark L. Stone) #2

Please read the CVX Users’ Guide http://cvxr.com/cvx/doc/ . Presuming all your terms really are linear (which they will be if all the A’s, F’s, and cf are constants (not a function of optimization (CVX) variables), this problem should be very straightforward to implement in CVX. If after reading the CVX Users’ Guide, you need help with something, then please indicate more specifically where you need help.


#3

I solved the following problem. Can you check the code whether is it proper way or not? I got result but I am new in CVX thats why I am not confident.
% min X22
% s.t . X11 + X12 = 1,
% 1.5 * X22 + X12 >= 2,
% - X + (5 - 0.3 * y) * I >= 0
% X + y * I >=0
% where X= [X11 X12; X12 X22] and I =[1 0;0 1]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cvx_begin sdp
variable X(2,2) symmetric;
variable y;
minimize(X(2,2));
subject to
X(1,1)+X(1,2)==1;
1.5 * X(2,2)+X(1,2)>=2;
-X+(5-0.3 * y) * eye(2) == semidefinite(2);
X+y * eye(2) == semidefinite(2);
cvx_end


(Mark L. Stone) #4

Yes, your CVX program implements the model provided in your comment lines and appears to be correct.

However, with the CVX program as you have entered, you don’t need SDP mode, i.e,. you don’t need the sdp in cvx_begin sdp. Alternatively, if you do use cvx_begin sdp, you could change your semidefiniite constraints to

-X+(5-0.3 * y) * eye(2) >= 0;
X+y * eye(2) >= 0;

But again, let me make clear that your program as provided appears to be correct.

Note that in SDP mode, your constraint 1.5 * X(2,2)+X(1,2)>=2 is interpreted, as desired, as an element-wise constraint, because it is one-dimensional. You might want to re-read http://cvxr.com/cvx/doc/sdp.html to make sure you understand everything.


#5

Thanks.
I understood the point.
The main problem which I have to deal is

    min sum tr(C_i * X_i)

s.t.
tr(A1_i * X_i)=b1_i; (Linear Equality Constraint)
tr(A2_i * X_i)<=b2_i; (Linear Inequality Constraint)
- X_i + (5 - 0.3*y_i)*I >= 0 (SDF constraint)
X_i + y_i * I >=0 (SDF constraint)
where X_i= [X11_i X12_i; X12_i X22_i] and I =[1 0;0 1]
for i = 1,2…,n ; n is very large.

Please help with some hint.


(Mark L. Stone) #6

You can use for loops to define constraints and if necessary, build up objective functions. You can also declare 3-D CVX variables, e.g., cvx variable X(2,2,n) symmetric . Then you can use such things as X(:,:,i) … See for instance mcg’s answer in Cvx sdp mode and cell arrays .

And of course, trace is supported by CVX.

.


#7

Thanks for the above advice.
I have solved a similar problem as follows :

n=2;
c=[0 1 0 0 1 0];
A1=[0 2 1 1 0 3
1 0 1 0 2 3];
b1=[1;1];
A2=[0 2 1 0 2 1
0 2 1 0 2 1];
b2=[0;0];
cvx_begin
variable X(3*n,1);
variable y(n);
minimize(c * X);
subject to
A1 * X==b1;
A2 * X<=b2;
for i=1:n
-X(3 * i - 2,1) * [1 0;0 0] - X(3 * i - 1,1) * [0 0;0 1] - X(3 * i,1) * [0 1;1 0] + (5 - 0.3 * y(i)) * eye(2) == semidefinite(2);
X(3 * i-2,1) * [1 0;0 0] + X(3 * i - 1,1) * [0 0;0 1]+X(3 * i,1) * [0 1;1 0]+y(i) * eye(2) == semidefinite(2);
end
cvx_end

To solve for a large n (say 10^5) , it really needs a very long time. Is there any way to solve it in a faster way.?


(Mark L. Stone) #8

Total time to solve is divided between CVX processing time and solver time. n = 10^5 has 200,000 semidefinite constraints, which sounds kind of big, so I suppose you can expect things to take a while.

I will defer to others to determine whether any vectorization and/or aggregation (in a nice way) of constraints into one or two large semidefinite constraints is possible and would speed things up, at least on the CVX side.