# Detecting a small subset of infeasible linear inequalities

Jump to: Source code Text output Plots Library index

    % 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

    Starting with an infeasible set of 150 inequalities in 10 variables.

    Calling sedumi: 150 variables, 11 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
    eqs m = 11, order n = 151, dim = 151, blocks = 1
    nnz(A) = 1650 + 0, nnz(ADA) = 121, nnz(L) = 66
     it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
      0 :            2.27E+02 0.000
      1 :   1.27E-02 7.71E+00 0.000 0.0339 0.9900 0.9900   2.93  1  1  1.7E+00
      2 :   4.31E-01 2.34E+00 0.000 0.3028 0.9000 0.9000   0.88  1  1  8.0E-01
      3 :   5.11E-01 1.16E+00 0.000 0.4971 0.9000 0.9000   0.88  1  1  5.3E-01
      4 :   5.53E-01 4.79E-01 0.000 0.4126 0.9000 0.9000   0.95  1  1  2.9E-01
      5 :   5.86E-01 1.85E-01 0.000 0.3860 0.9000 0.9000   0.95  1  1  1.4E-01
      6 :   5.96E-01 7.30E-02 0.000 0.3946 0.9000 0.9125   0.99  1  1  6.2E-02
      7 :   5.99E-01 2.74E-02 0.000 0.3748 0.9000 0.9202   1.00  1  1  2.6E-02
      8 :   6.01E-01 7.80E-03 0.000 0.2850 0.9105 0.9000   1.00  1  1  7.4E-03
      9 :   6.01E-01 4.39E-04 0.000 0.0563 0.9902 0.9900   1.00  1  1  4.2E-04
     10 :   6.01E-01 5.09E-07 0.000 0.0012 0.9990 0.9990   1.00  1  1
    iter seconds digits       c*x               b*y
     10      0.0   Inf  6.0131198034e-01  6.0131198034e-01
    |Ax-b| =   7.1e-17, [Ay-c]_+ =   1.3E-16, |x|=  2.8e-01, |y|=  8.1e-01

    Detailed timing (sec)
       Pre          IPM          Post
    0.000E+00    4.000E-02    0.000E+00
    Max-norms: ||b||=1, ||c|| = 1,
    Cholesky |add|=0, |skip| = 0, ||L.L|| = 9.91492.
    ------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): +0.601312

    Found a smaller set of 11 mutually inconsistent inequalities.

    A smaller set of mutually inconsistent inequalities are the ones
    with row indices:

    ans =

         1    22    33    54    59    73    79    94   115   136   149