# Finding a point that satisfies many linear inequalities

Jump to: Source code Text output Plots Library index

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