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
4

On a different note, what @Mark_L_Stone just did here has intrigued me for my current problem. I noticed that Stephen Boyd’s book Linear Matrix Inequalities in System and Control Theory references EVPs. Do you recommend other resources to learn about EVPs and GEVPs?

5

That;s probably as good as any. Beyond that, you can try to find research papers.

6

I don’t think it has any material directly on generalized eigenvalue problems, but if you can make it through Ben-Tal and Nemirovski “LECTURES ON MODERN CONVEX OPTIMIZATION”, you should be mentally toughened up to make the literature on generalized eigenvalue problems seem not so difficult.

1 Like