Figure 8.16: Quadratic placement problem
linewidth = 1;
markersize = 5;
fixed = [ 1 1 -1 -1 1 -1 -0.2 0.1;
1 -1 -1 1 -0.5 -0.2 -1 1]';
M = size(fixed,1);
N = 6;
A = [ 1 0 0 -1 0 0 0 0 0 0 0 0 0 0
1 0 -1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 -1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 -1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 -1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 -1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 1 -1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 -1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 -1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 -1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 -1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 -1 0
0 0 1 -1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 -1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 1 -1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 -1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 -1 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 -1 0 0
0 0 0 1 0 -1 0 0 0 0 0 -1 0 0
0 0 0 0 1 -1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 -1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 -1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 1 0 0 -1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 -1 0 0 0 ];
nolinks = size(A,1);
fprintf(1,'Computing the optimal locations of the 6 free points...');
cvx_begin
variable x(N+M,2)
minimize ( sum(square_pos(norms( A*x,2,2 ))))
x(N+[1:M],:) == fixed;
cvx_end
fprintf(1,'Done! \n');
free_sum = x(1:N,:);
figure(1);
dots = plot(free_sum(:,1), free_sum(:,2), 'or', fixed(:,1), fixed(:,2), 'bs');
set(dots(1),'MarkerFaceColor','red');
hold on
legend('Free points','Fixed points','Location','Best');
for i=1:nolinks
ind = find(A(i,:));
line2 = plot(x(ind,1), x(ind,2), ':k');
hold on
set(line2,'LineWidth',linewidth);
end
axis([-1.1 1.1 -1.1 1.1]) ;
axis equal;
title('Quadratic placement problem');
figure(2)
all = [free_sum; fixed];
bins = 0.05:0.1:1.95;
lengths = sqrt(sum((A*all).^2')');
[N2,hist2] = hist(lengths,bins);
bar(hist2,N2);
hold on;
xx = linspace(0,2,1000); yy = (4/1.5^2)*xx.^2;
plot(xx,yy,'--');
axis([0 1.5 0 4.5]);
hold on
plot([0 2], [0 0 ], 'k-');
title('Distribution of the 27 link lengths');
Computing the optimal locations of the 6 free points...
Calling SDPT3: 189 variables, 93 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 93
dim. of sdp var = 54, num. of sdp blk = 27
dim. of socp var = 81, num. of socp blk = 27
dim. of linear var = 27
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|7.0e+00|5.4e+00|2.6e+03| 5.400000e+01| 0:0:00| chol 1 1
1|0.847|0.818|1.1e+00|1.0e+00|5.9e+02| 7.188534e+00| 0:0:00| chol 1 1
2|0.918|1.000|8.7e-02|1.0e-02|1.3e+02|-3.512319e+01| 0:0:00| chol 1 1
3|0.981|0.969|1.7e-03|1.6e-02|2.2e+01|-2.471586e+01| 0:0:00| chol 1 1
4|1.000|1.000|1.5e-07|4.4e-04|5.3e+00|-2.109922e+01| 0:0:00| chol 1 1
5|0.938|0.948|1.5e-08|3.2e-05|4.1e-01|-2.058998e+01| 0:0:00| chol 1 1
6|0.980|0.979|2.9e-09|1.7e-06|1.1e-02|-2.054862e+01| 0:0:00| chol 1 1
7|0.986|0.987|5.8e-10|1.2e-07|1.5e-04|-2.054732e+01| 0:0:00| chol 1 1
8|1.000|0.998|4.3e-11|3.0e-10|3.2e-06|-2.054731e+01| 0:0:00| chol 1 1
9|1.000|1.000|1.2e-11|8.5e-12|9.7e-08|-2.054731e+01| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 9
primal objective value = -2.05473136e+01
dual objective value = -2.05473137e+01
gap := trace(XZ) = 9.69e-08
relative gap = 2.30e-09
actual relative gap = 2.29e-09
rel. primal infeas = 1.21e-11
rel. dual infeas = 8.54e-12
norm(X), norm(y), norm(Z) = 1.8e+01, 6.6e+00, 1.1e+01
norm(A), norm(b), norm(C) = 1.6e+01, 6.2e+00, 8.5e+00
Total CPU time (secs) = 0.4
CPU time per iteration = 0.0
termination code = 0
DIMACS: 3.8e-11 0.0e+00 3.6e-11 0.0e+00 2.3e-09 2.3e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +20.5473
Done!