Hi,

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

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

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

Thanks!

Hi,

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

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

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

Thanks!

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.

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?

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.

1 Like

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

- sum_log()

or - add log() in a for loop

or - 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)

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

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.

Original size: 1094 variables, 36 equality constraints

1 exponentials add 8 variables, 5 equality constraints

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

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.

Thank you. It is working.

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?

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.

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.

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

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

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ā)

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

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.

1 Like