Hi everyone!
I am new to CVX for Matlab and hope you can help me with an issue.
I want to solve a semi-definite program min(X * M) , where the constraints have the form Tr(A_i X) = a_i for a certain set of matrices A_i and real values a_i, for i goes from 1 to m. The n times n matrix X is required to be positive semi-definite (and Hermitian).
I decided to formulate the proble in the following way;
I used the {A_i} to form an orthnormal system {B_i} and added other matrices, such that in total we hold an orthonormal basis of the set of all complex valued n times n matrices. So, I can compose X as follows:
X = \sum_{i=1}^{m} B_i b_i + \sum_{i=m+1}^{n^2} D_i d_i .
As the first part of the sum describes those parts of X that are fixed by the constraints, and the B_i’s form an orthonormal system, it remains to optimize over the second sum, requiring that X is PSD.
For the sake of an easier notation, let us call the part that remains unchanged X_0 := \sum_{i=1}^{m} B_i b_i.
The advantage of this formulation is that I only have to optimize over vectors instead of matrices.
Unfortunately, when I do this I obtain a matrix that is not positive semi-definite, although this is the only constraint we have. In fact, the resulting matrix has only 4 positive eigenvalues and many (compared small) negative eigenvalues. Although the negative eigenvalues are quite small, I think it should be possible for the solver to find a matrix that is really positive semi-definite, and not only approximately, shouldn’t it?
That was the “context” of my question; now we come to the “minimal code” required to explain what I am doing:
%Preparation
for k = 1:length(D)
y(k) = trace(D{k} * M);
end%SDP solving
cvx_begin sdpvariables x(length(D)) dual variable Q C = 0; for k = 1:length(D) C = C + x(k) .* D{k}; end C = C + X_0; minimize( real( y' * x) ) C >= 0 : Q;cvx_end
%Calculating X
s=0;
for k = 1:length(D)
s = s + x(k) .* D{k};
endX = X_0 + s;
The eigenvalues that I obtain are mostly negative, as can be seen below.
In some cases the solver gives me a perfectly positive semi-definite matrix, but in many cases it doesn’t.
Is there any way how I can avoid that the solver violates the PSD requirement, or is this just the best that I can obtain within the numerial method?
Thank you very much in advance for your help!
-0.000000516155921
-0.000000516017584
-0.000000515702941
-0.000000515425191
-0.000000450301896
-0.000000450288575
-0.000000450148228
-0.000000450127882
-0.000000398222341
-0.000000398070259
-0.000000398055811
-0.000000397997038
-0.000000353923196
-0.000000353906003
-0.000000353833455
-0.000000353685267
-0.000000317047886
-0.000000316949589
-0.000000316870178
-0.000000316638173
-0.000000284905313
-0.000000284840041
-0.000000284630373
-0.000000284564555
-0.000000250103285
-0.000000250003089
-0.000000249892010
-0.000000249543980
-0.000000210383219
-0.000000210181552
-0.000000209457046
-0.000000208865466
-0.000000173907113
-0.000000173803027
-0.000000173642420
-0.000000173432423
-0.000000126522490
-0.000000126056356
-0.000000125631958
-0.000000125268480
0.009709750768604
0.064618961999724
0.286773403261360
0.638910197995383