# 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 SDPT3 4.0: 150 variables, 11 equality constraints
    ------------------------------------------------------------

     num. of constraints = 11
     dim. of linear var  = 150
    *******************************************************************
       SDPT3: Infeasible path-following algorithms
    *******************************************************************
     version  predcorr  gam  expon  scale_data
        NT      1      0.000   1        0
    it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
    -------------------------------------------------------------------
     0|0.000|0.000|3.3e+02|1.3e+01|2.7e+04| 1.837117e+03  0.000000e+00| 0:0:00| chol  1  1
     1|1.000|0.722|8.0e-05|3.6e+00|9.3e+03| 1.890871e+03  1.394017e+00| 0:0:00| chol  1  1
     2|1.000|1.000|6.1e-05|9.2e-03|1.2e+03| 1.202558e+03  2.851177e-01| 0:0:00| chol  1  1
     3|0.988|1.000|8.5e-07|9.4e-04|1.4e+01| 1.428534e+01  2.837170e-01| 0:0:00| chol  1  1
     4|0.894|1.000|8.5e-08|9.3e-05|1.6e+00| 1.926414e+00  3.698598e-01| 0:0:00| chol  1  1
     5|1.000|0.620|4.6e-10|4.1e-05|7.8e-01| 1.310752e+00  5.276449e-01| 0:0:00| chol  1  1
     6|0.710|0.829|2.3e-10|7.8e-06|3.7e-01| 9.383630e-01  5.653064e-01| 0:0:00| chol  1  1
     7|1.000|1.000|2.4e-11|9.2e-08|1.8e-01| 7.659147e-01  5.879403e-01| 0:0:00| chol  1  1
     8|0.828|0.911|1.6e-11|1.7e-08|7.5e-02| 6.698772e-01  5.952178e-01| 0:0:00| chol  1  1
     9|0.785|1.000|8.2e-12|9.3e-10|3.4e-02| 6.327347e-01  5.982705e-01| 0:0:00| chol  1  1
    10|0.995|0.807|4.5e-14|2.6e-10|4.2e-03| 6.047974e-01  6.005863e-01| 0:0:00| chol  1  1
    11|0.990|0.960|2.6e-15|2.0e-11|2.9e-04| 6.015589e-01  6.012647e-01| 0:0:00| chol  1  1
    12|0.987|0.987|5.4e-15|2.2e-12|3.8e-06| 6.013152e-01  6.013114e-01| 0:0:00| chol  1  1
    13|0.998|0.991|5.8e-15|1.0e-12|5.5e-08| 6.013120e-01  6.013120e-01| 0:0:00| chol  1  1
    14|1.000|0.992|2.4e-15|1.0e-12|6.6e-10| 6.013120e-01  6.013120e-01| 0:0:00|
      stop: max(relative gap, infeasibilities) < 1.49e-08
    -------------------------------------------------------------------
     number of iterations   = 14
     primal objective value =  6.01311981e-01
     dual   objective value =  6.01311980e-01
     gap := trace(XZ)       = 6.64e-10
     relative gap           = 3.01e-10
     actual relative gap    = 3.01e-10
     rel. primal infeas (scaled problem)   = 2.38e-15
     rel. dual     "        "       "      = 1.01e-12
     rel. primal infeas (unscaled problem) = 0.00e+00
     rel. dual     "        "       "      = 0.00e+00
     norm(X), norm(y), norm(Z) = 2.8e-01, 8.1e-01, 1.7e+01
     norm(A), norm(b), norm(C) = 4.1e+01, 2.0e+00, 1.3e+01
     Total CPU time (secs)  = 0.10
     CPU time per iteration = 0.01
     termination code       =  0
     DIMACS: 2.4e-15  0.0e+00  6.7e-12  0.0e+00  3.0e-10  3.0e-10
    -------------------------------------------------------------------

    ------------------------------------------------------------
    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