% Detecting a small subset of infeasible linear inequalities
% Section 5.8, Boyd & Vandenberghe "Convex Optimization"
% Written for CVX by Almir Mutapcic - 02/18/06
%
% We consider a set of linear inequalities A*x <= b which are
% infeasible. Here A is a matrix in R^(m-by-n) and b belongs
% to R^m. We apply a l1-norm heuristic to find a small subset
% of mutually infeasible inequalities from a larger set of
% infeasible inequalities. The heuristic finds a sparse solution
% to the alternative inequality system.
%
% Original system is A*x <= b and it alternative ineq. system is:
%
%   lambda >= 0,   A'*lambda == 0.   b'*lambda < 0
%
% where lambda in R^m. We apply the l1-norm heuristic:
%
%   minimize   sum( lambda )
%       s.t.   A'*lambda == 0
%              b'*lambda == -1
%              lambda >= 0
%
% Positive lambdas gives us a small subset of inequalities from
% the original set which are mutually inconsistent.

% problem dimensions (m inequalities in n-dimensional space)
m = 150;
n = 10;

% fix random number generator so we can repeat the experiment
seed = 0;
randn('state',seed);

% construct infeasible inequalities
A = randn(m,n);
b = randn(m,1);

fprintf(1, ['Starting with an infeasible set of %d inequalities ' ...
            'in %d variables.\n'],m,n);

% you can verify that the set is infeasible
% cvx_begin
%   variable x(n)
%   A*x <= b;
% cvx_end

% solve the l1-norm heuristic problem applied to the alternative system
cvx_begin
   variables lambda(m)
   minimize( sum( lambda ) )
   subject to
     A'*lambda == 0;
     b'*lambda == -1; 
     lambda >= 0;
cvx_end

% report the smaller set of mutually inconsistent inequalities
infeas_set = find( abs(b.*lambda) > sqrt(eps)/n );
disp(' ');
fprintf(1,'Found a smaller set of %d mutually inconsistent inequalities.\n',...
        length(infeas_set));
disp(' ');
disp('A smaller set of mutually inconsistent inequalities are the ones');
disp('with row indices:'), infeas_set'

% check that this set is infeasible
% cvx_begin
%    variable x_infeas(n)
%    A(infeas_set,:)*x_infeas <= b(infeas_set);
% cvx_end