basic question: interpreting numerical errors from SeDuMi

[confused physicist]

Hello all,

I'm new to linear optimization problems, but one (a semidefinite program) came up and I'm using SeDuMi to solve it.  It works but I'm not sure how to interpret the result.  Hopefully this is not a silly question or one that has been covered.

     As it says in the documentation, you can expect some numerical errors in the answers given, and I have that: the answer given does not exactly solve the constraints (|Ax-b| =   9.2e-09).  I need to have a rigorous argument that there is an exact solution with approximately the given value for the thing maximized, c*x.  Can I claim this?  I'm thinking of the approximate solution x and the nearest exact one x_{exact} as two points in the (natural inner-product) space of matrices.  How do I know that the change in c*x between x and x_{exact} is not big even if they are close in that space?  Is this guaranteed by something in the results? I have a feeling this may be basic and well-known, but I don't know it.

    Any help gratefully appreciated!

The output is below:

The coefficient matrix is not full row rank, numerical problems may occur.

SeDuMi 1.3 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 = 26, order n = 17, dim = 257, blocks = 2

nnz(A) = 556 + 0, nnz(ADA) = 676, nnz(L) = 351

 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec

  0 :            1.13E+01 0.000

  1 :  -6.04E+00 2.33E+00 0.000 0.2061 0.9000 0.9000  -0.77  1  1  1.9E+01

  2 :  -7.01E+00 5.58E-01 0.000 0.2398 0.9000 0.9000   0.84  1  1  4.2E+00

  3 :  -3.90E+00 1.31E-01 0.000 0.2349 0.9000 0.9000   2.11  1  1  5.6E-01

  4 :  -3.01E+00 2.96E-02 0.000 0.2258 0.9000 0.9000   1.53  1  1  9.8E-02

  5 :  -2.84E+00 1.51E-03 0.000 0.0509 0.9900 0.9900   1.13  1  1  4.7E-03

  6 :  -2.83E+00 7.65E-05 0.000 0.0508 0.9900 0.9900   1.01  1  1  2.4E-04

  7 :  -2.83E+00 6.08E-06 0.000 0.0795 0.8896 0.9450   1.00  1  1  2.8E-05

  8 :  -2.83E+00 2.69E-07 0.257 0.0442 0.9900 0.9900   1.00  1  1  1.3E-06

  9 :  -2.83E+00 1.80E-08 0.000 0.0668 0.9900 0.9900   1.00  1  1  8.4E-08

 10 :  -2.83E+00 1.89E-09 0.027 0.1052 0.9450 0.9450   1.00  2  2  8.8E-09

iter seconds digits       c*x               b*y

 10      0.5   9.1 -2.8284271442e+00 -2.8284271417e+00

|Ax-b| =   9.2e-09, [Ay-c]_+ =   2.2E-15, |x|=  5.5e+00, |y|=  1.4e+01

Detailed timing (sec)

   Pre          IPM          Post

4.280E-01    1.006E+00    9.600E-02    

Max-norms: ||b||=1, ||c|| = 4,

Cholesky |add|=0, |skip| = 4, ||L.L|| = 67.3521.

[Adkitta]

You can wait for Dr. Lofberg to chip in, but looks like SeDuMi has converged to the prescribed numerical tolerance for the duality gap. You can try an even smaller duality gap (default = 1e-9). We know that numerical computations are fundamentally limited by the floating-point implementation. You may also want to look at the DIMACS metrics, see this paper: "An independent benchmarking of SDP and SOCP solvers".

[Johan Löfberg]

From that it is is not enough to infer much.

Consider [x 1;1 y]>=0, x == 1e-9, minimize y. The optimal solution is x=1e-9 and y = 1e9. Now violate the equality and let x be 1e-16. The solution now is y = 1e16 while still maintaining feasibility of the eigenvalues, and the error on the equalities are around 1e-9 as in your case. Hence, you can obtain solutions arbitrarily far away from the true solution, with small errors

(EDITED: accidentally wrote maximize)

[confused physicist]

Many thanks for the useful answers.  I had noticed these kinds of examples, but they all seem to have special properties.  I am hoping that there exists a standard way to rule out this problem and infer my desired result, simply by appealing to some simple properties of my SDP.  Is my hope -- that there is a standard result in a textbook to reference, and that someone can tell me where to begin hunting for it -- not true?  Otherwise I guess I will have to (a) take time making some argument of my own (b) find some matrix of rational numbers near to the computational output that seen to exactly obey the constraints.  (There are papers in print in my field that, I think, are assuming this kind of thing works without any justification, so it might be important).

[Johan Löfberg]

No particular result springs to mind. Intuitively  knowing a bound on the size of the optimal solution and a ball which includes all feasible solutions would probably be enough, but I'm not that deep into that field you give you any pointers

All I know is that the geometry of SDP really can create bizarre effects. Here is an innocently looking problem which fails to be solved by SeDuMi (and other solvers I guess) for n larger than 5. The reason is that the optimal solution grows doubly exponentially (optimal objective x0^n^2

F  = [];

n  = 6;

x0 = 2;

x = sdpvar(n,1);

for i = 1:n-1

    F = [F, [x(i+1) x(i);x(i) 1]>=0]

end

solvesdp([x(1)==x0,F],x(end))

Also here, having a small error in the equality can lead to large changes in the optimal solution x.

[confused physicist]

Thanks, that certainly helps a lot. I guess in the weird examples the constraint surface is very close to the boundary of the positive semidefinite region over a large range of values of the quantity being maximised, and one just has to rule that out,or something like that.  Anyway thanks again, I will think about it and ask the people who have published such results what they think about it.