Determining Why Matrix Pencil SDP is Infeasible

1

Hello, I am working on a small SDP program. From what I understand, this is what is called a matrix pencil because I only have one decision variable. Unfortunately, I am receiving the infeasible status.

I have a feeling that my problem may be impossible, but it is not very clear because of the simple formulation. The feasibility problem is

\begin{split} R &= \begin{bmatrix} b_{11} + 2x & b_{12} + x & x \\ b_{12} + x & b_{22} & b_{23} \\ x & b_{23} & b_{33} \end{bmatrix} >0 \\ &= \begin{bmatrix} b_{11} & b_{12} & 0 \\ b_{12} & b_{22} & b_{23} \\ 0 & b_{23} & b_{33} \end{bmatrix} + x \begin{bmatrix} 2 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix} >0 \end{split}

where b_{11},b_{12},b_{22},b_{23},b_{33} are given values and x is the decision variable.

Is there any issue with how I set up this problem in CVX? The code is below

% init
cvx_begin sdp
cvx_precision best

% define variables
variables x

% define R
R = [b11 b12 0;b12 b22 b23;0 b23 b33] + x*[2 1 1;1 0 0;1 0 0];

% goal
minimize 1

% constraints
subject to:
R >= 0

cvx_end

One set of values for the b values is below

b11 =   26.2491;
b12 =   -7.39239;
b22 =   -3.12284e-12;
b23 =   -7.30907;
b33 =    0.169802;
2

It is “structurally” infeasible with those input values.

First of all, the diagonal needs to be nonnegative (actually positive, if the SDP constraint is strict, as in the image). But b22 is negative, although it is of sufficiently small magnitude that you might get away with it. But just looking at the lower right 2 by 2 submatrix, which consists entirely of input data: in order for the problem to be feasible, require b22 >= 0, b33 >= 0, and b22*b33 >= b23^2. which for your sample inputs, means that not only must b22 be >= 0, but if b23 and b33are taken as “given”, would need b22 >= 3.1462 to get that block to be psd, which is necessary, but not sufficient for the whole matrix to be psd.

Actually, the following program shows that with b11, b12, b23, b33 given as in your example, the minimum value of b22 to make the problem feasible is the cvx_optval of 314.616.

b11 =   26.2491;
b12 =   -7.39239;
b23 =   -7.30907;
b33 =    0.169802;
cvx_begin sdp

% define variables
variables x b22

% define R
R = [b11 b12 0;b12 b22 b23;0 b23 b33] + x*[2 1 1;1 0 0;1 0 0];

% goal
minimize b22

% constraints
subject to:
R >= 0

cvx_end

Note that you should never use cvx_precision best Just stick with the default, no matter what solver you use. cvx_precision is a well-intentioned , but ill-advised option.

1 Like
3

Another way of looking at it is determining how far R is from being psd, using the most “favorable” value of x.

b11 =   26.2491;
b12 =   -7.39239;
b22 =   -3.12284e-12;
b23 =   -7.30907;
b33 =    0.169802;
cvx_begin sdp

% define variables
variables x t

% define R
R = [b11 b12 0;b12 b22 b23;0 b23 b33] + x*[2 1 1;1 0 0;1 0 0];

% goal
minimize t

% constraints
subject to:
R + t*eye(3) >= 0

cvx_end

has optimal t = cvx_optval = 7.22466, which shows that the maximum achievable minimum eigenvalue of R is - 7.22466, so that is how far R is from being psd with the most favorable value of x. Or put another way if a scalar multiple of the identity matrix is added to R, that multiple would have to be at least 7.22466 in order to make the problem feasible.

1 Like