Figure 8.10: Approximate linear discrimination via linear programming
n = 2;
randn('state',2);
N = 50; M = 50;
Y = [1.5+0.9*randn(1,0.6*N), 1.5+0.7*randn(1,0.4*N);
2*(randn(1,0.6*N)+1), 2*(randn(1,0.4*N)-1)];
X = [-1.5+0.9*randn(1,0.6*M), -1.5+0.7*randn(1,0.4*M);
2*(randn(1,0.6*M)-1), 2*(randn(1,0.4*M)+1)];
T = [-1 1; 1 1];
Y = T*Y; X = T*X;
cvx_begin
variables a(n) b(1) u(N) v(M)
minimize (ones(1,N)*u + ones(1,M)*v)
X'*a - b >= 1 - u;
Y'*a - b <= -(1 - v);
u >= 0;
v >= 0;
cvx_end
linewidth = 0.5;
t_min = min([X(1,:),Y(1,:)]);
t_max = max([X(1,:),Y(1,:)]);
tt = linspace(t_min-1,t_max+1,100);
p = -a(1)*tt/a(2) + b/a(2);
p1 = -a(1)*tt/a(2) + (b+1)/a(2);
p2 = -a(1)*tt/a(2) + (b-1)/a(2);
graph = plot(X(1,:),X(2,:), 'o', Y(1,:), Y(2,:), 'o');
set(graph(1),'LineWidth',linewidth);
set(graph(2),'LineWidth',linewidth);
set(graph(2),'MarkerFaceColor',[0 0.5 0]);
hold on;
plot(tt,p, '-r', tt,p1, '--r', tt,p2, '--r');
axis equal
title('Approximate linear discrimination via linear programming');
Calling SDPT3: 203 variables, 100 equality constraints
------------------------------------------------------------
num. of constraints = 100
dim. of linear var = 200
dim. of free var = 3 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|9.1e-01|1.9e+01|4.1e+04| 7.071068e+02| 0:0:00| chol 1 1
1|1.000|0.968|1.2e-06|7.1e-01|2.6e+03| 6.263880e+02| 0:0:00| chol 1 1
2|1.000|0.567|2.7e-06|3.1e-01|1.0e+03| 2.282174e+02| 0:0:00| chol 1 1
3|0.910|0.846|1.6e-06|4.9e-02|1.4e+02| 3.699538e+01| 0:0:00| chol 1 1
4|0.940|0.640|6.2e-06|1.8e-02|6.3e+01| 1.877971e+01| 0:0:00| chol 1 1
5|0.982|0.439|6.7e-07|1.0e-02|2.8e+01| 8.953107e+00| 0:0:00| chol 1 1
6|1.000|0.754|7.9e-09|2.5e-03|1.1e+01| 7.598315e+00| 0:0:00| chol 1 1
7|1.000|0.241|5.0e-08|1.9e-03|8.2e+00| 6.953476e+00| 0:0:00| chol 1 1
8|1.000|0.587|1.5e-07|7.7e-04|5.0e+00| 6.947877e+00| 0:0:00| chol 1 1
9|0.921|0.455|8.2e-08|4.2e-04|2.4e+00| 6.243383e+00| 0:0:00| chol 1 1
10|1.000|0.524|2.6e-08|2.0e-04|1.4e+00| 6.199969e+00| 0:0:00| chol 1 1
11|1.000|0.299|1.3e-08|1.4e-04|1.0e+00| 6.141284e+00| 0:0:00| chol 1 1
12|1.000|0.516|5.4e-09|6.8e-05|6.2e-01| 6.160736e+00| 0:0:00| chol 1 1
13|0.755|0.303|2.3e-09|4.7e-05|4.0e-01| 6.105780e+00| 0:0:00| chol 1 1
14|1.000|0.303|9.4e-10|3.3e-05|4.1e-01| 6.184521e+00| 0:0:00| chol 1 1
15|0.983|0.306|1.1e-09|2.3e-05|2.4e-01| 6.130887e+00| 0:0:00| chol 1 1
16|1.000|0.679|1.3e-09|7.3e-06|7.8e-02| 6.132246e+00| 0:0:00| chol 1 1
17|0.993|0.899|1.1e-10|7.4e-07|6.7e-03| 6.146065e+00| 0:0:00| chol 1 1
18|0.987|0.986|6.7e-11|3.1e-06|1.4e-04| 6.148535e+00| 0:0:01| chol 1 1
19|0.996|0.989|1.2e-13|6.5e-08|3.5e-06| 6.148569e+00| 0:0:01| chol 1 1
20|1.000|0.989|7.0e-14|1.6e-09|7.9e-08| 6.148569e+00| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 20
primal objective value = 6.14856945e+00
dual objective value = 6.14856940e+00
gap := trace(XZ) = 7.91e-08
relative gap = 5.95e-09
actual relative gap = 4.14e-09
rel. primal infeas = 6.98e-14
rel. dual infeas = 1.60e-09
norm(X), norm(y), norm(Z) = 8.9e+01, 2.4e+00, 1.0e+01
norm(A), norm(b), norm(C) = 7.3e+01, 1.1e+01, 1.1e+01
Total CPU time (secs) = 0.6
CPU time per iteration = 0.0
termination code = 0
DIMACS: 3.8e-13 0.0e+00 8.8e-09 0.0e+00 4.1e-09 5.9e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +6.14857