The solution is not the "real" solution?

1

The code is as follows:

y = [-4.91948338301877;0.533572285858026;-0.0799123878389130;-0.525537643381234];
a = [-3703.06252029055,-0.930261381353146,-3724.75952374563,0;3703.06252029055,0.930261381353146,3724.75952374563,0;7320.96461030651,4.63458730389344,7419.77815452072,0;-7320.96461030651,-4.63458730389344,-7419.77815452072,0;-3647.58122946680,-9.25245500491457,-3724.42573372289,0;3647.58122946680,9.25245500491457,3724.42573372289,0];
b = [1;1;1;1;1;1];
c = [6.67780637643839,-1.00167095646579,6.61659816325546,-1];
d = [0];
f = [1,0.300000000000000,0.0355166168216346,0.00357095222159089;0,1,0.233572286001136,0.0355166168216346;0,0,0.920087612151322,0.291965357501420;0,0,-0.525537643502556,0.920087612151322];

cvx_begin
    variable x(4);    
    subject to         
        a * (x - f * y) <= b;
        c * (x - f * y) == d;    
cvx_end

a * (x - f * y) <= b
c * (x - f * y) == d

The status with gurobi is solved and the result is

ans =

     1
     1
     0
     1
     1
     1


ans =

     0

The status with sdpt3 is solved and the result is

ans =

     1
     1
     1
     1
     1
     1


ans =

     0

The status with sedumi is failed!!! And the result is

ans =

     1
     0
     0
     1
     1
     0


ans =

     0

The solution is not feasible for the constraints! How can it happen?

2

When I ran it, sedumi failed, and sdpt3 succeeded.

Here is the sedumi output

Calling SeDuMi 1.34: 6 variables, 3 equality constraints
   For improved efficiency, SeDuMi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.34 (beta) 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 = 3, order n = 7, dim = 7, blocks = 1
nnz(A) = 18 + 0, nnz(ADA) = 9, nnz(L) = 6
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            5.23E+03 0.000
  1 :   0.00E+00 1.38E+00 0.000 0.0003 0.9999 0.9999   1.00  1  1  1.0E+00
Run into numerical problems.

iter seconds digits       c*x               b*y
  1      0.0   4.2  5.9977037191e+00  0.0000000000e+00
|Ax-b| =   8.1e-12, [Ay-c]_+ =   8.7E+00, |x|=  2.4e+00, |y|=  4.8e+00
No sensible solution found.

Detailed timing (sec)
   Pre          IPM          Post
7.001E-03    1.700E-02    2.002E-03    
Max-norms: ||b||=0, ||c|| = 3.656073e+04,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 5.14829.
------------------------------------------------------------
Status: Failed
Optimal value (cvx_optval): NaN

Here is the sdpt3 output:

Calling SDPT3 4.0: 6 variables, 3 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  3
 dim. of linear var  =  6
*******************************************************************
   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||1.1e-05||2.6e+00||3.8e+06|| 6.000004e+01  0.000000e+00|| 0:0:00|| chol  1  1 
 1||1.000||0.989||4.6e-03||2.9e-02||4.1e+04|| 5.998078e+01  0.000000e+00|| 0:0:00|| chol  1  1 
 2||1.000||0.991||2.1e-06||2.7e-04||4.5e+02|| 5.982284e+01  0.000000e+00|| 0:0:00|| chol  1  1 
 3||1.000||1.000||9.8e-07||4.6e-07||4.6e+01|| 4.516516e+01  0.000000e+00|| 0:0:00|| chol  1  1 
 4||0.990||1.000||9.6e-09||2.0e-07||4.5e-01|| 4.516516e-01  0.000000e+00|| 0:0:00|| chol  1  1 
 5||0.990||1.000||1.0e-10||2.3e-09||4.8e-03|| 4.752003e-03  0.000000e+00|| 0:0:00|| chol  1  1 
 6||0.989||1.000||1.1e-12||5.9e-11||5.2e-05|| 5.217583e-05  0.000000e+00|| 0:0:00|| chol  1  1 
 7||0.989||1.000||1.2e-14||1.0e-12||5.7e-07|| 5.733490e-07  0.000000e+00|| 0:0:01|| chol  1  1 
 8||1.000||1.000||4.2e-20||1.0e-12||6.3e-09|| 6.300528e-09  0.000000e+00|| 0:0:01||
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   =  8
 primal objective value =  6.30052846e-09
 dual   objective value =  0.00000000e+00
 gap := trace(XZ)       = 6.30e-09
 relative gap           = 6.30e-09
 actual relative gap    = 6.30e-09
 rel. primal infeas     = 4.25e-20
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 2.6e-09, 4.8e+00, 2.4e+00
 norm(A), norm(b), norm(C) = 1.8e+04, 1.0e+00, 6.3e+04
 Total CPU time (secs)  = 0.50  
 CPU time per iteration = 0.06  
 termination code       =  0
 DIMACS: 4.2e-20  0.0e+00  1.7e-12  0.0e+00  6.3e-09  6.3e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -6.30053e-09

>> disp(x)
   -4.7641
    0.4962
   -0.2270
   -0.4415

So how could you get a solution which does not satisfy the constraints? Because it was not a solution, and the solver reported that it failed. The value of x at the point of solver exit is what you saw to be infeasible, and indeed it is infeasible. if the solver claimed to solve the problem and produced an argmin which was not feasible within tolerance, then you would have a reason to complain.

The value of x at the end of the successful sdpt3 run is indeed feasible. The x, which I didn’t show, at the end of the failed sedumi run is infeasible - as I said, the solver admitted to failing, so I am not complaining that upon CVX exit the x is infeasible.

3

Why do you think the solution computed by sdpt3 is feasible? The solution is not feasible for the equality constraint!
Notice the output of the following boolean expression:

c * (x - f * y) == d

The output is 0! And notice that gurobi claims that it succeed, but the solution is still infeasible!

This is only a simple linear programming problem. Why all these solvers cannot handle it?

4

I was saying that the solution found in the run of sdpt3 I showed was feasible.
Indeed,

c * (x - f * y) - d
ans =
5.453456748985313e-15

Perhaps i got confused when I read your original post. Looking at it now, I don’t see how it makes any sense. You declare variable x(4) , but you show a 6 by 1 result.

You should show the solver output and the value of x after CVX exits…

5

The solution of sdpt3 seems right. Is it the tolerance problem which makes the boolean expression c * (x - f * y) == d is false?

The gurobi output is

Calling Gurobi 5.62: 9 variables, 6 equality constraints
------------------------------------------------------------
Optimize a model with 6 rows, 9 columns and 24 nonzeros
Presolve removed 6 rows and 9 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   0.000000e+00   0.000000e+00      0s

Solved in 0 iterations and 0.00 seconds
Optimal objective  0.000000000e+00
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0
 

x =

   -4.8446
   -0.0373
   -0.1471
    0.0840

When I check

a * (x - f * y) - b
c * (x - f * y) - d

The output is

ans =

   -0.0000
   -2.0000
    0.0000
   -2.0000
   -0.0000
   -2.0000

ans =

   3.1086e-15

It seems a feasible solution too. But still, when I directly check the boolean expression:

 a * (x - f * y) <= b
 c * (x - f * y) == d

The output is

ans =

     1
     1
     0
     1
     1
     1

ans =

     0

It seems infeasible again. I am really confused.

6

Don’t use Boolean expressions to evaluate floating point constraint satisfaction. You have a solution which is feasible within allowed tolerance, but is not strictly feasible. You have some elements which are feasible within tolerance, but evaluate to false by MATLAB which does not make a provision for tolerance.

7

Thanks a lot for your help. I will modify my encoding of the problem.