Help regarding solving an SDP

1

I am using CVX to solve an SDP problem. CVX fails to solve the problem and shows an error msg " lack of progress in infeas ". The matlab output I am getting are as follows

----------------------------------------Output-----------------------------------------------------
Calling SDPT3 4.0: 18 variables, 10 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 10
dim. of sdp var = 6, num. of sdp blk = 2
dim. of socp var = 6, num. of socp 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.4e+00|8.7e+00|6.1e+02| 2.000000e+01 0.000000e+00| 0:0:00| chol 1 1
1|0.989|1.000|3.7e-02|9.6e-02|2.4e+01| 1.706179e+01 -1.224551e+00| 0:0:00| chol 1 1
2|0.989|0.996|4.1e-04|1.7e-02|6.7e-01|-4.709268e-01 -1.076886e+00| 0:0:00| chol 1 1
3|0.965|0.987|1.4e-05|1.3e-03|2.3e-02|-1.063321e+00 -1.084105e+00| 0:0:00| chol 1 1
4|1.000|1.000|4.1e-05|9.9e-05|8.9e-03|-1.078651e+00 -1.081513e+00| 0:0:00| chol 1 1
5|0.869|0.745|1.7e-05|3.7e-05|2.0e-03|-1.078973e+00 -1.076262e+00| 0:0:00| chol 1 1
6|1.000|0.941|1.4e-05|6.5e-06|7.2e-04|-1.078620e+00 -1.072879e+00| 0:0:00| chol 1 1
7|0.628|1.000|1.1e-05|2.9e-06|3.9e-04|-1.077274e+00 -1.072026e+00| 0:0:00| chol 1 1
8|1.000|1.000|1.1e-05|2.2e-06|1.6e-04|-1.077390e+00 -1.070427e+00| 0:0:00| chol 1 1
9|0.676|0.964|9.2e-06|2.3e-06|1.6e-04|-1.076066e+00 -1.068594e+00| 0:0:00| chol 1 1
10|0.020|0.495|9.0e-06|3.0e-06|4.8e-03|-1.075725e+00 -1.058955e+00| 0:0:00| chol 1 1
11|0.788|0.287|1.9e-06|4.0e-06|3.9e-02|-1.034670e+00 -1.072933e+00| 0:0:00| chol 1 1
12|0.309|0.654|1.3e-06|1.8e-06|2.9e-02|-1.039484e+00 -1.059514e+00| 0:0:00|
lack of progress in infeas

number of iterations = 12
primal objective value = -1.07606623e+00
dual objective value = -1.06859448e+00
gap := trace(XZ) = 1.57e-04
relative gap = 4.99e-05
actual relative gap = -2.38e-03
rel. primal infeas (scaled problem) = 9.23e-06
rel. dual " " " = 2.30e-06
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.5e+00, 3.9e+02, 3.9e+02
norm(A), norm(b), norm© = 6.0e+00, 3.0e+00, 2.8e+00
Total CPU time (secs) = 0.15
CPU time per iteration = 0.01
termination code = 0
DIMACS: 9.2e-06 0.0e+00 3.2e-06 0.0e+00 -2.4e-03 5.0e-05

Status: Solved
Optimal value (cvx_optval): +0.0685945

----------------------------------------------------end----------------------------------------------

However, when I am multiplying the objective function by 10^4 cvx is able to solve the SDP accurately. Then the output is

-----------------------------------output------------------------------------------------
Calling SDPT3 4.0: 18 variables, 10 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 10
dim. of sdp var = 6, num. of sdp blk = 2
dim. of socp var = 6, num. of socp 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.0e+00|8.7e+00|3.6e+06| 1.200060e+05 0.000000e+00| 0:0:00| chol 1 1
1|0.988|0.983|3.5e-02|6.1e-01|2.4e+05| 8.834179e+04 -5.342719e+03| 0:0:00| chol 1 1
2|0.979|1.000|7.2e-04|2.4e-01|2.3e+04| 4.025289e+03 -8.566728e+03| 0:0:00| chol 1 1
3|0.981|1.000|1.4e-05|1.2e-01|9.6e+02|-1.011400e+04 -9.530978e+03| 0:0:00| chol 1 1
4|0.624|1.000|5.3e-06|6.0e-02|4.2e+02|-1.048841e+04 -1.015833e+04| 0:0:00| chol 1 1
5|0.215|0.195|4.2e-06|5.4e-02|3.7e+02|-1.042035e+04 -1.000887e+04| 0:0:00| chol 1 1
6|0.414|0.436|2.5e-06|3.7e-02|2.5e+02|-1.042433e+04 -1.006334e+04| 0:0:00| chol 1 1
7|0.305|0.441|1.7e-06|2.4e-02|2.2e+02|-1.038446e+04 -1.007869e+04| 0:0:00| chol 1 1
8|0.285|0.792|1.2e-06|8.0e-03|2.2e+02|-1.033242e+04 -1.012363e+04| 0:0:00| chol 1 1
9|0.446|1.000|6.8e-07|1.9e-03|2.1e+02|-1.022707e+04 -1.015190e+04| 0:0:00| chol 1 1
10|0.746|0.820|1.7e-07|1.1e-03|7.3e+01|-1.011609e+04 -1.007428e+04| 0:0:00| chol 1 1
11|0.309|1.000|1.2e-07|4.7e-04|6.4e+01|-1.009341e+04 -1.003637e+04| 0:0:00| chol 1 1
12|0.776|0.709|2.7e-08|3.0e-04|2.7e+01|-1.002348e+04 -1.001166e+04| 0:0:00| chol 1 1
13|0.619|0.680|1.0e-08|1.8e-04|1.4e+01|-1.000872e+04 -1.000322e+04| 0:0:00| chol 1 1
14|0.708|0.844|3.0e-09|7.7e-05|7.1e+00|-1.000084e+04 -1.000048e+04| 0:0:00| chol 1 1
15|0.910|1.000|2.7e-10|2.9e-05|2.6e+00|-9.998592e+03 -1.000021e+04| 0:0:00| chol 1 1
16|1.000|1.000|3.7e-14|1.5e-05|5.8e-01|-9.999514e+03 -9.999941e+03| 0:0:00| chol 1 1
17|0.845|1.000|1.1e-14|5.3e-12|1.2e-01|-9.999905e+03 -1.000003e+04| 0:0:00| chol 1 1
18|1.000|0.972|6.5e-15|5.4e-12|3.3e-02|-9.999971e+03 -1.000000e+04| 0:0:00| chol 1 1
19|0.828|1.000|3.3e-15|2.8e-12|7.7e-03|-9.999995e+03 -1.000000e+04| 0:0:00| chol 1 1
20|1.000|0.915|5.5e-15|2.8e-12|2.1e-03|-9.999998e+03 -1.000000e+04| 0:0:00| chol 1 1
21|0.858|1.000|2.2e-15|8.5e-13|3.3e-04|-1.000000e+04 -1.000000e+04| 0:0:00| chol 1 1
22|1.000|0.883|2.9e-15|2.8e-12|1.0e-04|-1.000000e+04 -1.000000e+04| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 22
primal objective value = -9.99999991e+03
dual objective value = -1.00000000e+04
gap := trace(XZ) = 1.00e-04
relative gap = 5.02e-09
actual relative gap = 5.02e-09
rel. primal infeas (scaled problem) = 2.91e-15
rel. dual " " " = 2.80e-12
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.4e+04, 1.4e+05, 8.8e+04
norm(A), norm(b), norm© = 6.0e+00, 2.0e+04, 2.8e+00
Total CPU time (secs) = 0.20
CPU time per iteration = 0.01
termination code = 0
DIMACS: 2.9e-15 0.0e+00 3.9e-12 0.0e+00 5.0e-09 5.0e-09

Status: Solved
Optimal value (cvx_optval): +1.2115e-05
--------------------------------------------end----------------------------------------------------------------------

Please help me to understand why it is happening. Thankyou

2

Your problem likely has poor scaling. Perhaps you could get more specific guidance if you showed a reproducible problem, complete with input data.

1 Like
3

Thank you sir. I am attaching my code below.

-----------------------------Matlab Code --------------------------------------

cvx_begin  sdp
total_connections=size(anchor_connected,2);
variable h(total_connections)
variable x(2,1)
variable z
minimize 1*( (h.*lambda_source_anchor_connected' -  alpha1 )' ...
    *(h.*lambda_source_anchor_connected' -   alpha1 ) )

for j=1:total_connections    
    h(j)==[anchor_connected(:,j); -1]' * [eye(2) x;x' z] * [anchor_connected(:,j); -1];
end
[eye(2) x;x' z]>=semidefinite(3);
cvx_end

Given parameters are: alpha1= 0.0056; lambda_source_anchor_connected = [1.1246e-06 1.1245e-06 1.1248e-06 1.1246e-06]; anchor_connected=[ 0 0 100 100; 0 100 0 100];

I am estimating the value of x.

4

Your objective function is a square, so the optimal objective value must be >= 0 if the optimization problem were solved exactly.

All your solutions (also true using SeDuMi) produce an optimal objective value of zero, within solver tolerance. There are an infinite number of combinations of x and z which satisfy the semidefinite constraint and produce optimal objective value of zero.

So it appears that your problem may not be very well formed.

Note: Your use of [eye(2) x;x' z]>=semidefinite(3); in SDP mode is undocumented. The documented syntax would be [eye(2) x;x' z] >= 0.
Or [eye(2) x;x' z] == semidefinite(3); if not in SDP mode. Your syntax appears to produce the correct result in this case, although I am not sure if that will always be the case.

1 Like
5

Thanks a lot for you help. I will change my syntax. The whole SDP starts to produce correct answer once I scale the objective function by 10^4.

6

What you call the “correct” answer is just one of many “answers” to this poorly specified problem.

7

Thank you sir for your kind help. I will try to work rephrase the problem.