Infeasible SDP (large sparse matrices)

1

Hi,

I am attempting to solve an SDP problem using CVX. Unfortunately, I haven’t been able to obtain a result, as the solver terminates with the message ‘Status: Infeasible’. The code I am using, and the associated variables are as follows:

cvx_begin sdp
variable gamma_i(N)
minimize(sum(((gamma_i - max_beta)./(min_beta - max_beta))))
subject to
(D - eps.*identity_mat)*diag(gamma_i) - A >= 0;
gamma_i >= min_gamma;
gamma_i <= max_gamma;
cvx_end

N --> 500
max_beta --> 0.0056
min_beta —> 0.0011
D —> diag(delta_i) [500 x 500], where delta_i is a 500x1 vector with all entries being equal to 0.1
eps --> 0.5
min_gamma —> 1/max_beta = 178.2332
max_gamma --> 1/min_beta = 891.1659
A —> 500 x 500 matrix, with dominant eigenvalue 21.38

This code is based on the work completed in this paper:

https://arxiv.org/pdf/1303.3984.pdf (Optimal Vaccine Allocation to Control Epidemic
Outbreaks in Arbitrary Networks)

1 Like
2

Log output from the solver would be helpful.

1 Like
3

Hi Michal,

Thank you so much for the response!

Here’s the solver log output:

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

num. of constraints = 500
dim. of sdp var = 500, num. of sdp blk = 1
dim. of linear var = 1000

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|3.1e+03|3.1e+01|7.9e+08|-1.469531e+06 0.000000e+00| 0:0:00| spchol 1 1
1|1.000|0.816|9.6e-04|5.7e+00|1.1e+08| 4.013989e+06 1.741893e+03| 0:0:00| chol 1 1
2|1.000|0.910|7.9e-04|5.1e-01|1.1e+07| 2.248266e+06 1.528083e+02| 0:0:00| chol 1 1
3|1.000|0.202|1.7e-04|4.1e-01|1.2e+07|-1.764399e+07 1.262098e+02| 0:0:00| chol 1 1
4|1.000|0.070|2.4e-04|3.8e-01|7.4e+07|-4.142158e+08 1.293318e+02| 0:0:01| chol 1 1
5|0.064|0.017|2.4e-04|3.7e-01|3.4e+08|-5.429773e+09 1.333419e+02| 0:0:01| chol 1 1
6|0.033|0.035|2.4e-04|3.6e-01|1.4e+09|-6.789565e+10 1.303868e+02| 0:0:01| chol 1 1
7|0.002|0.008|2.3e-04|3.6e-01|4.6e+09|-4.299894e+11 1.295038e+02| 0:0:01| chol 1 1
8|0.001|0.005|2.3e-04|3.6e-01|1.7e+10|-3.008545e+12 1.289529e+02| 0:0:01| chol 2 2
9|0.000|0.003|2.3e-04|3.6e-01|6.2e+10|-2.292797e+13 1.286149e+02| 0:0:01| chol 2 2
10|0.000|0.002|2.3e-04|3.5e-01|2.2e+11|-1.875385e+14 1.284368e+02| 0:0:02| chol 2 2
11|0.000|0.001|2.5e-04|3.5e-01|7.5e+11|-1.610789e+15 1.283544e+02| 0:0:02| chol 2 2
12|0.000|0.000|6.8e-04|3.5e-01|2.4e+12|-1.421452e+16 1.283211e+02| 0:0:02| chol 2 2
13|0.000|0.000|5.3e-03|3.5e-01|7.6e+12|-1.269780e+17 1.283089e+02| 0:0:02| chol 2 2
14|0.000|0.000|4.7e-02|3.5e-01|2.3e+13|-1.139688e+18 1.283049e+02| 0:0:02| chol 2 2
15|0.000|0.000|4.9e-02|3.5e-01|8.3e+12|-1.190890e+18 1.283037e+02| 0:0:02| chol 2 2
16|0.000|0.000|5.3e-02|3.5e-01|5.5e+12|-1.286176e+18 1.283034e+02| 0:0:02| chol 2
stop: steps in predictor too short: pstep = 8.79e-07, dstep = 3.83e-06

17|0.000|0.000|5.3e-02|3.5e-01|5.5e+12|-1.286176e+18 1.283034e+02| 0:0:02|
prim_inf,dual_inf,relgap = 5.34e-02, 3.54e-01, 4.26e-06
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 17
residual of dual infeasibility
certificate X = 5.17e-20
reldist to infeas. <= 1.45e-19
Total CPU time (secs) = 2.49
CPU time per iteration = 0.15
termination code = 2
DIMACS: 5.5e-02 0.0e+00 7.9e+00 0.0e+00 -1.0e+00 4.3e-06

Status: Infeasible
Optimal value (cvx_optval): +Inf

Thanks!

1 Like
4

You had attempted to solve using only SDP3 solver… It will be appreciative if you share results for Solver Sedumi for comparison

Supra