Finding a point that satisfies many linear inequalities
m = 150;
n = 10;
seed = 0;
randn('state',seed);
A = randn(m,n);
b = randn(m,1);
fprintf(1, ['Starting with an infeasible set of %d inequalities ' ...
'in %d variables.\n'],m,n);
cvx_begin
variable x(n)
minimize( sum( max( A*x - b, 0 ) ) )
cvx_end
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
eqs m = 150, order n = 303, dim = 312, blocks = 2
nnz(A) = 300 + 1500, nnz(ADA) = 150, nnz(L) = 150
Handling 11 + 1 dense columns.
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 1.56E+01 0.000
1 : 1.73E+02 8.06E+00 0.000 0.5153 0.9000 0.9000 1.18 1 1 1.9E+00
2 : 1.39E+02 2.82E+00 0.000 0.3498 0.9000 0.9000 2.90 1 1 2.8E-01
3 : 8.45E+01 1.14E+00 0.000 0.4045 0.9000 0.9000 2.86 1 1 6.4E-02
4 : 7.42E+01 3.33E-01 0.000 0.2917 0.9000 0.9000 1.47 1 1 1.6E-02
5 : 7.24E+01 1.33E-01 0.000 0.4004 0.9000 0.9000 1.11 1 1 6.1E-03
6 : 7.16E+01 3.93E-02 0.000 0.2954 0.9000 0.9000 1.04 1 1 1.8E-03
7 : 7.16E+01 1.18E-06 0.000 0.0000 0.9000 0.0000 1.01 1 1 1.1E-03
8 : 7.13E+01 3.55E-07 0.000 0.3004 0.9265 0.9000 1.01 1 1 3.2E-04
9 : 7.12E+01 6.98E-08 0.000 0.1968 0.9000 0.9139 1.00 1 1 6.8E-05
10 : 7.12E+01 2.17E-08 0.000 0.3113 0.4278 0.9000 1.00 1 1 2.4E-05
11 : 7.12E+01 9.85E-09 0.000 0.4534 0.9000 0.5955 1.00 1 1 1.1E-05
12 : 7.12E+01 1.82E-09 0.000 0.1844 0.9000 0.9000 1.00 1 1 2.0E-06
13 : 7.12E+01 7.75E-12 0.000 0.0043 0.9990 0.9990 1.00 1 1 8.6E-09
iter seconds digits c*x b*y
13 0.1 Inf 7.1186236806e+01 7.1186236855e+01
|Ax-b| = 8.1e-09, [Ay-c]_+ = 1.2E-07, |x|= 1.4e+01, |y|= 9.6e+00
Detailed timing (sec)
Pre IPM Post
0.000E+00 7.000E-02 0.000E+00
Max-norms: ||b||=3.073745e+00, ||c|| = 2.637396e+01,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +38.9168
Found an x that violates 57 out of 150 inequalities.