Unbounded SDP but the problem is feasible/bounded

1

Dear all,

I’m solving the following optimization problem with CVX:

cvx_begin quiet
    variable W(N,N) hermitian
    variable t
    maximize( trace(R(:,:,1)*W) )
     subject to
     for i=1:N
        W(i,i) == t;
     end
     trace(J(:,:,1)*W) == 1;  
     W == hermitian_semidefinite(N);
     
cvx_end

Where R(:,:,1) and J(:,:,1) are Hermitian semidefinite positive matrices. Depending the value of these matrices, I obtain the following result:

Calling SDPT3 4.0: 1296 variables, 36 equality constraints

num. of constraints = 36
dim. of sdp var = 72, num. of sdp blk = 1

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.6e+01|1.0e+01|5.2e+04|-7.440721e+02 0.000000e+00| 0:0:00| chol 1 1
1|1.000|0.969|2.3e-05|6.1e-01|2.3e+03|-7.255549e+02 -1.849722e+01| 0:0:00| chol 1 1
2|1.000|0.254|9.6e-05|4.8e-01|3.0e+03|-4.317215e+03 -2.617684e+01| 0:0:00| chol 1 1
3|0.016|0.016|1.1e-04|4.7e-01|3.6e+03|-1.885771e+04 -2.850937e+01| 0:0:00| chol 1 1
4|0.009|0.013|1.2e-04|4.7e-01|6.0e+03|-1.070550e+05 -3.634638e+01| 0:0:00| chol 1 1
5|0.008|0.012|1.2e-04|4.6e-01|2.3e+04|-1.021671e+06 -8.827492e+01| 0:0:00| chol 1 2
6|0.001|0.002|1.2e-04|4.6e-01|7.2e+04|-3.831836e+06 -1.840813e+02| 0:0:00| chol 2 2
7|0.001|0.002|1.2e-04|4.6e-01|3.1e+05|-2.008218e+07 -4.546200e+02| 0:0:00| chol 2 2
8|0.000|0.000|1.2e-04|4.6e-01|4.5e+05|-2.972326e+07 -5.995847e+02| 0:0:00| chol 2 2
9|0.000|0.000|1.2e-04|4.6e-01|6.5e+05|-4.249214e+07 -7.230162e+02| 0:0:00| chol 2 2
10|0.000|0.000|1.2e-04|4.6e-01|7.4e+05|-4.726870e+07 -7.231650e+02| 0:0:00| chol 2 * 4
11|0.000|0.000|1.1e-04|4.6e-01|7.5e+05|-4.537039e+07 -6.132804e+02| 0:0:00| chol 2 3
12|0.000|0.000|1.1e-04|4.6e-01|8.2e+05|-4.905174e+07 -4.493363e+02| 0:0:00| chol 2 2
13|0.000|0.000|1.1e-04|4.6e-01|9.4e+05|-5.479629e+07 -5.572144e+02| 0:0:00| chol 2 2
14|0.000|0.000|1.1e-04|4.6e-01|1.1e+06|-7.018672e+07 -7.939857e+02| 0:0:00| chol 2 2
15|0.000|0.000|1.1e-04|4.6e-01|1.3e+06|-8.551341e+07 -1.010778e+03| 0:0:00| chol 2 3
16|0.000|0.000|1.1e-04|4.6e-01|1.8e+06|-1.254625e+08 -1.347171e+03| 0:0:00| chol 3 3
17|0.000|0.000|1.1e-04|4.6e-01|2.7e+06|-1.973905e+08 -1.649807e+03| 0:0:00| chol 3 3
18|0.000|0.000|1.3e-04|4.6e-01|4.2e+06|-3.216027e+08 -2.165831e+03| 0:0:00| chol 3 3
19|0.000|0.000|1.6e-04|4.6e-01|5.5e+06|-4.286403e+08 -2.621341e+03| 0:0:00| chol 3 3
20|0.000|0.000|2.5e-04|4.6e-01|7.1e+06|-5.696079e+08 -3.248557e+03| 0:0:00| chol 3 3
21|0.000|0.000|2.3e-04|4.6e-01|8.4e+06|-6.875518e+08 -3.765532e+03| 0:0:00| chol 3 3
22|0.000|0.000|3.3e-04|4.6e-01|1.2e+07|-1.003153e+09 -4.627078e+03| 0:0:00| chol 3 * 5
23|0.000|0.000|3.5e-04|4.6e-01|1.5e+07|-1.314203e+09 -5.184290e+03| 0:0:00| chol 3 * 5
24|0.000|0.000|7.9e-04|4.6e-01|2.0e+07|-1.835452e+09 -6.464178e+03| 0:0:00| chol 3 * 5
25|0.000|0.000|8.4e-04|4.6e-01|2.6e+07|-2.312570e+09 -7.098093e+03| 0:0:00| chol 3 * 6
26|0.000|0.000|1.9e-03|4.6e-01|3.4e+07|-3.217746e+09 -9.815672e+03| 0:0:00| chol 3 * 5
27|0.000|0.000|2.2e-03|4.6e-01|3.8e+07|-3.609259e+09 -1.040805e+04| 0:0:00| chol * 5 * 5
28|0.000|0.001|2.4e-03|4.6e-01|3.9e+07|-4.012248e+09 -1.394667e+04| 0:0:00| chol 4 * 6
29|0.000|0.000|2.3e-03|4.6e-01|4.2e+07|-4.271910e+09 -1.518461e+04| 0:0:00| chol 4 * 6
30|0.000|0.000|4.1e-03|4.6e-01|5.1e+07|-5.394488e+09 -1.831299e+04| 0:0:00| chol 4 * 5
31|0.000|0.000|4.0e-03|4.5e-01|5.4e+07|-5.822215e+09 -1.936435e+04| 0:0:00|
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 31
residual of dual infeasibility
certificate X = 1.71e-10
reldist to infeas. <= 2.59e-11
Total CPU time (secs) = 0.45
CPU time per iteration = 0.01
termination code = 2
DIMACS: 4.0e-03 0.0e+00 6.2e-01 0.0e+00 -1.0e+00 9.3e-03

Status: Unbounded
Optimal value (cvx_optval): +Inf

However, to the best of my knowledge, the problem is not unbounded or unfeasible.

Could anyone help on how to identify the problem?

Thank you,

2

The solver is reporting dual infeasibiity, which corresponds to primal unboundedness, which is what CVX reports. You haven’t provided us the input data to enable us to investigate. It looks to me that whether or not the problem is unbounded can depend on the input data provided (R(:,:,1) and J(:,:,1)). You could try another solver, such as sedumi, to see whether that also results in a claim of (primal) unboundedness.

Why do you believe the problem is not unbounded?

3

Thanks for your response,

In general Tr(JR) is not equal to zero so that if the objective function Tr(RW) tends to infinity, it will entail that Tr(JW) to be infinity which is not possible due to the equality constraint.

Maybe the reason is that by time to time J takes very high values and R very low and this will induce certain ‘numerical unfeasiblity’. Does this make any sense?

4

As I said before, you haven’t shown us the input data. I am not convinced of your explanation on boundedness. Are you sure there are not “offsetting” changes possible to certain elements of W which allow the constraints to be satisfied, while increasing the objective function without bound?

5

R and J are rank-1 matrices obtained like

R = randn(N^2,1);
R = R*R';
J = randn(N^2,1);
J = J*J';
6

This is unbounded because t is a CVX (optimization) variable. So the optimizer can make it whatever it “wants” to drive the objective function up, without bound.