I am trying to solve the following feasibility problem (as part of a GEVP).
cvx_clear
cvx_begin sdp
variable DD(2,2) diagonal;
M'*DD*M-t*DD <= -1e-6*eye(2);
DD >= 1e-6*eye(2);
M'*DD*M >= 0;
cvx_end
This code works most of the time. Sometimes, however, it reports Solved, yet the solution is infeasible (DD has a negative eigenvalue). This behavior seems to be solver dependent (different numbers cause the problem in SeDuMi or SDPT3, but it occurs in both).
I’ve also noticed that cvx_optval in this case is not close to 0.
What could be causing cvx to report that a feasibility problem has been solved when it is actually infeasible?
Example inputs (using SeDuMi)
M=[-0.795393541488967 + 0.846262947097616i, -0.204606458511033 - 0.846262947097616i;
0.000795393541489 - 0.000846262947098i, 0.000204606458511 + 0.000846262947098i];
t=.5;
Which yields:
Calling sedumi: 11 variables, 2 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
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 = 2, order n = 7, dim = 21, blocks = 4
nnz(A) = 18 + 0, nnz(ADA) = 4, nnz(L) = 3
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 5.13E+00 0.000
1 : 0.00E+00 9.45E-01 0.000 0.1842 0.9000 0.9000 1.00 1 1 9.2E-01
2 : 0.00E+00 8.25E-02 0.000 0.0873 0.9900 0.9900 1.00 1 1 8.0E-02
3 : 0.00E+00 7.24E-03 0.029 0.0878 0.9900 0.9900 1.00 1 1 7.0E-03
4 : 0.00E+00 1.56E-03 0.263 0.2157 0.9000 0.9000 1.00 1 1 1.5E-03
5 : 0.00E+00 3.34E-04 0.000 0.2141 0.9000 0.9000 0.99 1 1 3.3E-04
6 : 0.00E+00 7.87E-06 0.000 0.0235 0.9904 0.9900 0.93 1 1 8.8E-06
7 : 0.00E+00 4.67E-07 0.000 0.0594 0.9100 0.9000 -0.19 1 1 6.9E-06
8 : 0.00E+00 9.02E-09 0.000 0.0193 0.9902 0.9900 -1.59 1 1 3.6E-06
9 : 0.00E+00 2.49E-10 0.000 0.0276 0.9900 0.9295 -1.38 1 1 6.3E-06
10 : 0.00E+00 8.66E-11 0.000 0.3477 0.9000 0.7478 -3.11 1 1 1.6E-05
11 : 0.00E+00 1.30E-11 0.000 0.1497 0.9240 0.9000 -4.79 1 1 3.3E-06
12 : 0.00E+00 2.61E-13 0.000 0.0201 0.9900 0.9785 -1.17 1 1 5.3E-06
iter seconds digits c*x b*y
12 0.1 Inf -3.6076012912e+01 0.0000000000e+00
|Ax-b| = 7.2e-07, [Ay-c]_+ = 1.7E-06, |x|= 3.4e+07, |y|= 7.1e-01
Detailed timing (sec)
Pre IPM Post
3.120E-02 6.240E-02 3.120E-02
Max-norms: ||b||=0, ||c|| = 1.851579e-06,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +36.076
The eigenvalues of DD are
-0.000000289433172
0.713265302051374
which violates the 2nd constraint.