# Problem in solving a SDP question

I am using the code below to find a symmetric matric P that simultaneously satisfies two lyapunov inequalities for two given A1 and A2, and the cvx_status shows ‘Solved’.

cvx_begin sdp
variable P(n,n) symmetric
A1’P + PA1 <= -eye(n)
A2’P + PA2 <= -eye(n)
P >= eye(n)
cvx_end

However, when I reduce the three constraints to two and apply the following code

cvx_begin sdp
variable P(n,n) symmetric
A1’P + PA1 <= -eye(n)
P >= eye(n)
cvx_end

The cvx_status shows ‘Infeasible’. Matrix A1 is same as the one in the first code.

Both A1 and A2 are hurwitz, I do not understand why the problem is feasible for three constraints and infeasible for two constraint.

Thanks.

Can anyone please help me answer this question? Is it because the optimization problem has not bounded region in P, which means the constraints are too few so there is no solution for this optimization problem? Thanks.

Can you provide a reproducible example? Have you tried another solver?

Because no objective function is specified, it s a feasibility problem, and the solver/CVX should return a feasible solution if it exists. So if the first problem is feasible, and the second problem is identical except for deletion of one constraint, the second problem should be feasible as well, which is why you made your post.

Are you sureA1 is unchanged between the problems, such as using new random numbers? Barring that, it sounds like either a bug in CVX or the solver, or the numerics of your problems are bad, for instance, having matrix entries of widely disparate orders of magnitude or high condition number.

Thanks for your answer. In my case, both A1 and A2 are 10-by-10 matrices as following

A1 =
[ 0 & 0& 0& 0& 0& 0& 0& -6.81681473377097e-05 & 0 & 6.81681473377097e-05;
0&0 &0& 0& 0& 0& -7.33367572339382e-05& 0 &7.33367572339382e-05& 0;
0& 0& 0& 0& 0& 0& -5.16605537576411e-06 & 5.16605537576411e-06& -5.16605537576411e-06 &5.16605537576411e-06;
7.5& 0& 0& -50& 0 &0& 0& 0 &0 &0;
0& 7.5& 0& 0& -50 &0& 0& 0& 0 &0;
0 &0& 7.5& 0& 0& -50& 0 &0&0 &0;
0 & 1118142988.12532& 5818971517.66573& 0& -7356203869.24554& -38282707353.0640& -11 & 0& 0& 0;
1118142988.12532 & 0 & -5818971517.66573& -7356203869.24554 & 0& 38282707353.0640& 0& -11& 0& 0;
0& -1118142988.12532& 5818971517.66573& 0& 7356203869.24554& -38282707353.0640& 0& 0& -11& 0;
-1118142988.12532& 0& -5818971517.66573 & 7356203869.24554& 0& 38282707353.0640 & 0 & 0& 0 & -11;]

A2 =
[0& 0& 0& 0& 0& 0& 0& -6.81681473377097e-05& 0& 6.81681473377097e-05;
0& 0& 9.05037530514293& 0& 0& 0& -7.33367572339382e-05& 0& 7.33367572339382e-05& 0;
0& 1.74645891494061& 0& 0& 0& 0& -5.16605537576411e-06& 5.16605537576411e-06 &-5.16605537576411e-06& 5.16605537576411e-06;
7.5& 0& 0& -50& 0& 0& 0& 0& 0& 0;
0& 7.5& 0& 0& -50& 0& 0& 0& 0& 0;
0& 0& 7.5& 0& 0& -50& 0& 0& 0& 0;
0& 1118142988.12532& 5818971517.66573& 0& -7356203869.24554& -38282707353.0640& -11& 0& 0& 0;
1118142988.12532& 0& -5818971517.66573& -7356203869.24554& 0& 38282707353.0640 &0& -11& 0& 0;
0& -1118142988.12532& 5818971517.66573& 0& 7356203869.24554 &-38282707353.0640& 0& 0& -11& 0;
-1118142988.12532& 0& -5818971517.66573& 7356203869.24554 &0& 38282707353.0640& 0& 0 &0 &-11;]

For this set of A1 and A2, the problem with both A1 and A2 constraints is solvable, and the problem with either A1 or A2 constraint is infeasible.

Thank you!

Indeed, A1 and A2 have entries having a very wide range of magnitudes, and the 2-norm condition numbers of A1 and A2 are respectively 8e15 and 1e17, which are very large, and make double precision calculations rather unreliable. Are your order e-5 and e-6 entries “legitimate”, and not “rightly” zero?

Both your two and three constraint problems appear to be infeasible in my efforts. But such determination may be unreliable due to the horrible numerics in A1 and A2. If you are really stuck with these matrices, your only only hope might be going to higher precision - you can take a look at Quadruple Precision .

For some unknown reason, the three constraint problem is feasible on my computer, and the two constraint problem is infeasible. What could be the possible reason for this to happen since both the condition numbers are very large? Thank you.

The calculations are unreliable (untrustworthy) with such poorly conditioned problems. If you have access to it, you can try MOSEK, which is more numerically robust than SeDuMi and SDPT3. But even MOSEK may be on very shaky ground with such a terribly conditioned problem.

The fact that you got inconsistent results tells you that, due to the numerics, neither of the results can be relied on with whatever solver you used.

Thank you! It really helps.

Hi Mark, I have a quick question. Since there is no objective function, what is the meaning of the optimal value that the algorithm gets? I do not understand what is the condition for the algorithm to get the optimal solution when there is no objective function in an SDP problem? Thank you!

When a feasible solution is found, i.e., a solution which satisfies all the constraints, the problem is considered to be solved.

When a solver and CVX claim the problem is solved, that means a feasible solution has been found. Any feasible solution can be found and reported. So any feasible solution is “optimal” if there is no objective function.