% Finding a point that satisfies many linear inequalities
% Section 11.4.1, 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 heuristic to find a point x that violates
% only a small number of inequalities.
%
% We use the sum of infeasibilities heuristic:
%
%   minimize   sum( max( Ax - b ) )
%
% which is equivalent to the following LP (book pg. 580):
%
%   minimize   sum( s )
%       s.t.   Ax <= b + s
%              s >= 0
%
% with variables x in R^n and s in R^m.

% 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);

% sum of infeasibilities heuristic
cvx_begin
   variable x(n)
   minimize( sum( max( A*x - b, 0 ) ) )
cvx_end

% full LP version of the sum of infeasibilities heuristic
% cvx_begin
%   variables x(n) s(m)
%   minimize( sum( s ) )
%   subject to
%     A*x <= b + s;
%     s >= 0;
% cvx_end

% number of satisfied inequalities
nv = length( find( A*x > b ) );
fprintf(1,'\nFound an x that violates %d out of %d inequalities.\n',nv,m);