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