SDP, Infeasible

1

Hi,
I hope everyone is doing well.
I am trying to solve an SDP by using CVX. Unfortunately, it constantly gives me infeasible solutions!
In the below, I provide comprehensive details of my problem including CVX code and constant values.

Besides, it is absolutely guaranteed to be convex. I was wondering if it has to do with the solver (i.e., SDPT3 4.0)? or the dimension of the problem? I really appreciate it if somebody could give me a hint regarding this problem.

                cvx_begin SDP

% cvx_precision low

                variable W(M,M,K) hermitian semidefinite
                variable W_E(M,M,1) hermitian semidefinite
                variable rho(K)   nonnegative
                variable t
                C0=cvx(zeros(1));
                for m=1:K
                    C0=C0+real(trace(W(:,:,m)));
                end

                maximize(t)

                subject to
                C1=cvx(zeros(K,1));

                for m=1:K
                    for n=1:K
                        old=real(trace(H(:,:,m)*W(:,:,n)));
                        C1(m)=old+C1(m);
                    end 

                    (log(C1(m)+sigma_1+(sigma_2)*(inv_pos(rho_int(m))-inv_pos(rho_int(m).^2)* (rho(m)-rho_int(m)))))/log(2)-real(g_new(m))-real(trace(derivative1(:,:,m)'*(W(:,:,m)-W_int(:,:,m))))-real(derivative2(m).'*(rho(m)-rho_int(m)))>=real(lamda*(real(trace(W(:,:,m)))+real(trace(W_E(:,:,1)))+p_cir)+t);
                    
                    sigma_1+(sigma_2)*inv_pos(rho(m))<=real(((1/gamma)+1)*(real(trace(H(:,:,m)*W(:,:,m))))-(C1(m)));

                    C1(m)+real(trace(H(:,:,m)*W_E(:,:,1)))>=e_m*inv_pos(eta*(1-rho(m)));

                    C0+real(trace(W_E(:,:,1)))<=p_max;

                    0<rho(m)<1;
                end
                cvx_end

%%%%%%%%%%%%%%%%%

Values:

p_max=10;
e_m =1.0000e-04;

H(:,:,1) =

1.0e-06 *

0.2136 + 0.0000i 0.2000 + 0.0697i 0.2678 + 0.0851i 0.2756 + 0.0079i 0.1923 + 0.0096i
0.2000 - 0.0697i 0.2100 + 0.0000i 0.2785 - 0.0077i 0.2606 - 0.0826i 0.1832 - 0.0538i
0.2678 - 0.0851i 0.2785 + 0.0077i 0.3698 + 0.0000i 0.3488 - 0.0999i 0.2450 - 0.0646i
0.2756 - 0.0079i 0.2606 + 0.0826i 0.3488 + 0.0999i 0.3560 - 0.0000i 0.2486 + 0.0053i
0.1923 - 0.0096i 0.1832 + 0.0538i 0.2450 + 0.0646i 0.2486 - 0.0053i 0.1737 + 0.0000i

H(:,:,2) =

1.0e-05 *

0.1285 - 0.0000i 0.1309 - 0.0053i 0.1275 - 0.0079i 0.1241 - 0.0053i 0.1305 - 0.0041i
0.1309 + 0.0053i 0.1336 + 0.0000i 0.1302 - 0.0028i 0.1266 - 0.0002i 0.1331 + 0.0012i
0.1275 + 0.0079i 0.1302 + 0.0028i 0.1270 + 0.0000i 0.1234 + 0.0024i 0.1297 + 0.0040i
0.1241 + 0.0053i 0.1266 + 0.0002i 0.1234 - 0.0024i 0.1200 + 0.0000i 0.1262 + 0.0014i
0.1305 + 0.0041i 0.1331 - 0.0012i 0.1297 - 0.0040i 0.1262 - 0.0014i 0.1326 + 0.0000i

H(:,:,3) =

1.0e-06 *

0.7061 + 0.0000i 0.7558 - 0.2411i 0.5608 - 0.1586i 0.5493 + 0.0182i 0.7382 - 0.0480i
0.7558 + 0.2411i 0.8915 + 0.0000i 0.6545 + 0.0218i 0.5818 + 0.2070i 0.8066 + 0.2007i
0.5608 + 0.1586i 0.6545 - 0.0218i 0.4811 - 0.0000i 0.4322 + 0.1378i 0.5971 + 0.1277i
0.5493 - 0.0182i 0.5818 - 0.2070i 0.4322 - 0.1378i 0.4278 - 0.0000i 0.5730 - 0.0563i
0.7382 + 0.0480i 0.8066 - 0.2007i 0.5971 - 0.1277i 0.5730 + 0.0563i 0.7751 - 0.0000i

H(:,:,4) =

1.0e-07 *

0.2512 - 0.0000i 0.3100 - 0.2699i 0.0981 - 0.2902i 0.0892 - 0.1249i 0.3247 - 0.1531i
0.3100 + 0.2699i 0.6726 - 0.0000i 0.4330 - 0.2528i 0.2443 - 0.0584i 0.5653 + 0.1600i
0.0981 + 0.2902i 0.4330 + 0.2528i 0.3737 - 0.0000i 0.1792 + 0.0542i 0.3038 + 0.3155i
0.0892 + 0.1249i 0.2443 + 0.0584i 0.1792 - 0.0542i 0.0938 - 0.0000i 0.1915 + 0.1072i
0.3247 + 0.1531i 0.5653 - 0.1600i 0.3038 - 0.3155i 0.1915 - 0.1072i 0.5132 + 0.0000i

%%%%%%%%%%%%%%%%%%%%%%

Result:

CVX Warning:
Models involving “log” or other functions in the log, exp, and entropy
family are solved using an experimental successive approximation method.
This method is slower and less reliable than the method CVX employs for
other models. Please see the section of the user’s guide entitled
The successive approximation method
for more details about the approach, and for instructions on how to
suppress this warning message in the future.

Successive approximation method to be employed.
SDPT3 will be called several times to refine the solution.
Original size: 186 variables, 48 equality constraints
4 exponentials add 32 variables, 20 equality constraints

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Infeasible

Status: Infeasible
Optimal value (cvx_optval): -Inf

2

Either use CVX 2.2, with Mosek as solver (preferable), or if that is not possible, install CVXQUAD and its exponential.m replacement, and follow the directions at 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 .

The scaling of H is very bad, and may make the solution unreliable.Try to improve scaling so that most non-zero input numbers are within a few orders of magntiude of 1. If not using Mosek, you can also try SeDuMi as solver.

After you have done all of the preceding, if the problem is still reported as infeasible, follow the advice at https://yalmip.github.io/debugginginfeasible/ , all of which also applies to CVX, except for section 1.

3

Thank you, Mr. Stone, for your prompt and valuable reply

I am afraid I could not manipulate the scaling of matrix ‘H’.

I suppose Mosek would handle it (not sure).

I got an Academic License of Mosek by filling an application form last five months ago. Now, I decided to request a new Personal Academic License file again. It was mentioned that it is valid until 2021-aug-31. However, I was not able to install it!

The below message, during installing cvx setups, appears in my command window:

2 solvers initialized (* = default):

  • SDPT3 4.0 {cvx}\sdpt3
    SeDuMi 1.3.4 {cvx}\sedumi
    4 solvers skipped:
    GLPK
    Could not find a GLPK installation.
    Gurobi unknown {cvx}\gurobi\w64
    No valid Gurobi license was found.
    Gurobi_2 unknown C:\gurobi902\win64\matlab
    No valid Gurobi license was found.
    Mosek 9.1.9 {cvx}\mosek\w64
    Error code 1001 (MSK_RES_ERR_LICENSE_EXPIRED).
4

You can request help for Mosek installation and license issues at https://groups.google.com/forum/#!forum/mosek .

As for scaling, have you figured out what you would have to change in your program and other input data if you multiplied all elements of H by 1e6?

5

You probably have the license file in the wrong place and some older license is being picked up. Or you should restart Matlab. In any case running mosekdiag in Matlab will show you a path where your Mosek installation is expecting the license.

6

Hi sir,

Thanks for your help. I am sorry I do not get your point!
Is it a file or command? However, I copy and past it in my command window, it states 'Undefined function or variable ‘mosekdiag’.

7

If you just have the Mosek that comes bundled with CVX then possibly you don’t have mosekdiag. Sorry for confusing you. The instructions for where to keep the Mosek license file by default are in https://docs.mosek.com/9.2/licensing/quickstart.html#local, Section 4.3.

8

Hi, Mr. Stone,

I change the magnitude of each element in H as follows

H(:,:,1) =

1.0e-03 *

0.4574 + 0.0000i 0.4458 - 0.0511i 0.4882 - 0.0428i 0.4609 - 0.0652i 0.4352 - 0.0402i
0.4458 + 0.0511i 0.4401 - 0.0000i 0.4806 + 0.0128i 0.4565 - 0.0120i 0.4287 + 0.0095i
0.4882 + 0.0428i 0.4806 - 0.0128i 0.5251 - 0.0000i 0.4981 - 0.0264i 0.4683 - 0.0021i
0.4609 + 0.0652i 0.4565 + 0.0120i 0.4981 + 0.0264i 0.4737 - 0.0000i 0.4443 + 0.0215i
0.4352 + 0.0402i 0.4287 - 0.0095i 0.4683 + 0.0021i 0.4443 - 0.0215i 0.4177 - 0.0000i

H(:,:,2) =

0.0043 + 0.0000i 0.0043 - 0.0002i 0.0044 + 0.0001i 0.0044 - 0.0001i 0.0041 - 0.0001i
0.0043 + 0.0002i 0.0044 + 0.0000i 0.0044 + 0.0002i 0.0045 + 0.0000i 0.0042 + 0.0001i
0.0044 - 0.0001i 0.0044 - 0.0002i 0.0045 - 0.0000i 0.0045 - 0.0002i 0.0042 - 0.0001i
0.0044 + 0.0001i 0.0045 - 0.0000i 0.0045 + 0.0002i 0.0045 - 0.0000i 0.0042 + 0.0001i
0.0041 + 0.0001i 0.0042 - 0.0001i 0.0042 + 0.0001i 0.0042 - 0.0001i 0.0040 + 0.0000i

H(:,:,3) =

0.0032 - 0.0000i 0.0034 - 0.0000i 0.0035 + 0.0002i 0.0036 + 0.0000i 0.0037 - 0.0001i
0.0034 + 0.0000i 0.0036 + 0.0000i 0.0036 + 0.0002i 0.0037 + 0.0001i 0.0038 - 0.0001i
0.0035 - 0.0002i 0.0036 - 0.0002i 0.0038 - 0.0000i 0.0038 - 0.0001i 0.0039 - 0.0003i
0.0036 - 0.0000i 0.0037 - 0.0001i 0.0038 + 0.0001i 0.0039 - 0.0000i 0.0040 - 0.0002i
0.0037 + 0.0001i 0.0038 + 0.0001i 0.0039 + 0.0003i 0.0040 + 0.0002i 0.0041 + 0.0000i

H(:,:,4) =

0.0012 + 0.0000i 0.0012 + 0.0000i 0.0013 + 0.0000i 0.0013 + 0.0000i 0.0013 - 0.0000i
0.0012 - 0.0000i 0.0013 + 0.0000i 0.0013 + 0.0000i 0.0013 - 0.0000i 0.0013 - 0.0000i
0.0013 - 0.0000i 0.0013 - 0.0000i 0.0013 + 0.0000i 0.0013 - 0.0000i 0.0014 - 0.0000i
0.0013 - 0.0000i 0.0013 + 0.0000i 0.0013 + 0.0000i 0.0014 - 0.0000i 0.0014 - 0.0000i
0.0013 + 0.0000i 0.0013 + 0.0000i 0.0014 + 0.0000i 0.0014 + 0.0000i 0.0014 + 0.0000i

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

I managed to solve the problem, it does not provide an optimal answer according to my mathematical calculations! But, it works. Thank you so much, Mr. Stone, for your kind responses.

9

No worry at all.

As I know, the license file needs to be placed inside a folder named “mosek” under the user’s home directory as follows:

c:\users_userid_\mosek\mosek.lic

Previously, I replaced the new license file with the old one and reinstalled the CVX in my Matlab. Still, it can not determine the validity of the license file! So interesting :slight_smile:

Anyway, thank you so much, Mr. Adamaszek, for your consideration.

10

You are supposed to make offsetting changes to other data when you multiply H. Otherwise, you will be solving a different, non-equivalent problem to your original problem, and will not get the solution to your original problem. You should try to make changes which would result in an exactly equivalent problem if the problem were solved exactly (in exact arithmetic). The purpose of making the scaling change is so that the solver, which uses double precision floating point, and does not solve the problem exactly, will solve the problem reasonably well, despite roundoff errors and tolerances in the solver.

You should show use the solver and CVX output. Also show and explain to us why you believe the solution returned by the solver/CVX is not optimal. There is no point is showing us this if in fact you didn’t make offsetting changes when you multiplied H.

11

For the first section, I guess that I made a mistake, while I was generating; ‘H’ (please note that ‘H’ is random)
Consequently, I generate the normalized version of ‘H’, which therefore it is not required to make offsetting changes to other data.

For the second section, my problem should provide a rank-one solutions according to my proof. Nevertheless, the obtained solutions are not rank-one. For instance,

1.0e+03 *[-1.6542 0 0 0 0
0 -0.0913 0 0 0
0 0 0.0000 0 0
0 0 0 0.0913 0
0 0 0 0 1.6542]

, which are the eigenvalues of one obtained optimal solution.

12

What proof do you have, as opposed to hope and desire, that the solution to the problem you specified must be rank one? That is a non-convex constraint, and you have not specified it. So if it must hold, there must be some mathematical property of your problem that would guarantee such a result. There are some such problems and proofs in the literature, but in general, it is not guaranteed (and may not be likely) that a a rank one solution will be obtained when only a semidefinite constraint is imposed.

13

Exactly, as a consequence, I resort to SDP to relax the rank-one constraint. Besides, I read a lot in this context regarding proofing rank-one property, and successfully proof it mathematically that the solution should satisfy the rank-one solution. But, CVX would not guarantee such a result!

14

Well, you haven’t shown us the proof. Until then, we will not presume CVX, or the solver (Mosek?) it calls is at fault. CVX’s job is to corectly solve the problem you enter. Whether the solution to the problem you enter is useful for your intended purposes is up to you.

People often reach invalid conclusions about the efficacy or adequacy of various algorithms, based on only seeing examples in which they are successful. In many cases, the typical user is much more likely to encounter problems in which the algorithm will work poorly, than well. For example, Successive Convex Approximation, if you don’t happen to be Stephen Boyd, and have his judgement and abilities. This is similar in spirit to the Taylor Series horror stories I have encountered.- see https://www.linkedin.com/pulse/high-crimes-misdemeanors-analysis-biz-part-i-my-funny-mark-l-stone/ .