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 Mosek 9.1.9: 203 variables, 100 equality constraints
------------------------------------------------------------
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86
Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 100
Cones : 0
Scalar variables : 203
Matrix variables : 0
Integer variables : 0
Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 100
Cones : 0
Scalar variables : 203
Matrix variables : 0
Integer variables : 0
Optimizer - threads : 8
Optimizer - solved problem : the dual
Optimizer - Constraints : 3
Optimizer - Cones : 0
Optimizer - Scalar variables : 100 conic : 0
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 6 after factor : 6
Factor - dense dim. : 0 flops : 1.21e+03
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 4.0e+00 4.5e+01 2.0e+02 0.00e+00 0.000000000e+00 1.000000000e+02 4.0e+00 0.00
1 1.6e+00 1.8e+01 7.7e+01 1.00e+00 1.326796838e+01 5.217637579e+01 1.6e+00 0.01
2 3.4e-01 3.9e+00 1.7e+01 8.00e-01 1.276465396e+01 2.276054023e+01 3.4e-01 0.01
3 9.4e-02 1.1e+00 4.6e+00 7.29e-01 1.056871385e+01 1.373372432e+01 9.4e-02 0.01
4 5.7e-02 6.4e-01 2.8e+00 6.95e-01 9.981841488e+00 1.207699096e+01 5.7e-02 0.01
5 2.4e-02 2.7e-01 1.2e+00 5.28e-01 9.577353165e+00 1.084650474e+01 2.4e-02 0.01
6 1.5e-02 1.7e-01 7.4e-01 -2.38e-01 9.090838843e+00 1.021931758e+01 1.5e-02 0.01
7 7.1e-03 8.0e-02 3.5e-01 7.88e-01 7.843975801e+00 8.411374355e+00 7.1e-03 0.01
8 5.3e-03 6.0e-02 2.6e-01 3.60e-01 7.713726063e+00 8.230116821e+00 5.3e-03 0.01
9 4.2e-03 4.7e-02 2.1e-01 7.82e-01 7.375338663e+00 7.795080822e+00 4.2e-03 0.01
10 8.1e-04 9.2e-03 4.0e-02 9.81e-01 6.402420149e+00 6.483453549e+00 8.1e-04 0.01
11 6.0e-04 6.7e-03 2.9e-02 7.09e-01 6.352875466e+00 6.418381327e+00 6.0e-04 0.01
12 9.4e-05 1.1e-03 4.7e-03 9.89e-01 6.180539134e+00 6.190871435e+00 9.4e-05 0.01
13 3.8e-07 4.3e-06 1.9e-05 9.96e-01 6.148692445e+00 6.148734520e+00 3.8e-07 0.01
14 3.9e-11 4.4e-10 1.9e-09 1.00e+00 6.148569445e+00 6.148569449e+00 3.9e-11 0.01
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Optimizer terminated. Time: 0.02
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 6.1485694488e+00 nrm: 2e+01 Viol. con: 4e-11 var: 0e+00
Dual. obj: 6.1485694488e+00 nrm: 1e+00 Viol. con: 0e+00 var: 8e-09
Basic solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 6.1485694227e+00 nrm: 2e+01 Viol. con: 2e-08 var: 0e+00
Dual. obj: 6.1485694323e+00 nrm: 1e+00 Viol. con: 0e+00 var: 3e-15
Optimizer summary
Optimizer - time: 0.02
Interior-point - iterations : 14 time: 0.01
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +6.14857