I want to determine whether a given 3x3 matrix is positive-semidefinite or not. To do so, I write the following SDP in YALMIP
v=0.2;
a=sdpvar(1);
b=sdpvar(1);
M=[1 a -v/4 ; b 1 0 ; -v/4 0 0.25];
x=sdpvar(1);
optimize([M+x*eye(3)>=0],x,sdpsettings('solver','sedumi'))
This program gives me the error "Dual infeasible, primal improving direction found". This happens for any value of v in the interval (0,1].
Given that this problem is tractable, I diagonalized the matrix directly obtaining that the three eigenvalues are the three roots of the following polynomial
16*t^3 - 36*t^2 + (24 - 16*a*b - v^2)*t + (-4 + 4*a*b + v^2)
Computing the values of the three roots numerically I see that the three of them are positive for sign(a)=sign(b) (except for a small region in the neighborhood of a,b=+-1), for any value of v. Therefore, the SDP should run without problems and output a negative value of x without further complications.
To make things more interesting, I ran the same code with the following matrix
M=[1 a v/4 ; b 1 0 ; v/4 0 0.25];
This matrix has the same eigenvalues as the previous one, and in this case the program runs without any issues, confirming that the matrix is indeed positive-semidefinite.
I am really curious about the nature of this issue, any help would be really appreciated.
EDIT: I also tried the SDPT3 solver, and results are very similar. In fact, the program runs smoothly for the case of +v, but when i put a minus sign I get the following error
'Unknown problem in solver (Turn on 'debug' in sdpsettings) (Error using & …'
Furthermore, when I add some restrictions to the variables, i.e., I run the following command
optimize([total+w*eye(3)>=0,-1<=a<=1,-1<=b<=1],w,sdpsettings('solver','sdpt3'))
Then the error turns to an 'Infeasible problem' error.
Late answer, but anyway. The matrix you have specified is not symmetric. Semidefinite programming is about optimization over the set of symmetric positive semi-definite matrices.
When you define this unsymmetric matrix constraint in YALMIP, it is simply interpreted as a set of 9 linear elementwise constraints, and for that linear program, the optimal x is unbounded.