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 SDPT3: 200 variables, 100 equality constraints
------------------------------------------------------------
num. of constraints = 100
dim. of socp var = 100, num. of socp blk = 50
dim. of linear var = 100
*******************************************************************
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|1.5e+01|1.5e+01|1.3e+05| 1.153213e+02| 0:0:00| chol 1 1
1|0.607|0.203|5.7e+00|1.2e+01|9.6e+04| 1.147035e+03| 0:0:00| chol 1 1
2|0.527|0.755|2.7e+00|3.0e+00|4.4e+04| 1.224390e+03| 0:0:00| chol 1 1
3|0.783|1.000|5.9e-01|2.7e-02|1.1e+04| 7.672027e+02| 0:0:00| chol 1 1
4|0.933|1.000|3.9e-02|8.1e-03|1.2e+03|-2.176195e+02| 0:0:00| chol 1 1
5|1.000|0.960|7.9e-07|8.9e-03|2.8e+02|-3.549165e+01| 0:0:00| chol 1 1
6|0.842|0.872|3.2e-07|1.2e-03|5.3e+01| 3.009030e+01| 0:0:00| chol 1 1
7|0.590|0.753|1.4e-07|3.1e-04|3.3e+01| 3.201707e+01| 0:0:00| chol 1 1
8|0.864|0.581|2.2e-08|1.3e-04|1.9e+01| 3.262613e+01| 0:0:01| chol 1 1
9|1.000|0.553|1.2e-09|5.8e-05|1.1e+01| 3.402021e+01| 0:0:01| chol 1 1
10|1.000|0.851|9.9e-14|8.6e-06|3.9e+00| 3.553340e+01| 0:0:01| chol 1 1
11|0.857|0.651|2.6e-14|3.0e-06|2.2e+00| 3.565455e+01| 0:0:01| chol 1 1
12|0.885|1.000|8.2e-14|8.2e-11|1.1e+00| 3.594403e+01| 0:0:01| chol 1 1
13|1.000|0.971|2.8e-14|1.1e-11|2.2e-01| 3.593053e+01| 0:0:01| chol 1 1
14|1.000|0.667|4.2e-12|5.3e-12|9.5e-02| 3.592692e+01| 0:0:01| chol 1 1
15|0.965|0.928|4.2e-13|1.5e-12|1.7e-02| 3.593930e+01| 0:0:01| chol 1 1
16|0.873|1.000|3.1e-13|1.0e-12|5.3e-03| 3.594086e+01| 0:0:01| chol 1 2
17|0.920|0.980|1.4e-12|1.0e-12|5.9e-04| 3.594084e+01| 0:0:01| chol 2 2
18|1.000|0.977|7.0e-12|1.0e-12|5.9e-05| 3.594077e+01| 0:0:01| chol 2 2
19|0.996|0.998|2.3e-12|1.4e-12|9.1e-07| 3.594078e+01| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 19
primal objective value = 3.59407774e+01
dual objective value = 3.59407765e+01
gap := trace(XZ) = 9.08e-07
relative gap = 1.25e-08
actual relative gap = 1.25e-08
rel. primal infeas = 2.31e-12
rel. dual infeas = 1.39e-12
norm(X), norm(y), norm(Z) = 1.7e+01, 1.6e+00, 9.9e+00
norm(A), norm(b), norm(C) = 7.3e+01, 8.9e+01, 8.1e+00
Total CPU time (secs) = 1.1
CPU time per iteration = 0.1
termination code = 0
DIMACS: 8.0e-12 0.0e+00 5.6e-12 0.0e+00 1.2e-08 1.2e-08
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +35.9408
Found a feasible x in R^50 that has 46 nonzeros using the l1-norm heuristic.
Log-based heuristic:
found a solution with 46 nonzeros...
found a solution with 37 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
found a solution with 35 nonzeros...
Found a feasible x in R^50 that has 35 nonzeros using the log heuristic.