CVX failed when different scaling is applied

1

Recently, I am using the cvx to solve an outage constrained robust beamforming problem. The problem is finally formulated as a convex problem by appling the S-procedure, which is

cvx_begin
variable F(J,J) hermitian semidefinite
variable t(K_num,1)
A = (as_ele_Tx * as_ele_Tx').';
% A = 1/2 *(A + A');
A1 = -1 .* A;
minimize( trace(A1 * F) )
subject to

for ii=1:J
    F(ii,ii) <= P;
end
for i = 1:(K_num)
    C_i = epsilon .* diag(ones(J,1));
    d_i = sqrt(chi2inv(1 - rou, 2 * J) ./ 2);

    [-1 .* sqrt(C_i) * F * sqrt(C_i) + t(i) .* diag(ones(J,1))   (-1 .* sqrt(C_i) * F * Hm(i,:)'); ...
        (-1 .* sqrt(C_i) * F * Hm(i,:)')'   gamma - Hm(i,:) * F * Hm(i,:)' - t(i) * d_i^2] == hermitian_semidefinite( J + 1 );

    t(i) >= 0;
end


cvx_end

Specifically, the epsilon in the formulation is zero, which denotes a special scenario of my problem. Then I found that, for some P values, for example, between 0.3 and 2, the problem can be perfectly solved. However, for smaller P like 0.01 and larger P like 5, CVX will fail and gives me something like,

Calling SDPT3 4.0: 9552 variables, 1302 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 1302
dim. of sdp var = 516, num. of sdp blk = 7
dim. of linear var = 42

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|8.3e+01|6.7e+02|3.3e+06| 3.963474e+00  0.000000e+00| 0:0:00| chol  1  1 
 1|1.000|0.812|1.9e-06|1.3e+02|9.5e+05| 7.102757e+01  3.379866e+02| 0:0:01| chol  1  1 
 2|1.000|0.989|9.8e-06|1.6e+00|1.2e+04| 7.042052e+01  5.535133e+00| 0:0:01| chol  1  1 
 3|1.000|1.000|2.1e-07|7.5e-02|5.7e+02| 4.888803e+01  1.165530e+00| 0:0:02| chol  1  1 
 4|0.988|1.000|1.9e-08|3.8e-02|7.1e+01| 6.888510e+00  1.035422e+00| 0:0:02| chol  1  1 
 5|1.000|0.665|1.3e-08|2.0e-02|3.0e+01| 9.572384e+00  8.121442e+00| 0:0:02| chol  1  1 
 6|1.000|1.000|1.1e-09|3.4e-03|3.1e+00| 6.503451e+00  6.809413e+00| 0:0:02| chol  1  1 
 7|0.989|1.000|8.7e-11|1.0e-03|4.3e-01| 6.472475e+00  6.638532e+00| 0:0:03| chol  1  1 
 8|1.000|1.000|1.9e-11|3.0e-04|6.7e-02| 6.473451e+00  6.523251e+00| 0:0:03| chol  1  1 
 9|1.000|0.985|3.7e-12|3.4e-05|5.1e-03| 6.473632e+00  6.480623e+00| 0:0:03| chol  1  1 
10|1.000|0.217|6.8e-12|2.8e-05|7.8e-03| 6.471058e+00  6.479344e+00| 0:0:03| chol  1  1 
11|0.003|0.003|1.3e-09|2.7e-05|7.8e-03| 6.469931e+00  6.479296e+00| 0:0:03| chol  1  1 
12|0.011|0.003|1.4e-09|2.7e-05|8.1e-03| 6.466552e+00  6.479220e+00| 0:0:04|
  stop: steps too short consecutively
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value =  6.47363249e+00
 dual   objective value =  6.48062327e+00
 gap := trace(XZ)       = 5.12e-03
 relative gap           = 3.67e-04
 actual relative gap    = -5.01e-04
 rel. primal infeas (scaled problem)   = 3.75e-12
 rel. dual     "        "       "      = 3.44e-05
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 4.2e+02, 1.3e-01, 1.3e-01
 norm(A), norm(b), norm(C) = 8.6e+01, 5.2e+01, 1.0e+00
 Total CPU time (secs)  = 3.63  
 CPU time per iteration = 0.30  
 termination code       = -5
 DIMACS: 6.4e-11  0.0e+00  3.5e-05  0.0e+00  -5.0e-04  3.7e-04
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Failed
Optimal value (cvx_optval): NaN

What bothers me is that, for larger P, I can understand why it will fail for the corresponding scenario of my application, but for smaller P, it was supposed to be solved more easily but it just failed. So right now I really need some help to figure out why the smaller P will fail.

2

Numerical issues can hit in different ways. There is no good answer to your question. Trying a bunch of different solvers would be my first suggestion.

3

Also note that P appears only as the RH of a <= constraint. So making P too small might cause “failure” due to infeasibility. Does CVX report the problem as infeasible when the very small values of P are used? If so, that is a very different type of failure than the solver running into numerical difficulties, as occurred in the output you showed.

4

Really thanks for the answer. I will try some other solvers or reformulate my problem.

5

Hi Mark, really thanks for the answer. I think you are right, somehow, small P will lead to numerical difficulities of my formulation with S-procedure implemented. As after I modified the P into the semidefinite constraint and let F(ii,ii) <= 1, the problem with same P then can be well solved. So, directly using P on the RHS might casue some kind of numerical difficulities, although I don’t how to explain why right now.

Meanwhile, for very small P situation (original formulation, without modification in the last paragraph), I also tried, which can be well solved, and solver stops at “stop: max(relative gap, infeasibilities) < 1.49e-08”. The main problem here is that, for very small P, as the gamma value is the same as above, the semidefinite constraint that relates to the gamma value will be satisfied anyway. Therefore, the solver only needs to make sure that F(ii,ii) <= P and the minimization objective is satified. I think this why the very small P does not fail. But, if we also get a smaller gamma, the same problem will appear again.

To sum up, I think when P gets to a certain lower limit, the relation between P and gamma will cause the numerical difficulties, as long as the P is not that small to make the semidefinite constraints are satisfied anyway.

6 
for ii=1:J
    F(ii,ii) <= P;
end

can be written more simply in vectorized way as
diag(F) <= P

8

ah yes, really thanks!!

9

Hi Mark, sry it’s me again. After I reformulated the problem, for some paramter configuration, the infeasiblity showed up. Could you enlighten me a bit more to cope with the infeasiblity? The problem now is

cvx_begin 
variable F(J,J) hermitian semidefinite
variable t(K_num,1)
A = (as_ele_Tx * as_ele_Tx').';
% A = 1/2 *(A + A');
A1 = -1 .* A;
minimize( trace(A1 * F) )
subject to
for i = 1:(K_num)
C_i = epsilon .* diag(ones(J,1));
d_i = sqrt(chi2inv(1 - rou, 2 * J) ./ 2);

[-1 .* sqrt(C_i) * F * sqrt(C_i) + t(i) .* diag(ones(J,1))   (-1 .* sqrt(C_i) * F * Hm(i,:)'); ...
    (-1 .* sqrt(C_i) * F * Hm(i,:)')'   gamma / P - Hm(i,:) * F * Hm(i,:)' - t(i) * d_i^2] == hermitian_semidefinite( J + 1 );
t(i) >= 0;
end

%for ii=1:J
%    Q = zeros(J,J);
%    Q(ii,ii) = 1;
%    trace(Q * F) == 1;
%end
diag(F) == 1;

cvx_end

For this simulation, P is fixed, and the value is 1/36. gamma is 1e-5. rou is 0.1. Hm and A are known matrices. For epsilon larger than around 1e-5, the problem will be infeasible. For example, when epsilon = 1e-3, the output is like

Calling SDPT3 4.0: 9516 variables, 1266 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 1266
dim. of sdp var = 516, num. of sdp blk = 7
dim. of linear var = 6

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|8.3e+01|1.3e+02|3.3e+06| 3.817666e+03 0.000000e+00| 0:0:00| chol 1 1
1|1.000|0.989|7.1e-07|1.8e+00|4.7e+04| 3.405271e+03 1.001307e+02| 0:0:01| chol 1 1
2|0.693|1.000|1.3e-06|9.0e-02|3.0e+03| 1.259048e+03 2.018489e+02| 0:0:03| chol 1 1
3|1.000|0.420|2.1e-06|6.4e-02|2.6e+03| 1.607813e+03 7.690000e+02| 0:0:05| chol 1 1
4|0.237|0.523|8.7e-07|3.7e-02|1.9e+03| 3.090768e+02 9.219622e+01| 0:0:07| chol 1 1
5|0.970|0.708|2.2e-07|1.6e-02|7.5e+02|-3.776150e+01 6.750934e+01| 0:0:09| chol 1 1
6|1.000|0.687|1.0e-07|7.2e-03|3.6e+02|-1.255251e+02 2.397545e+01| 0:0:11| chol 1 1
7|0.314|0.280|6.5e-08|5.7e-03|3.2e+02|-2.793324e+02 1.177937e+01| 0:0:12| chol 1 1
8|0.043|0.129|6.2e-08|5.1e-03|2.9e+02|-4.416025e+02 5.788052e+00| 0:0:14| chol 1 1
9|0.026|0.069|6.0e-08|4.7e-03|2.9e+02|-8.733218e+02 1.988144e+00| 0:0:16| chol 1 1
10|0.006|0.011|6.0e-08|4.7e-03|3.4e+02|-2.498903e+03 2.069494e+00| 0:0:18| chol 1 1
11|0.006|0.007|5.9e-08|4.7e-03|6.6e+02|-1.550252e+04 2.343388e+00| 0:0:19| chol 1 1
12|0.002|0.003|5.9e-08|4.6e-03|1.6e+03|-6.435581e+04 2.034864e+00| 0:0:21| chol 1 1
13|0.005|0.009|5.9e-08|4.6e-03|9.3e+03|-7.852549e+05 1.750319e+00| 0:0:23| chol 1 1
14|0.000|0.001|5.9e-08|4.6e-03|3.7e+04|-3.504161e+06 1.271302e+00| 0:0:25| chol 1 1
15|0.000|0.001|5.9e-08|4.6e-03|1.4e+05|-1.503901e+07 7.949758e-01| 0:0:27| chol 1 1
16|0.000|0.001|7.7e-08|4.6e-03|7.3e+05|-8.972968e+07 1.178505e+00| 0:0:28| chol 1 1
17|0.002|0.002|2.0e-06|4.6e-03|1.7e+07|-2.873482e+09 2.291976e+00| 0:0:30| chol 2 2
18|0.001|0.001|2.6e-05|4.6e-03|4.9e+08|-9.346213e+10 1.877488e+00| 0:0:32| chol 2 2
stop: primal infeas has deteriorated too much, 6.4e+00
19|1.000|0.000|2.6e-05|4.6e-03|4.9e+08|-9.346213e+10 1.877488e+00| 0:0:34|
prim_inf,dual_inf,relgap = 2.62e-05, 4.58e-03, 5.26e-03
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 19
residual of dual infeasibility
certificate X = 5.37e-10
reldist to infeas. <= 1.87e-14
Total CPU time (secs) = 33.77
CPU time per iteration = 1.78
termination code = 2
DIMACS: 4.5e-04 0.0e+00 1.6e-02 0.0e+00 -1.0e+00 5.3e-03

Status: Infeasible
Optimal value (cvx_optval): +Inf

So, how we cope with this infeasiblity usually?

10

epsilon almost zero makes C_i almost zero. When that is true, the first additive term of -1 .* sqrt(C_i) * F * sqrt(C_i) + t(i) .* diag(ones(J,1)) is almost zero, which means that t(i) can be zero and still make this block psd, which it must be. Perhaps the only reason the problem is feasible with even a slightly positive epsilon is because of the solver’s feasibility tolerance which allows slight “cheating” on positive semidefinitness or nonegativity of t. You haven’t provided the input data, so I cant run it myself, and will therefore leave further diagnosis to you, for instance as to whether other terms allow tt(i) to be sufficiently positive to overcome the first term. C_i and t(i)also appear in other terms. Anyhow, you should pay attention to what is going on with t when the problem is feasible.

All but the first section of Debugging infeasible models - YALMIP apll applies to CVX. Together with my hints, hopefully you can figure things out.

11

Really thanks for the answer, Mark. I will follow the hint to figure out why, and especially see the value of t. Meanwhile, could you please give a glimpse maybe, if I paste an executable code with input data below?

Btw, in cvx, how does the PSD constraint is satisfied? Like to calculate all the leading principal minors to make sure they are larger than 0?

12

Enforcement of psd constraints is done by the solver, not directly by CVX. Solvers don’t do it by checking that the leading principal minors are nonnegative, which would be a numerically horrendous thing to do.

13

Got it, really thanks!