% 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);
Starting with an infeasible set of 150 inequalities in 10 variables.
 
Calling sedumi: 310 variables, 150 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 10 free variables
eqs m = 150, order n = 321, dim = 321, blocks = 1
nnz(A) = 300 + 3000, nnz(ADA) = 150, nnz(L) = 150
Handling 20 + 0 dense columns.
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.48E+02 0.000
  1 :   2.77E+01 7.99E+01 0.000 0.5388 0.9000 0.9000   4.79  1  1  1.5E+00
  2 :   3.28E+01 2.04E+01 0.000 0.2553 0.9000 0.9000   2.03  1  1  3.7E-01
  3 :   3.69E+01 5.54E+00 0.000 0.2714 0.9000 0.9000   1.16  1  1  1.1E-01
  4 :   3.82E+01 2.04E+00 0.000 0.3685 0.9000 0.9000   1.03  1  1  4.2E-02
  5 :   3.87E+01 6.37E-01 0.000 0.3123 0.9000 0.9000   1.01  1  1  1.4E-02
  6 :   3.89E+01 1.85E-01 0.000 0.2900 0.9000 0.9057   1.00  1  1  3.8E-03
  7 :   3.89E+01 3.67E-02 0.000 0.1985 0.9061 0.9000   1.00  1  1  8.1E-04
  8 :   3.89E+01 5.34E-03 0.000 0.1457 0.9253 0.9000   1.00  1  1  1.6E-04
  9 :   3.89E+01 1.60E-03 0.000 0.2990 0.9000 0.9306   1.00  1  1  3.6E-05
 10 :   3.89E+01 8.74E-05 0.000 0.0547 0.9902 0.9900   1.00  1  1  2.3E-06
 11 :   3.89E+01 1.91E-08 0.000 0.0002 0.9999 0.9999   1.00  4  4  
iter seconds digits       c*x               b*y
 11      0.1  15.1  3.8916762959e+01  3.8916762959e+01
|Ax-b| =   1.3e-14, [Ay-c]_+ =   5.1E-15, |x|=  1.5e+01, |y|=  7.4e+00

Detailed timing (sec)
   Pre          IPM          Post
1.000E-02    6.000E-02    0.000E+00    
Max-norms: ||b||=3.073745e+00, ||c|| = 1,
Cholesky |add|=6, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +38.9168

Found an x that violates 54 out of 150 inequalities.