Computing a sparse solution of a set of linear inequalities
seed = 0;
randn('state',seed);
rand('state',seed);
delta = 1e-8;
m = 100;
n = 50;
A = randn(m,n);
x0 = randn(n,1);
b = A*x0 + rand(m,1);
fprintf(1, 'Finding a sparse feasible point using l1-norm heuristic ...')
cvx_begin
variable x_l1(n)
minimize( norm( x_l1, 1 ) )
subject to
A*x_l1 <= b;
cvx_end
nnz = length(find( abs(x_l1) > delta ));
fprintf(1,['\nFound a feasible x in R^%d that has %d nonzeros ' ...
'using the l1-norm heuristic.\n'],n,nnz);
NUM_RUNS = 15;
nnzs = [];
W = ones(n,1);
disp([char(10) 'Log-based heuristic:']);
for k = 1:NUM_RUNS
cvx_begin quiet
variable x_log(n)
minimize( sum( W.*abs(x_log) ) )
subject to
A*x_log <= b;
cvx_end
nnz = length(find( abs(x_log) > delta ));
nnzs = [nnzs nnz];
fprintf(1,' found a solution with %d nonzeros...\n', nnz);
W = 1./(delta + abs(x_log));
end
nnz = length(find( abs(x_log) > delta ));
fprintf(1,['\nFound a feasible x in R^%d that has %d nonzeros ' ...
'using the log heuristic.\n'],n,nnz);
plot(1:NUM_RUNS, nnzs, [1 NUM_RUNS],[nnzs(1) nnzs(1)],'--');
axis([1 NUM_RUNS 0 n])
xlabel('iteration'), ylabel('number of nonzeros (cardinality)');
legend('log heuristic','l1-norm heuristic','Location','SouthEast')
Finding a sparse feasible point using l1-norm heuristic ...
Calling sedumi: 200 variables, 100 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 100, order n = 201, dim = 201, blocks = 51
nnz(A) = 5100 + 0, nnz(ADA) = 2650, nnz(L) = 1375
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 8.50E-01 0.000
1 : 4.27E+01 2.94E-01 0.000 0.3463 0.9000 0.9000 4.50 1 1 6.5E+00
2 : 6.19E-02 1.05E-01 0.000 0.3581 0.9000 0.9000 1.68 1 1 1.8E+00
3 : -1.67E+01 6.65E-02 0.000 0.6313 0.9000 0.9000 1.49 1 1 9.8E-01
4 : -2.96E+01 2.67E-02 0.000 0.4017 0.9000 0.9000 1.41 1 1 3.4E-01
5 : -3.38E+01 9.99E-03 0.000 0.3739 0.9000 0.9000 1.17 1 1 1.2E-01
6 : -3.52E+01 3.27E-03 0.000 0.3273 0.9000 0.9000 1.06 1 1 3.8E-02
7 : -3.56E+01 1.35E-03 0.000 0.4138 0.9000 0.9000 1.02 1 1 1.6E-02
8 : -3.56E+01 6.56E-05 0.000 0.0485 0.9000 0.0000 1.01 1 1 6.4E-03
9 : -3.58E+01 3.31E-06 0.000 0.0504 0.9341 0.9000 1.01 1 1 8.7E-04
10 : -3.59E+01 7.70E-07 0.000 0.2328 0.9015 0.9000 1.00 1 1 2.0E-04
11 : -3.59E+01 2.10E-07 0.000 0.2725 0.9000 0.9043 1.00 1 1 5.1E-05
12 : -3.59E+01 3.72E-08 0.000 0.1774 0.9124 0.9000 1.00 1 1 9.7E-06
13 : -3.59E+01 6.12E-09 0.000 0.1645 0.9133 0.9000 1.00 1 1 1.7E-06
14 : -3.59E+01 1.12E-10 0.000 0.0183 0.9900 0.9902 1.00 1 1 3.0E-08
15 : -3.59E+01 4.75E-15 0.000 0.0000 1.0000 1.0000 1.00 1 1 1.2E-12
iter seconds digits c*x b*y
15 0.1 Inf -3.5940776942e+01 -3.5940776942e+01
|Ax-b| = 2.3e-12, [Ay-c]_+ = 2.8E-12, |x|= 9.9e+00, |y|= 1.0e+01
Detailed timing (sec)
Pre IPM Post
1.000E-02 8.000E-02 0.000E+00
Max-norms: ||b||=1, ||c|| = 2.494989e+01,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.88599.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +35.9408
Found a feasible x in R^50 that has 44 nonzeros using the l1-norm heuristic.
Log-based heuristic:
found a solution with 44 nonzeros...
found a solution with 44 nonzeros...
found a solution with 44 nonzeros...
found a solution with 44 nonzeros...
found a solution with 44 nonzeros...
found a solution with 43 nonzeros...
found a solution with 42 nonzeros...
found a solution with 40 nonzeros...
found a solution with 39 nonzeros...
found a solution with 39 nonzeros...
found a solution with 39 nonzeros...
found a solution with 39 nonzeros...
found a solution with 38 nonzeros...
found a solution with 38 nonzeros...
found a solution with 38 nonzeros...
Found a feasible x in R^50 that has 38 nonzeros using the log heuristic.