Is this possible for Assignment: Trace(M1_n*X) == Trace(M2_n*X)?


(PLTB) #1

I have a variable that is Matrix X positive semi-definite with size 2Nx2N. and 2N matrices that are M1_1,M1_2,…,M1_N and M2_1, M2_2,…,M2_N. Is this possible to write a loop like this:
for n=1:N
trace(M1_n
X)==trace(M2_n*X);
end
Because everytime i added this contraints to cvx, my problem does not work:
`Calling SDPT3 4.0: 8861 variables, 3240 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 3240
dim. of sdp var = 80, num. of sdp blk = 1
dim. of linear var = 5601
dim. of free var = 20 *** convert ublk to lblk


SDPT3: Infeasible path-following algorithms


version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|1.6e+05|7.4e+01|1.6e+26| 1.155527e+24 0.000000e+00| 0:0:07| spchol 1 2
1|0.024|0.000|4.7e+13|7.4e+01|2.2e+26| 1.155396e+23 -5.734178e+10| 0:0:15|
sqlp stop: primal or dual is diverging, 3.9e+15

number of iterations = 1
Total CPU time (secs) = 14.62
CPU time per iteration = 14.62
termination code = 3
DIMACS: 2.2e+14 0.0e+00 2.9e+03 0.0e+00 1.0e+00 1.9e+03


Status: Failed
Optimal value (cvx_optval): NaN`
Another point: when i change to: Trace(M1_nX) <= Trace(M2_nX). It works but that is not i want.
Thank you!


(Mark L. Stone) #2

Do you actually have variables literally named M1_n and M2_n? I’m not talking about having variables named M1_1 , M1_2, etc. If not, I think your for loop

for n=1:N
trace(M1_n*X)==trace(M2_n*X);
end 

would generate an error message, and therefore be “ignored” by CVX, i.e., it would never be part of the CVX model you create. And if you do have variables literally named M1_n and M2_n, you have specified the constraint trace(M1_n*X)==trace(M2_n*X) N times, which is equivalent to specifying it once. And then it’s a matter of whether the solver can successfully solve the problem, or whether it encounters numerical difficulties or an error condition.

Have you tried using sedumi, or if you have CVX Professional and MOSEK, using MOSEK?

Perhaps you should put M1_1, … M1_N all into one 3 dimensional array, M1 with 3rd dimension of length N. And similarly for M2_1, …, M2_N. See mcg’s answer in How to change the number of variables based on the iteration number? .


(PLTB) #3

Hi,
Thank you for you explanation. Actually i did not use M1_1 M1_2 … in the coding program. I built a matrix named M1 to store N matrices: M1_1, M1_2 … and M2 to store N matrices M2_1, M2_2 … . Below is my code in the link:
https://drive.google.com/drive/folders/0B4c0HPM_merbcUpobkIxdDVTZDg?usp=sharing
Problem is without trace==trace conditions, my problem run well without error. But when i added [quote=“mossy.fighting, post:1, topic:4213”]
for n=1:Ntrace(M1_nX)==trace(M2_nX);end
[/quote]
the program fail for SDPT3 and Sedumi (after one loop it failed). So i do not know whether trace==trace is allowed in CVX? And the paper i followed (in the link) Section III.C written that formula trace==trace and they successfully run.
Thank you!


(Mark L. Stone) #4

Your trace == trace constraints are being accepted by CVX, and are allowed. The solvers you have tried are having difficulty (failing) solving the problem. I don’t know whether MOSEK might succeed. Perhaps your optimization problem (with all the constraints) is ill-specified/numerically “nasty”. One other solver you could try is SCS under CVX 3.0 beta - it is a first order solver, so it might be slow, but slow is better than not at all - however, I am not suggesting SCS will succeed.

Have you tried different input data? Data in examples from the paper? Have you checked to see how well scaled the problem data is?


(Michael C. Grant) #5

It is almost certain that the issues are with the numeric ranges of M1 and M2 and/or other quantities in your problem. Look at those initial prim-obj and dual-obj values. You’ll need to rescale your model so the coefficients are in ranges just a few orders of magnitude away from 1.


(PLTB) #6

Thank you for your kind suggestion!

For my test, it does not succeed for MOSEK.

I used the parameters (2 files: Mask.cosinetheta.SUM and Mask.cosinetheta.FLATTOP) from the paper. And this does not even run for each iteration step by step, just notify the status FAIL.
And the interesting fact that, the paper says this optimization run successfully less than 30 seconds. But for me without trace == trace, it takes 15 minutes for each loop cvx_begin and cvx_end.
Last thing: i do not understand that point:

In general, which parameters should i scale to check.
Thanks!


(Mark L. Stone) #7

See mcg’s post above.