% 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 = 100;
n = 2;

one = ones(m,1);
zero = zeros(m,1);

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

%sum of infeasibilities heuristic
cvx_begin
   variables a_p(n) b_p(1)
   minimize( sum( ( ones(m,1) -(X_train*a_p + b_p).* labels_train ) ) )
cvx_end

% number of satisfied inequalities
nv = length( find(( ones(m,1) - (X_train*a_p + b_p).* labels_train )< zero));
fprintf(1,'\nFound an x (%d %d %d) that violates %d out of %d inequalities.\n',a_p, b_p,nv,m);