Is it possible to obtain a local extreme when using sdpt3?

1

I am trying to solve my sdp problem with cvx. To check my answer obtaining from cvx, I use lots of known results. For the table, n = 8 and all d less or equal to n are correct. Also, for n <= 20 and d <= 2, d = n are correct. But for n >= 9, d around n/2, I get an incorrect answer. For the case n > 13, I get status fail. Here is my code.
cvx_clear
cvx_begin sdp
cvx_solver sdpt3
variable x(n+1, n+1, n+1) nonnegative symmetric;
tar = 0;
a = [];
b = [];
%%definition condition
b = [b x(1, 1, 1) == 1];
%{
for i = 0: n
for j = i: n
for t = 0: n
if triple_comb(n, i-t, j-t, t) == 0
b = [b x(i+1, j+1, t+1) == 0];
end
end
end
end
%}

for i = 0: n
    tar = tar + comb(n,i)*x(i+1, 1, 1);
end
for k = 0: floor(n/2)
    [matrix_1, matrix_2] = genetate(x, n, k);
    a = [a matrix_1 == semidefinite(n-2*k+1)];
    a = [a matrix_2 == semidefinite(n-2*k+1)];
end
for i = 0: n
    disp(i);
    for j = i: n
        for t = 0: n

%% distance
if d >= 2
index = 1:d-1;
if ismember(i, index) || ismember(i + j -2*t, index)
b = [b (x(i+1, j+1, t+1) == 0)];
end
end
%%condition2

            %if j ~- 0 && t ~= 0
                    %b = [b (x(i+1, j+1, t+1) - x(i+1, 1, 1) <= 0)];
            %end;
            %b = [b (1 + x(i+1, j+1, t+1) - x(i+1, 1, 1) - x(j+1, 1, 1) >= 0)];

%%permutation

             for m = 0: n
                 for l = m: n
                     for k = 0: n
                         if per(i, j, t, m, l, k)
                             b = [b (x(i+1, j+1, k+1) == x(m+1, l+1, k+1))];
                         end
                     end
                 end
             end
        end
    end
end

maximize(tar)
subject to
    a
    b

cvx_end

When I get fail, this is an output.
Calling SDPT3 4.0: 8543 variables, 1307 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 1307
dim. of sdp var = 620, num. of sdp blk = 40
dim. of free var = 2693 *** convert ublk to lblk

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|2.9e+09|1.8e+10|5.3e+15| 9.822752e-05 0.000000e+00| 0:0:00| spchol 2 2
1|0.000|0.000|2.9e+09|1.8e+10|5.3e+15| 5.224288e+06 6.604612e+00| 0:0:00| chol 2 2
2|0.000|0.000|2.9e+09|1.8e+10|5.3e+15| 9.107597e+06 6.009881e+01| 0:0:00| chol 2 2
3|0.001|0.000|2.9e+09|1.8e+10|5.3e+15| 6.716106e+07 2.035227e+02| 0:0:01| chol 2 2
4|0.000|0.001|2.9e+09|1.8e+10|5.3e+15| 1.024894e+08 1.893112e+03| 0:0:01|
*** Too many tiny steps: restarting with the following iterate.
*** [X,y,Z] = infeaspt(blk,At,C,b,2,1e5); spchol * 7 * 7
5|0.644|0.814|3.4e+09|6.0e+05|3.9e+12| 1.062009e+01 2.424941e+00| 0:0:01| chol * 5 * 5
6|0.782|0.925|7.3e+08|4.5e+04|2.5e+11| 4.850818e+01 3.231783e+00| 0:0:01| chol * 4 * 4
7|0.897|0.961|7.6e+07|1.8e+03|1.7e+10| 2.502935e+02 3.303799e+00| 0:0:01| chol 2 2
8|0.914|0.709|6.5e+06|5.1e+02|2.0e+09| 3.178932e+03 3.310131e+00| 0:0:01| chol 2 2
9|0.808|0.059|1.3e+06|4.9e+02|1.1e+09| 7.009246e+05 3.314997e+00| 0:0:01| chol 2 2
10|0.887|0.639|1.4e+05|1.8e+02|3.7e+08| 3.803116e+06 3.491204e+00| 0:0:01| chol 2 2
11|0.971|0.907|4.1e+03|1.6e+01|3.2e+07| 3.335380e+06 3.504863e+00| 0:0:02| chol 2 2
12|0.729|0.707|1.1e+03|4.8e+00|1.0e+07| 1.499548e+06 4.823097e+00| 0:0:02| chol 1 1
13|0.592|0.148|4.5e+02|5.2e+00|8.9e+06| 7.334299e+05 5.381954e+00| 0:0:02| chol 1 1
14|0.536|0.360|2.1e+02|3.4e+00|5.6e+06| 4.358467e+05 8.495145e+00| 0:0:02| chol 1 1
15|0.426|0.221|1.2e+02|2.6e+00|4.3e+06| 1.513958e+05 1.263680e+01| 0:0:02| chol 1 1
16|0.547|0.572|5.4e+01|1.1e+00|1.9e+06| 1.090365e+05 3.216632e+01| 0:0:02| chol 1 1
17|0.362|0.357|3.5e+01|7.2e-01|1.2e+06| 7.759803e+04 1.636918e+02| 0:0:02| chol 1 1
18|0.227|0.355|2.7e+01|4.6e-01|7.8e+05| 6.378481e+04 2.798617e+02| 0:0:03| chol 1 1
19|0.566|0.610|1.2e+01|1.8e-01|3.3e+05| 3.585003e+04 2.229041e+02| 0:0:03| chol 1 1
20|0.490|0.370|5.9e+00|1.1e-01|2.2e+05| 2.123992e+04 1.677861e+02| 0:0:03| chol 1 1
21|0.473|0.576|3.1e+00|4.8e-02|1.0e+05| 1.346310e+04 1.256575e+02| 0:0:03| chol 1 1
22|0.429|0.219|1.8e+00|3.8e-02|8.1e+04| 8.984756e+03 2.573884e+02| 0:0:03| chol 1 1
23|0.493|0.457|9.1e-01|2.1e-02|4.7e+04| 5.316286e+03 1.097317e+02| 0:0:03| chol 1 1
24|0.679|0.511|2.9e-01|1.0e-02|2.4e+04| 2.486378e+03 8.449894e+01| 0:0:03| chol 1 1
25|0.526|0.391|1.4e-01|6.1e-03|1.5e+04| 1.430206e+03 2.339892e+01| 0:0:03| chol 1 1
26|0.605|0.378|5.4e-02|3.8e-03|9.4e+03| 7.410126e+02 1.995129e+01| 0:0:04| chol 1 1
27|0.592|0.429|2.2e-02|2.4e-03|5.8e+03| 3.879251e+02 1.738059e+01| 0:0:04| chol 1 1
28|0.623|0.248|8.4e-03|1.9e-03|4.8e+03| 2.133878e+02 1.568826e+01| 0:0:04| chol 1 1
29|0.715|0.289|2.4e-03|1.5e-03|3.8e+03| 1.198053e+02 1.335281e+01| 0:0:04| chol 1 1
30|0.235|0.398|1.8e-03|9.9e-04|2.5e+03| 1.060285e+02 1.064353e+01| 0:0:04| chol 1 1
31|0.223|0.160|1.4e-03|1.2e-03|2.5e+03| 9.303003e+01 1.018606e+01| 0:0:04| chol 1 1
32|0.654|0.234|4.9e-04|9.6e-04|2.2e+03| 6.204456e+01 9.883194e+00| 0:0:04| chol 1 1
33|0.823|0.181|8.7e-05|1.1e-03|2.4e+03| 5.023026e+01 1.063667e+01| 0:0:04| chol 1 1
34|0.924|0.516|6.6e-06|5.4e-04|1.2e+03| 3.809272e+01 1.310330e+01| 0:0:05| chol 1 1
35|0.925|0.437|4.9e-07|3.1e-04|6.7e+02| 2.634302e+01 1.511427e+01| 0:0:05| chol 1 1
36|1.000|0.334|1.4e-10|2.0e-04|4.6e+02| 2.351770e+01 1.629903e+01| 0:0:05| chol 1 1
37|1.000|0.368|1.7e-10|1.3e-04|2.9e+02| 2.187267e+01 1.734958e+01| 0:0:05| chol 1 1
38|1.000|0.481|2.1e-10|6.7e-05|1.5e+02| 2.066598e+01 1.844811e+01| 0:0:05| chol 1 1
39|1.000|0.647|2.6e-10|2.4e-05|5.2e+01| 2.009967e+01 1.941085e+01| 0:0:05| chol 1 1
40|1.000|0.297|1.9e-10|1.7e-05|3.7e+01| 2.007541e+01 1.956852e+01| 0:0:05| chol 1 1
41|1.000|0.489|2.9e-10|8.5e-06|1.9e+01| 2.002497e+01 1.977051e+01| 0:0:05| chol 1 1
42|1.000|0.494|2.9e-10|4.3e-06|9.5e+00| 2.001028e+01 1.988058e+01| 0:0:06| chol 1 1
43|1.000|0.376|2.8e-10|2.7e-06|5.9e+00| 2.000501e+01 1.992443e+01| 0:0:06| chol 1 1
44|1.000|0.408|3.2e-10|1.6e-06|3.5e+00| 2.000349e+01 1.995444e+01| 0:0:06| chol 1 1
45|1.000|0.350|3.2e-10|1.1e-06|2.3e+00| 2.000184e+01 1.997007e+01| 0:0:06| chol 1 1
46|1.000|0.395|3.3e-10|6.5e-07|1.4e+00| 2.000115e+01 1.998166e+01| 0:0:06| chol 1 1
47|0.089|0.255|3.3e-10|5.0e-07|1.0e+00| 2.000114e+01 1.998618e+01| 0:0:06| chol 1 1
48|0.011|0.107|3.3e-10|4.5e-07|9.2e-01| 2.000115e+01 1.998757e+01| 0:0:06| chol 1 1
49|0.008|0.023|3.3e-10|4.4e-07|9.0e-01| 2.000115e+01 1.998783e+01| 0:0:07|
stop: steps too short consecutively

number of iterations = 49
primal objective value = 2.00011486e+01
dual objective value = 1.99878275e+01
gap := trace(XZ) = 9.03e-01
relative gap = 2.20e-02
actual relative gap = 3.25e-04
rel. primal infeas (scaled problem) = 3.30e-10
rel. dual " " " = 4.42e-07
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 5.1e+06, 1.3e+10, 1.3e+10
norm(A), norm(b), norm© = 3.1e+10, 1.9e+05, 2.4e+00
Total CPU time (secs) = 6.65
CPU time per iteration = 0.14
termination code = -5
DIMACS: 6.7e-10 0.0e+00 5.3e-07 0.0e+00 3.2e-04 2.2e-02

Status: Failed
Optimal value (cvx_optval): NaN

So, Is there anyone could help? I am wondering that cvx gave me a local maximum for some case because for those incorrect answer, they are all smaller than the correct one. For the failed case, I do not know how to solve this problem.

2

This shows

that A is most likely badly scaled. So you should work on the formulation.

You might also try another optimizer like Mosek and hope it works.

3

Thanks for replying. I will go to find some information about how to formulation or try to download Mosek free.

4

Can you explain what this code segment does?

for k = 0: floor(n/2)
    [matrix_1, matrix_2] = genetate(x, n, k);
    a = [a matrix_1 == semidefinite(n-2*k+1)];
    a = [a matrix_2 == semidefinite(n-2*k+1)];
end

I understand
a matrix_1 == semidefinite(n-2*k+1) .

I don’t understand
a = [a matrix_1 == semidefinite(n-2*k+1)];

5

This code is to add the condition matrix_1 == semidefinite(n-2*k+1) to the list a. As I define, a and b are two lists containing constraints. In here, a contains all semidefinite constraints and b contains others.