Feasible SDP fails during minimization

#1

Hi. I’ve been having an issue for a while where the feasibility problem is solved (implying the existence of a solution). However when I take the next step, and attempt to make this a minimization problem rather than a feasibility problem, cvx now fails to converge to a solution. P.S. I’m sorry that the last bit of results are bolded, I’m not familiar with this markup environment and I don’t know how to unbold it.

An analogy would be to say “find x such that x < 10,” and then after that is shown to be feasible, you might introduce a new optimization variable b and say “minimize b such that x < b, and b > 9.” The problem I’m having is that cvx fails to find x in the second case. So I’m wondering if there is something I could be doing differently to make this easier to solve (if it’s a numerical issue).

Any thoughts are appreciated. This could of course be addressed by turning this into a sort of bisection problem, and sequentially determining the feasibility of systems with successively smaller bounds. But my actual research problem is a bit more complicated, and I’m wondering if this issue is indicative of some bigger numerical challenge.

This is my first time posting here, so perhaps I don’t know the correct etiquette when asking questions. But I will provide some more context if anyone can provide some insight. The specific code involves minimizing the infinity-norm of a dynamic linear system; so what I want to ultimately do is maximize some quantity, eta, which represents the inverse of an upper bound of the norm (so bigger eta means smaller norm

The relevant code follows:
In the commented line, I have replaced eta with a hard-set value of 1E-4. When I uncomment this line and instead comment the “maximize (eta)”, we are left with a feasibility problem where the goal is to show that a solution exists such that the norm of the system is upper bounded by 100. That problem is feasible. The code as shown makes it into a maximization problem, where we attempt to maximize eta (and thus minimize the norm), but in this case the solver fails to find a solution. I don’t think this is necessarily a scale issue; the “lmi1” matrix is 39 by 39.
In the case where I still keep eta as a variable, but just comment out “maximize (eta)” the solver now fails because steps are too short consecutively. Which is even more baffling since this is just a feasibility check, and a feasible solution clearly exists (eta = 1E-4).

cvx_begin
variable X(24,24) symmetric
variable Y(6,24)
variable eta(1,1)

``````lmi1 = -[A*X + X'*A' + B_u*Y + Y'*B_u' + eta*(B_w)*B_w', (C_z*X + D_uz*Y)';
C_z*X + D_uz*Y, -eye(size(C_z, 1));];
``````

% lmi1 = -[AX + X’A’ + B_uY + Y’B_u’ + (1E-4)(B_w)B_w’, (C_zX + D_uzY)’;
% C_zX + D_uzY, -eye(size(C_z, 1));];

maximize (eta)
subject to
X == semidefinite(24);
lmi1 == semidefinite(length(lmi1));
cvx_end

My feasible output is as follows:

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

num. of constraints = 552
dim. of sdp var = 63, num. of sdp blk = 2
dim. of free var = 108 convert ublk to lblk
number of nearly dependent constraints = 39
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 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.3e+06|1.0e+01|6.3e+07|-1.203825e+06 0.000000e+00| 0:0:00| spchol 1 1
1|0.286|0.462|2.3e+06|5.4e+00|3.6e+07|-8.567407e+05 0.000000e+00| 0:0:00| chol 1 1
2|0.777|0.957|5.2e+05|2.3e-01|4.3e+06|-1.885866e+05 0.000000e+00| 0:0:00| chol 1 2
3|0.814|0.359|9.7e+04|1.5e-01|1.4e+06|-3.299903e+04 0.000000e+00| 0:0:00| chol 1 1
4|0.903|0.545|9.4e+03|6.8e-02|3.8e+05|-2.518695e+03 0.000000e+00| 0:0:01| chol 1 1
5|0.816|0.552|1.7e+03|3.1e-02|1.5e+05|-1.190875e+02 0.000000e+00| 0:0:01| chol 1 1
6|0.793|0.343|3.6e+02|2.0e-02|9.2e+04| 2.680762e+02 0.000000e+00| 0:0:01| chol 1 1
7|0.836|0.365|5.9e+01|1.3e-02|5.7e+04| 3.374172e+02 0.000000e+00| 0:0:01| chol 1 1
8|0.742|0.367|1.5e+01|8.1e-03|3.6e+04| 3.427661e+02 0.000000e+00| 0:0:01| chol 1 1
9|0.555|0.367|6.7e+00|5.1e-03|2.3e+04| 3.446138e+02 0.000000e+00| 0:0:01| chol 1 1
10|0.611|0.293|2.6e+00|3.6e-03|1.6e+04| 3.380835e+02 0.000000e+00| 0:0:01| chol 1 1
11|0.721|0.451|7.3e-01|2.0e-03|8.5e+03| 3.253958e+02 0.000000e+00| 0:0:01| chol 1 1
12|0.856|0.598|1.1e-01|8.0e-04|3.4e+03| 2.945643e+02 0.000000e+00| 0:0:01| chol 1 1
13|0.778|0.443|2.3e-02|4.4e-04|1.7e+03| 2.373356e+02 0.000000e+00| 0:0:01| chol 1 1
14|0.267|0.094|1.7e-02|4.0e-04|1.7e+03| 2.134356e+02 0.000000e+00| 0:0:02| chol 1 1
15|0.296|0.292|1.2e-02|2.9e-04|1.3e+03| 1.885676e+02 0.000000e+00| 0:0:02| chol 1 1
16|0.368|0.133|7.7e-03|2.5e-04|1.1e+03| 1.558719e+02 0.000000e+00| 0:0:02| chol 1 1
17|0.403|0.325|4.6e-03|1.7e-04|8.1e+02| 1.245146e+02 0.000000e+00| 0:0:02| chol 1 2
18|0.424|0.153|2.6e-03|1.4e-04|7.0e+02| 9.432021e+01 0.000000e+00| 0:0:02| chol 1 1
19|0.464|0.363|1.4e-03|9.1e-05|4.7e+02| 6.869055e+01 0.000000e+00| 0:0:02| chol 1 1
20|0.445|0.156|7.8e-04|7.7e-05|4.1e+02| 5.008803e+01 0.000000e+00| 0:0:02| chol 1 2
21|0.325|0.135|5.3e-04|6.7e-05|3.8e+02| 4.164956e+01 0.000000e+00| 0:0:02| chol 1 2
22|0.316|0.126|3.6e-04|5.9e-05|3.6e+02| 3.565234e+01 0.000000e+00| 0:0:02| chol 2 2
23|0.316|0.126|2.5e-04|5.2e-05|3.4e+02| 3.125998e+01 0.000000e+00| 0:0:02| chol 2 2
24|0.321|0.129|1.7e-04|4.5e-05|3.2e+02| 2.798128e+01 0.000000e+00| 0:0:02| chol 2 2
25|0.329|0.133|1.1e-04|3.9e-05|3.0e+02| 2.549477e+01 0.000000e+00| 0:0:03| chol 2 2
26|0.332|0.135|7.6e-05|3.4e-05|2.9e+02| 2.369316e+01 0.000000e+00| 0:0:03| chol 2 2
27|0.343|0.140|5.0e-05|3.0e-05|2.7e+02| 2.227170e+01 0.000000e+00| 0:0:03| chol 2 2
28|0.354|0.148|3.3e-05|2.5e-05|2.5e+02| 2.102256e+01 0.000000e+00| 0:0:03| chol 2 2
29|0.381|0.157|2.2e-05|2.2e-05|2.3e+02| 1.973887e+01 0.000000e+00| 0:0:03| chol 2 2
30|0.392|0.170|1.5e-05|1.8e-05|2.1e+02| 1.838613e+01 0.000000e+00| 0:0:03| chol 2 2
31|0.472|0.200|1.1e-05|1.5e-05|1.8e+02| 1.615069e+01 0.000000e+00| 0:0:03| chol 2 2
32|0.549|0.258|7.1e-06|1.1e-05|1.5e+02| 1.304557e+01 0.000000e+00| 0:0:03| chol 2 3
33|0.706|0.333|4.2e-06|7.5e-06|1.0e+02| 9.115838e+00 0.000000e+00| 0:0:03| chol 2 2
34|0.909|0.625|1.0e-06|2.8e-06|4.0e+01| 5.029560e+00 0.000000e+00| 0:0:03| chol 2 3
35|1.000|0.177|1.5e-06|2.4e-06|3.0e+01| 3.323169e+00 0.000000e+00| 0:0:03| chol 2 3
36|1.000|0.280|1.5e-06|1.8e-06|2.2e+01| 2.409180e+00 0.000000e+00| 0:0:03| chol 2 3
37|1.000|0.297|1.5e-06|1.3e-06|1.5e+01| 1.753830e+00 0.000000e+00| 0:0:04| chol 2 4
38|1.000|0.317|1.2e-06|9.0e-07|1.1e+01| 1.290304e+00 0.000000e+00| 0:0:04| chol 3 3
39|1.000|0.396|7.6e-07|5.6e-07|6.5e+00| 8.393190e-01 0.000000e+00| 0:0:04| chol 3 4
40|1.000|0.441|3.7e-07|3.3e-07|3.6e+00| 5.183363e-01 0.000000e+00| 0:0:04| chol 4 4
41|1.000|0.487|1.4e-07|1.8e-07|1.7e+00| 3.216155e-01 0.000000e+00| 0:0:04| chol 5 5
42|1.000|0.433|6.8e-08|1.1e-07|8.8e-01| 2.098654e-01 0.000000e+00| 0:0:04| chol 6 5
43|1.000|0.511|2.5e-08|5.7e-08|3.6e-01| 1.196956e-01 0.000000e+00| 0:0:04| chol 7 8
44|1.000|0.496|9.4e-09|3.2e-08|1.2e-01| 5.376328e-02 0.000000e+00| 0:0:04| chol 6 7
45|1.000|0.648|2.0e-09|1.3e-08|2.6e-02| 1.620949e-02 0.000000e+00| 0:0:04| chol 8 16
46|1.000|0.470|8.7e-10|1.4e-08|4.4e-03| 2.456181e-03 0.000000e+00| 0:0:05| chol 24 14
47|1.000|0.684|2.8e-10|3.0e-09|4.4e-04| 3.147500e-04 0.000000e+00| 0:0:05| chol
linsysolve: Schur complement matrix not positive definite
switch to LU factor. lu 30 ^ 6
48|0.762|0.776|1.4e-10|5.3e-10|1.0e-04| 8.556438e-05 0.000000e+00| 0:0:05| lu 30 ^12
49|0.957|0.790|1.3e-11|1.6e-10|6.0e-06| 4.810886e-06 0.000000e+00| 0:0:05| lu 11 ^20
50|0.264|0.307|3.7e-11|9.6e-11|4.2e-06| 3.699605e-06 0.000000e+00| 0:0:05| lu 30 ^ 9
51|0.733|0.917|1.4e-11|9.9e-11|1.2e-06| 1.046132e-06 0.000000e+00| 0:0:05| lu 11 30
52|0.156|0.127|2.0e-11|9.3e-11|9.9e-07| 9.030236e-07 0.000000e+00| 0:0:06| lu 30 ^ 7
53|0.252|0.941|1.6e-11|8.0e-11|7.5e-07| 6.704352e-07 0.000000e+00| 0:0:06| lu 13 ^28
54|0.303|0.490|1.5e-11|7.6e-11|5.2e-07| 4.695927e-07 0.000000e+00| 0:0:06| lu 30 ^11
55|0.041|0.147|1.4e-11|7.9e-11|4.9e-07| 4.547121e-07 0.000000e+00| 0:0:06| lu 30 ^25
56|0.023|0.053|1.4e-11|5.9e-11|4.8e-07| 4.476404e-07 0.000000e+00| 0:0:06|
stop: steps too short consecutively

number of iterations = 56
primal objective value = 4.47640419e-07
dual objective value = 0.00000000e+00
gap := trace(XZ) = 4.77e-07
relative gap = 4.77e-07
actual relative gap = 4.48e-07
rel. primal infeas (scaled problem) = 1.44e-11
rel. dual " " " = 5.94e-11
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.3e-03, 2.0e+06, 2.9e+10
norm(A), norm(b), norm© = 6.6e+05, 1.0e+00, 5.3e+04
Total CPU time (secs) = 6.34
CPU time per iteration = 0.11
termination code = -5
DIMACS: 1.4e-11 0.0e+00 2.0e-10 0.0e+00 4.5e-07 4.8e-07

Status: Inaccurate/Solved
Optimal value (cvx_optval): -4.4764e-07

while my “failed” output (max iterations is reached, but clearly this solution does not seem like it’s going anywhere) is

``````Calling SDPT3 4.0: 1189 variables, 553 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 553
dim. of sdp    var  = 63,   num. of sdp  blk  =  2
dim. of linear var  =  1
dim. of free   var  = 108  convert ublk to lblk
number of nearly dependent constraints = 39
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 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|6.0e+09|6.8e+08|3.3e+11| 2.423149e+02  0.000000e+00| 0:0:00| spchol  1  2
1|0.000|0.003|6.0e+09|6.7e+08|3.7e+11| 2.423150e+02  1.659480e+01| 0:0:00| chol  2  2
2|0.005|0.000|6.0e+09|6.7e+08|3.7e+11| 2.424527e+02  2.057097e+01| 0:0:00| chol  2  2
3|0.005|0.002|6.0e+09|6.7e+08|3.7e+11| 2.426283e+02  3.719155e+01| 0:0:01| chol  2  2
4|0.009|0.003|5.9e+09|6.7e+08|3.7e+11| 2.428799e+02  5.987569e+01| 0:0:01| chol  2  2
5|0.019|0.005|5.8e+09|6.7e+08|3.7e+11| 2.433303e+02  9.496288e+01| 0:0:01| chol  2  2
6|0.025|0.009|5.6e+09|6.6e+08|3.6e+11| 2.438916e+02  1.552193e+02| 0:0:01| chol  2  2
7|0.055|0.012|5.3e+09|6.5e+08|3.5e+11| 2.450676e+02  2.367309e+02| 0:0:01| chol  2  2
8|0.059|0.026|5.0e+09|6.4e+08|3.4e+11| 2.462430e+02  4.001487e+02| 0:0:01| chol  2  2
9|0.142|0.031|4.3e+09|6.2e+08|3.2e+11| 2.488394e+02  5.864318e+02| 0:0:01| chol  2  2
10|0.144|0.069|3.7e+09|5.7e+08|3.0e+11| 2.510827e+02  9.888177e+02| 0:0:01| chol  2  2
11|0.306|0.077|2.6e+09|5.3e+08|2.6e+11| 2.552522e+02  1.415330e+03| 0:0:01| chol  2  2
12|0.301|0.158|1.8e+09|4.5e+08|2.1e+11| 2.583137e+02  2.282197e+03| 0:0:01| chol  2  2
13|0.500|0.165|8.9e+08|3.7e+08|1.7e+11| 2.624732e+02  3.169173e+03| 0:0:01| chol  2  2
14|0.260|0.208|6.6e+08|2.9e+08|1.3e+11| 2.646442e+02  4.822779e+03| 0:0:02| chol  2  2
15|0.472|0.152|3.5e+08|2.5e+08|1.1e+11| 2.689140e+02  5.989161e+03| 0:0:02| chol  2  2
16|0.464|0.183|1.9e+08|2.0e+08|8.5e+10| 2.742777e+02  8.203634e+03| 0:0:02| chol  2  2
17|0.560|0.190|8.2e+07|1.7e+08|6.7e+10| 2.820396e+02  1.165743e+04| 0:0:02| chol  2  3
18|0.500|0.224|4.1e+07|1.3e+08|5.1e+10| 2.897046e+02  1.856580e+04| 0:0:02| chol  3  3
19|0.592|0.239|1.7e+07|9.8e+07|3.8e+10| 2.966113e+02  2.802781e+04| 0:0:02| chol  3  3
20|0.602|0.190|6.7e+06|7.9e+07|3.1e+10| 3.073468e+02  4.497793e+04| 0:0:02| chol  3  3
21|0.384|0.271|4.1e+06|5.8e+07|2.3e+10| 3.118560e+02  8.065350e+04| 0:0:02| chol  3  3
22|0.594|0.189|1.7e+06|4.7e+07|1.8e+10| 3.191279e+02  1.069797e+05| 0:0:02| chol  3  3
23|0.428|0.218|9.6e+05|3.7e+07|1.4e+10| 3.246658e+02  1.588358e+05| 0:0:02| chol  3  3
24|0.676|0.200|3.1e+05|2.9e+07|1.1e+10| 3.319454e+02  2.044433e+05| 0:0:02| chol  4  4
25|0.515|0.252|1.5e+05|2.2e+07|8.6e+09| 3.370143e+02  2.850127e+05| 0:0:03| chol  4  4
26|0.721|0.243|4.2e+04|1.7e+07|6.5e+09| 3.430621e+02  3.318820e+05| 0:0:03| chol  4  5
27|0.525|0.234|2.0e+04|1.3e+07|5.0e+09| 3.477637e+02  4.028679e+05| 0:0:03| chol  5  7
28|0.680|0.370|6.4e+03|8.0e+06|3.2e+09| 3.512639e+02  3.418697e+05| 0:0:03| chol  8  7
29|0.429|0.204|3.7e+03|6.4e+06|2.5e+09| 3.543498e+02  3.250129e+05| 0:0:03| chol  9  9
30|0.622|0.334|1.4e+03|4.2e+06|1.7e+09| 3.566896e+02  2.466601e+05| 0:0:03| chol  7  9
31|0.823|0.550|2.4e+02|1.9e+06|7.6e+08| 3.578368e+02  1.194213e+05| 0:0:03| chol  8  9
32|0.244|0.068|1.8e+02|1.8e+06|7.2e+08| 3.594876e+02  1.124025e+05| 0:0:03| chol 16 30
33|0.170|0.109|1.5e+02|1.6e+06|6.4e+08| 3.614413e+02  1.030113e+05| 0:0:03| chol 10 15
34|0.255|0.111|1.1e+02|1.4e+06|5.8e+08| 3.648751e+02  9.709624e+04| 0:0:04| chol 27 22
35|0.319|0.155|7.8e+01|1.2e+06|5.0e+08| 3.693212e+02  9.016650e+04| 0:0:04| chol 26 30
36|0.548|0.314|3.5e+01|8.2e+05|3.4e+08| 3.731507e+02  6.801166e+04| 0:0:04| chol 23 17
37|0.742|0.421|9.1e+00|4.7e+05|2.0e+08| 3.755223e+02  4.058459e+04| 0:0:04| chol 26 30
38|0.191|0.054|7.3e+00|4.5e+05|1.9e+08| 3.792542e+02  3.694062e+04| 0:0:04| chol
warning: symqmr failed: 0.3
switch to LU factor. lu 16 ^12
39|0.047|0.075|7.0e+00|4.1e+05|1.8e+08| 3.828099e+02  2.906123e+04| 0:0:05| lu 23   4
40|0.242|0.075|5.3e+00|3.8e+05|1.7e+08| 3.898972e+02  2.652113e+04| 0:0:05| lu 11 ^11
41|0.015|0.026|5.2e+00|3.7e+05|1.6e+08| 3.913053e+02  2.619236e+04| 0:0:05| lu 30   3
42|0.199|0.177|4.2e+00|3.1e+05|1.4e+08| 3.964083e+02  2.276090e+04| 0:0:05| lu 29   2
43|0.416|0.137|2.4e+00|2.6e+05|1.2e+08| 4.044833e+02  2.031385e+04| 0:0:05| lu 11 ^ 6
44|0.136|0.072|2.1e+00|2.4e+05|1.2e+08| 4.197357e+02  1.915583e+04| 0:0:05| lu 24   9
45|0.391|0.150|1.3e+00|2.1e+05|1.0e+08| 4.327931e+02  1.714880e+04| 0:0:06| lu 29 ^ 9
46|0.101|0.153|1.2e+00|1.8e+05|8.8e+07| 4.380963e+02  1.548094e+04| 0:0:06| lu 30   4
47|0.913|0.438|1.0e-01|9.9e+04|4.9e+07| 4.415107e+02  8.961268e+03| 0:0:06| lu 30 ^ 7
48|0.770|0.493|2.3e-02|5.0e+04|2.5e+07| 4.437505e+02  4.611701e+03| 0:0:06| lu 26   3
49|0.545|0.250|1.0e-02|3.8e+04|1.9e+07| 4.464402e+02  3.490966e+03| 0:0:06| lu 16   2
50|0.461|0.204|5.7e-03|3.0e+04|1.5e+07| 4.491277e+02  2.799732e+03| 0:0:06| lu 14   9
51|0.085|0.037|5.2e-03|2.9e+04|1.4e+07| 4.518062e+02  2.714234e+03| 0:0:06| lu 30 ^20
52|0.282|0.091|3.7e-03|2.6e+04|1.4e+07| 4.595576e+02  2.499970e+03| 0:0:07| lu 30   7
53|0.480|0.338|1.9e-03|1.7e+04|9.1e+06| 4.666230e+02  1.711938e+03| 0:0:07| lu 30 ^14
54|0.301|0.290|1.3e-03|1.2e+04|6.4e+06| 4.697803e+02  1.234262e+03| 0:0:07| lu 19  30
55|0.067|0.054|1.3e-03|1.2e+04|6.1e+06| 4.721202e+02  1.177245e+03| 0:0:07| lu 16 ^20
56|0.004|0.027|1.2e-03|1.1e+04|5.9e+06| 4.726883e+02  1.157589e+03| 0:0:07| lu 15 ^16
57|0.049|0.025|1.2e-03|1.1e+04|5.8e+06| 4.739063e+02  1.135323e+03| 0:0:08| lu 30 ^11
58|0.003|0.007|1.2e-03|1.1e+04|5.7e+06| 4.744258e+02  1.127028e+03| 0:0:08| lu 29 ^ 4
59|0.053|0.015|1.1e-03|1.1e+04|5.7e+06| 4.791484e+02  1.116769e+03| 0:0:08| lu 30 ^25
60|0.077|0.055|1.0e-03|1.0e+04|5.5e+06| 4.821503e+02  1.066436e+03| 0:0:08| lu 20 ^13
61|0.181|0.060|8.4e-04|9.6e+03|5.3e+06| 4.881858e+02  1.013101e+03| 0:0:08| lu 14 ^26
62|0.085|0.047|7.7e-04|9.2e+03|5.1e+06| 4.995017e+02  9.603902e+02| 0:0:08| lu 12 ^27
63|0.223|0.080|6.0e-04|8.4e+03|4.9e+06| 5.121407e+02  8.995951e+02| 0:0:09| lu 29 ^26
64|0.169|0.140|5.0e-04|7.2e+03|4.3e+06| 5.185124e+02  7.931493e+02| 0:0:09| lu 23 ^17
65|0.264|0.164|3.7e-04|6.1e+03|3.6e+06| 5.252965e+02  6.765466e+02| 0:0:09| lu 12 ^15
66|0.001|0.000|3.8e-04|6.1e+03|3.5e+06| 5.224010e+02  6.764318e+02| 0:0:09| lu 13 ^27
67|0.213|0.031|3.0e-04|5.9e+03|3.5e+06| 5.303777e+02  6.585829e+02| 0:0:09| lu 13  30
68|0.025|0.044|2.9e-04|5.6e+03|3.4e+06| 5.345164e+02  6.253092e+02| 0:0:10| lu 30 ^19
69|0.653|0.064|1.1e-04|5.3e+03|3.3e+06| 5.529126e+02  5.888591e+02| 0:0:10| lu 18 ^21
70|0.052|0.194|1.0e-04|4.2e+03|2.6e+06| 5.539418e+02  4.806528e+02| 0:0:10| lu 30 ^13
71|0.362|0.657|6.6e-05|1.5e+03|9.2e+05| 5.618554e+02  1.832996e+02| 0:0:10| lu 30 ^ 9
72|0.436|0.110|4.2e-05|1.3e+03|8.5e+05| 5.761440e+02  1.630264e+02| 0:0:10| lu 30 ^17
73|1.000|0.220|1.8e-05|1.0e+03|7.1e+05| 6.143265e+02  1.269609e+02| 0:0:11| lu 13 ^ 7
74|0.182|0.302|2.6e-05|7.0e+02|4.9e+05| 6.207686e+02  9.130247e+01| 0:0:11| lu 20 ^17
75|0.521|0.077|3.1e-05|6.5e+02|5.0e+05| 6.639450e+02  8.445973e+01| 0:0:11| lu 30 ^21
76|0.431|0.397|2.3e-05|3.9e+02|3.0e+05| 6.886484e+02  5.004532e+01| 0:0:11| lu 30 ^10
77|0.129|0.126|4.2e-05|3.4e+02|2.7e+05| 7.083385e+02  4.388693e+01| 0:0:11| lu 16 ^ 9
78|0.306|0.113|1.5e-04|3.0e+02|2.7e+05| 7.952529e+02  3.754628e+01| 0:0:11| lu 15 ^18
79|0.208|0.171|1.3e-04|2.5e+02|2.3e+05| 8.498406e+02  3.157560e+01| 0:0:12| lu 30 ^ 9
80|0.754|0.211|8.3e-05|2.0e+02|2.1e+05| 1.080097e+03  2.559976e+01| 0:0:12| lu 11 ^21
81|0.007|0.012|9.3e-05|2.0e+02|2.0e+05| 1.095066e+03  2.489633e+01| 0:0:12| lu 11  30
82|0.014|0.018|1.1e-04|1.9e+02|2.0e+05| 1.087018e+03  2.422377e+01| 0:0:12| lu 30  30
83|0.011|0.016|1.1e-04|1.9e+02|1.9e+05| 1.090931e+03  2.368975e+01| 0:0:12| lu 24 ^ 7
84|0.186|0.068|9.1e-05|1.8e+02|1.9e+05| 1.107635e+03  2.224791e+01| 0:0:12| lu 30 ^23
85|0.140|0.080|8.5e-05|1.6e+02|1.9e+05| 1.225802e+03  1.967137e+01| 0:0:13| lu 11 ^26
86|0.029|0.018|1.8e-04|1.6e+02|1.9e+05| 1.333295e+03  1.902119e+01| 0:0:13| lu 22   3
87|0.067|0.051|1.7e-04|1.5e+02|1.9e+05| 1.372725e+03  1.817243e+01| 0:0:13| lu 16 ^27
88|0.103|0.037|2.1e-04|1.5e+02|1.9e+05| 1.498051e+03  1.752079e+01| 0:0:13| lu 13   5
89|0.077|0.057|2.0e-04|1.4e+02|1.9e+05| 1.559574e+03  1.670763e+01| 0:0:13| lu 12  17
90|0.028|0.052|1.9e-04|1.3e+02|1.8e+05| 1.622699e+03  1.511166e+01| 0:0:13| lu 15 ^ 2
91|0.080|0.019|1.8e-04|1.3e+02|2.0e+05| 1.943100e+03  1.465045e+01| 0:0:13| lu 30  30
92|0.001|0.005|1.8e-04|1.3e+02|2.0e+05| 1.949925e+03  1.453110e+01| 0:0:14| lu  6   2
93|0.196|0.012|5.5e-04|1.3e+02|2.5e+05| 2.987855e+03  1.423957e+01| 0:0:14| lu 25   7
94|0.018|0.020|5.4e-04|1.2e+02|2.3e+05| 5.010329e+03  8.073147e+00| 0:0:14| lu 14   4
95|0.002|0.004|8.3e-04|1.2e+02|2.4e+05| 3.915040e+03  1.069076e+01| 0:0:14| lu  6   2
96|0.027|0.015|9.1e-04|1.2e+02|2.5e+05| 3.131346e+03  1.113281e+01| 0:0:14| lu  8   3
97|0.140|0.015|9.4e-04|1.2e+02|3.3e+05| 6.390254e+03  1.069399e+01| 0:0:14| lu 20  30
98|0.000|0.000|9.6e-04|1.2e+02|3.2e+05| 6.578451e+03  1.038703e+01| 0:0:15| lu  5   2
99|0.016|0.013|9.2e-04|1.2e+02|3.4e+05| 7.445174e+03  1.001145e+01| 0:0:15| lu  6   3
100|0.003|0.002|9.2e-04|1.2e+02|3.5e+05| 5.617423e+03  1.141895e+01| 0:0:15|
sqlp stop: maximum number of iterations reached
-------------------------------------------------------------------
number of iterations   = 100
primal objective value =  5.61742255e+03
dual   objective value =  1.14189522e+01
gap := trace(XZ)       = 3.46e+05
relative gap           = 6.14e+01
actual relative gap    = 9.96e-01
rel. primal infeas (scaled problem)   = 9.22e-04
rel. dual     "        "       "      = 1.18e+02
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual     "        "       "      = 0.00e+00
norm(X), norm(y), norm(Z) = 4.3e+04, 4.7e+11, 3.0e+16
norm(A), norm(b), norm(C) = 5.3e+08, 2.0e+00, 4.9e+00
Total CPU time (secs)  = 14.88
CPU time per iteration = 0.15
termination code       = -6
DIMACS: 9.2e-04  0.0e+00  2.9e+02  0.0e+00  1.0e+00  6.1e+01

Status: Failed
Optimal value (cvx_optval): NaN``````

(Mark L. Stone) #2

You haven’t provided the input data. Therefore this is not reproducible by forum readers.

You can try another solver, such as SeDuMi, and if you have access to it, better yet, Mosek.

The SDPT3 output gives a clue.

number of nearly dependent constraints = 39
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 1.

You can do this by adding the following line to your program:
`cvx_solver_settings('rmdepconstr',1)`

The primal-dual path-following algorithm we implemented assumes that A has full column rank. But in our software, the presence of (nearly) dependent constraints is detected automatically, and warning messages are displayed if such constraints exist. When this happens, the user has the option of removing these (nearly) dependent constraints by calling a preprocessing routine to remove them by setting OPTIONS.rmdepconstr = 1. We should mention that the routine we have coded for removing dependent constraints is a rather primitive one, and it is inefficient for large problems. We hope to improve on this routine in future versions of SDPT3.

Perhaps you can also examine why there are nearly dependent constraints, and whether you can improve your model formulation to avoid that.