Question on SDR modeling

[Kali (Kali Krishna)]

Hi,

Is it still valid to model the problem as follows and solve it using SDR?

max \sum_{k=K}^K log(1 + trace(XA_k))
s.t. trace(XA_j) >= c_j; \forall j = 1:M

If the SDR method is inaccurate? Can you please suggest an alternative?

Thanks!

[Mark_L_Stone]

Unless you have a specific theoretical result for your problem saying otherwise, unless the original constraints are satisfied by the solution to the relaxation (for instance, the solution of the relaxed problem is rank one for this case in which the relaxation consists of omitting the rank one constraint), you don’t know anything other than that the optimal objective value of the relaxed problem is an upper bound (for maximi9zation) to the optimal objective value of the original problem; and you don’t know by how much.

[Kali (Kali Krishna)]

Attached is an abstraction of my problem. The objectives are the same, and the constraints also remain to be the same. So, would this be a valid way to solve the original problem? If not, instead of picking the dominant eigenvector, can I implement Gaussian randomization, as it is guaranteed to converge very close to the actual solution?

[Mark_L_Stone]

At this point, you’re kind of going out of the scope of his forum. So you shouldn’t count on getting help here with these kinds of questions. Nevertheless, anyone should feel free to provide whatever assistance they want.

[Kali (Kali Krishna)]

Hi,

I’ve gone through the following post: CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions

My question is do I have to replace the objective I mentioned in the post with

1. sum_log()
   or
2. add log() in a for loop
   or
3. add -rel_entr(1,x) in a for loop

Also, the above post mentions, Pade Approximant is better than Successive Approximation method, and this is particularly the case when there are logs in the optimization problem.

Can you please suggest the best practice to model the objective functions mentioned in the question that I posted above, because sometime successive approximation fails to solve the problem.
For example: see the below log (sorry if this is not giving a lot of info)

Successive approximation method to be employed.
SDPT3 will be called several times to refine the solution.
Original size: 1093 variables, 36 equality constraints
1 exponentials add 8 variables, 5 equality constraints

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
1/ 1 | 8.000e+00 4.621e+01 0.000e+00 | Solved
1/ 1 | 8.000e+00s 8.848e+00 0.000e+00 | Solved
1/ 1 | 1.631e+00 1.606e-01 0.000e+00 | Solved
1/ 1 | 2.304e+00s 3.252e-01s 0.000e+00 | Failed
1/ 1 | 2.133e+00s 2.135e-01 0.000e+00 | Failed
1/ 1 | 4.592e+00s 1.416e+00s 0.000e+00 | Failed
1/ 1 | 5.523e+00s 1.682e+00s 0.000e+00 | Solved
1/ 1 | 8.196e-01 4.269e-02 0.000e+00 | Solved
1/ 1 | 3.752e+00s 9.306e-01s 0.000e+00 | Failed

Status: Failed
Optimal value (cvx_optval): NaN

I’ve used the epigraph technique to model the problem, and with the same data I see the following log:
Successive approximation method to be employed.

SDPT3 will be called several times to refine the solution.
Original size: 1094 variables, 36 equality constraints
1 exponentials add 8 variables, 5 equality constraints

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
1/ 1 | 8.000e+00 4.621e+01 0.000e+00 | Solved
1/ 1 | 8.000e+00s 4.673e+00 0.000e+00 | Failed
1/ 1 | 2.380e+00 3.564e-01 0.000e+00 | Failed
1/ 1 | 4.504e+00s 1.145e+00s 0.000e+00 | Solved
1/ 1 | 5.627e-01 2.002e-02 0.000e+00 | Solved
1/ 1 | 4.019e+00s 1.057e+00s 0.000e+00 | Failed
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Failed
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Failed
1/ 1 | 4.559e+00 1.172e+00 0.000e+00 | Solved
1/ 1 | 5.756e-01 2.095e-02 0.000e+00 | Solved
1/ 1 | 1.047e-02 6.856e-06 0.000e+00 | Solved
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Solved

Status: Solved
Optimal value (cvx_optval): +17.5511

So, to summarize, I have different solver log for the same problem with the same data, but with different modeling.

Can you please suggest the best practice? or redirect me to some documentation which will help me understand better.

Thanks in advance!

Kali

[Mark_L_Stone]

Use Mosek if available.

Otherwise, install CVXQUAD and its exponential.m replacement ,and change log(cvx_expression) to -rel_entr(1,cvx_expression). There is no need to change to -rel_entr(1,cvx_expression). if you are using Mosek.

[Kali (Kali Krishna)]

Thank you. It is working.

[Kali (Kali Krishna)]

I’ve changed the objective as
\sum_{k=1}^K log( 1 + 2 real{a_k^H f} - (f^H A_k f) )

s.t. ||f|| = 1, |f_i| <= 2; \forall i = 1:M

The objective is convex in f, and because I have logs in the expression, I’ve changed it to sum(-rel_entr(1,1 + 2 real{a_k^H f} - (f^H A_k f))), and using the Pade’s approximation to solve the problem.

However, following is the error:

=====================================
Using Pade approximation for exponential
cone with parameters m=3, k=3

Error using cvxprob/newcnstr (line 192)
Disciplined convex programming error:
Invalid constraint: {concave} == {real affine}

Error in cvxprob/newcnstr (line 72)
newcnstr( prob, x{k}, y{k}, op );

Error in == (line 3)
b = newcnstr( evalin( ‘caller’, ‘cvx_problem’, ‘’ ), x, y, ‘==’ );

Error in cvx/rel_entr (line 80)
{ -q, xt, yt } == exponential( sz ); %#ok

I’m using Pade’s approximation because, Mosek throws an error that the problem is ill posed, and in these cases SCA solves the problem. However, it feels like something is wrong, so I want to check with Pade’s approximation as well.

Could you please help?

[Mark_L_Stone]

Please show reproducible CVX code, not a math description of your problem.

And make sure you are using CVX 2.2, not CVX 3.0beta, which is riddled with bugs which will never be fixed.

And of course, you’ve already made sure the problem you provide to CVX is a convex optimization problem.

The 2nd argument of rel_entr does look concave, as CVX requires, presuming A_k is psd and f is affine.

If you used an explicit { -q, xt, yt } == exponential( sz ); constraint, all of the arguments on the LHS must be affine.

[Mark_L_Stone]

If Mosek is reporting the problem is ill-posed, perhaps something about the problem formulation and/or input data is not good. “Shopping” for another solver which doesn’t report that is not necessarily the best way of addressing that. Maybe you should try to figure out what it is concerning the model and input data which causes Mosek to report that.

Or maybe SDR is not a good approach for your problem.

[Kali (Kali Krishna)]

I’m not using SDR. How can I share the working code and data that I’m using for my code?

[Mark_L_Stone]

You can post reproducible code to this forum, with data set explicitly in the code.

[Kali (Kali Krishna)]

I’ve appended the following lines, and Mosek is able to solve the problem:
cvx_solver mosek;
% Set MOSEK parameters using generic names
cvx_solver_settings(‘MSK_DPAR_OPTIMIZER_MAX_TIME’, 100.0, …
‘MSK_IPAR_INTPNT_SOLVE_FORM’, ‘MSK_SOLVE_DUAL’);
% Shows how to save the MOSEK task file
cvx_solver_settings(‘write’, ‘dump.task.gz’)

[Kali (Kali Krishna)]

Hi, I’m unable to post the reproducible code because it is exceeding the word count.

[Mark_L_Stone]

Perhaps you can spread it across posts. And use Pre-formatted text icon. And try copying and pasting everything into a new MATLAB session to make sure it runs.