use cvx to solve SDP,Why is this a problem?


#1

Untitled
警告: This linear matrix inequality appears to be unsymmetric. This is
very likely an error that will produce unexpected results. Please check
the LMI; and, if necessary, re-enter the model.
In cvxprob.newcnstr at 241
In cvx.ge at 21
In Untitled at 62

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

num. of constraints = 8
dim. of sdp var = 8, num. of sdp blk = 2


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|5.1e+00|1.1e+01|5.2e+09| 1.300537e+08 0.000000e+00| 0:0:00| chol 1 1
1|0.897|1.000|5.2e-01|5.0e-01|4.9e+08| 1.113261e+08 1.068415e+08| 0:0:00| chol 1 1
2|0.651|0.807|1.8e-01|3.0e-01|1.4e+08| 1.426745e+08 3.074225e+08| 0:0:00| chol 1 1
3|0.395|0.409|1.1e-01|2.3e-01|9.7e+07| 2.205289e+08 4.619816e+08| 0:0:00| chol 1 1
4|0.383|0.113|6.8e-02|2.1e-01|8.9e+07| 3.515606e+08 6.108415e+08| 0:0:00| chol 1 1
5|0.206|0.076|5.4e-02|2.0e-01|1.0e+08| 4.540972e+08 7.874405e+08| 0:0:00| chol 1 1
6|0.084|0.056|5.0e-02|1.9e-01|1.0e+08| 4.925811e+08 9.748567e+08| 0:0:00| chol 1 1
7|0.207|0.092|3.9e-02|1.7e-01|9.9e+07| 5.955075e+08 1.131456e+09| 0:0:00| chol 1 1
8|0.207|0.100|3.1e-02|1.5e-01|8.4e+07| 7.047698e+08 1.305316e+09| 0:0:00| chol 1 1
9|0.171|0.059|2.6e-02|1.4e-01|9.6e+07| 8.353288e+08 1.512334e+09| 0:0:00| chol 1 2
10|0.170|0.060|2.1e-02|1.3e-01|1.0e+08| 9.620352e+08 1.684198e+09| 0:0:00| chol 1 2
11|0.132|0.058|1.9e-02|1.3e-01|1.0e+08| 1.073879e+09 1.907863e+09| 0:0:00| chol 1 1
12|0.204|0.074|1.5e-02|1.2e-01|1.0e+08| 1.252735e+09 2.094768e+09| 0:0:00| chol 1 1
13|0.140|0.059|1.3e-02|1.1e-01|1.1e+08| 1.397099e+09 2.352208e+09| 0:0:01| chol 1 1
14|0.211|0.072|1.0e-02|1.0e-01|1.2e+08| 1.614260e+09 2.548117e+09| 0:0:01| chol 1 1
15|0.146|0.066|8.6e-03|9.6e-02|1.2e+08| 1.777852e+09 2.815251e+09| 0:0:01| chol 1 1
16|0.241|0.086|6.5e-03|8.9e-02|1.3e+08| 2.046264e+09 3.011185e+09| 0:0:01| chol 1 1
17|0.165|0.074|5.5e-03|8.4e-02|1.5e+08| 2.259235e+09 3.305741e+09| 0:0:01| chol 1 1
18|0.330|0.156|3.7e-03|7.2e-02|1.6e+08| 2.629651e+09 3.495027e+09| 0:0:01| chol 1 1
19|0.276|0.149|2.6e-03|6.2e-02|1.6e+08| 2.928506e+09 3.755120e+09| 0:0:01| chol 1 1
20|0.471|0.252|1.4e-03|4.7e-02|1.5e+08| 3.352425e+09 3.883119e+09| 0:0:01| chol 1 1
21|0.518|0.259|6.8e-04|3.5e-02|1.2e+08| 3.693610e+09 4.011403e+09| 0:0:01| chol 1 1
22|0.769|0.435|1.6e-04|2.0e-02|8.1e+07| 3.958039e+09 4.033427e+09| 0:0:01| chol 1 1
23|1.000|0.683|3.0e-13|6.4e-03|3.1e+07| 4.047669e+09 4.039136e+09| 0:0:01| chol 1 1
24|0.966|0.979|8.8e-15|1.4e-04|7.3e+05| 4.042943e+09 4.042686e+09| 0:0:01| chol 1 1
25|0.899|0.935|3.5e-14|8.9e-06|5.7e+04| 4.042850e+09 4.042823e+09| 0:0:01| chol 2 2
26|1.000|0.955|2.9e-13|4.0e-07|4.4e+03| 4.042847e+09 4.042844e+09| 0:0:01| chol 2 1
27|0.982|0.979|4.4e-13|8.5e-09|9.2e+01| 4.042846e+09 4.042846e+09| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08
prim_inf,dual_inf,relgap = 4.38e-13, 8.49e-09, 1.13e-08
sqlp stop: primal problem is suspected of being infeasible

number of iterations = 27
residual of primal infeasibility
certificate (y,Z) = 3.50e-10
reldist to infeas. <= 1.38e-05
Total CPU time (secs) = 0.61
CPU time per iteration = 0.02
termination code = 1
DIMACS: 5.8e-13 0.0e+00 1.0e-08 0.0e+00 7.7e-09 1.1e-08


Status: Unbounded
Optimal value (cvx_optval): -Inf


(Mark L. Stone) #2

Please show us your code, preferably with input data.


#3
%无线网络节点坐标
s1=[0,0];   %参考节点
s2=[260,150];
s3=[0,300];
s4=[-260,150];
s5=[200,-150];
s=[s1;s2;s3;s4;s5];
%目标节点
u=[50,100];

%生成TDOA测量值
d=zeros(1,5);
for i=1:5
d(i)=norm((u-s(i,:)));
end

tdoa=zeros(1,4);
for i=1:4
tdoa(i)=(d(i+1)-d(1))+3*randn(1,1);
end
%生成AOA测量值
thta=zeros(1,5);
for i=1:5
thta(i)=atan((u(2)-s(i,2))/(u(1)-s(i,1)))+randn(1,1);
end
%G矩阵
G1=[];
G2=[];
for i=1:4
g1=[s(i+1,1)-s(1,1),s(i+1,2)-s(1,2),tdoa(i)];
G1=[G1;g1];
end
for i=1:5
g2=[sin(thta(i)),-cos(thta(i)),0];
G2=[G2;g2];
end

G=[G1;G2];
%h矩阵
h1=[];
h2=[];
for i=1:4
h11=1/2*[(s(i+1,1)-s(1,1)).^2+(s(i+1,2)-s(1,2)).^2-(tdoa(i)).^2];
h1=[h1;h11];
end
h2=[0];
for i=1:4
h22=[(s(i+1,1)-s(1,1))*sin(thta(i+1))-(s(i+1,2)-s(1,2))*cos(thta(i+1))];
h2=[h2;h22]; %行扩展
end
h=[h1;h2];
W=eye(9);
n=4;
C=[G'*inv(W)*G,-G'*inv(W)*h;-h'*inv(W)*G,h'*inv(W)*h];
K=diag([1,1,-1,0]);
cvx_begin sdp
variables Z(3,3) z(3,1) 
minimize(trace(C*[Z z;z.' 1]));
subject to
trace(K*[Z z;z' 1]) == 0;
[Z z;z' 1] == semidefinite(4);
[Z z;z' 1]>=0;
cvx_end

(Mark L. Stone) #4

The warning message
This linear matrix inequality appears to be unsymmetric.
is because you didn’t declare Z to be symmetric.

However, after making that correction
variable Z(3,3) symmetric
it is still the case that the problem is unbounded.

Also note that your inclusion of both
[Z z;z' 1] == semidefinite(4);
and
[Z z;z' 1]>=0;
is redundant. Both of these constraints are the same given that you have invoked sdp mode. However your inclusion of both doesn’tt seem to do any harm, and the result is the same if one of these code lines is removed.

I think your problem is assessed by the solver as unbounded because C is very poorly scaled. I changed the objective to
minimize(trace(1e-8*C*[Z z;z.' 1]));
and got an optimal solution.


(Mark L. Stone) #5

>> disp(C)

   1.0e+09 *

   0.000175203062655  -0.000029999623029   0.000013132054229  -0.006438738509987
  -0.000029999623029   0.000157501937345   0.000047772408445  -0.019623581791272
   0.000013132054229   0.000047772408445   0.000092574956830  -0.015905590544226
  -0.006438738509987  -0.019623581791272  -0.015905590544226   4.046452272095730