Feasibility of LMI(SDP) in cvx


#1

Hi,

I am solving a robust control problem and it eventually boils down to the feasibility of an LMI. This is what it looks like in cvx:

cvx_begin sdp
variable X(3N,3N) semidefinite
variable s nonnegative
s <= 10000;
f(X) + s g(X) <= 0;
cvx_end

This is infeasible asserted by cvx. But if I add some insignificant constraint as
cvx_begin sdp
variable X(3N,3N) semidefinite
variable s nonnegative
s <= 10000;
X >= 1e-8eye(3N);
X <= 1e-2eye(3N);
f(X) + s g(X) <= 0;
cvx_end
Then it becomes feasible. Which result should I trust? The solver is SDPT3.
Also both formulations are infeasible by mosek. Thanks.


(Mark L. Stone) #2

Mosek is probably more reliable in general than SDPT3, and better able to deal with numerically difficult problems. But based on addition of constraints causing the problem to be reported feasible when it was reported infeasible without the added constraints, it appears that your problem may be numerically unstable.

Specifying the very large upper bound of 10000 could perhaps be causing numerical difficulties in the solver. Can you look at changing the problem formulation, and specifically, perhaps the scaling so that any upper bound for S is smaller in magnitude?

You haven’t shown us what fX) and g(X) are, including whatever numerical “sins” they may exhibit, so your problem is not reproducible. If you at least show the solver output from SDPT3 and Mosek, perhaps someone, such as one of the Mosek guys who read the forum, could better assess the situation.

What are the results of eig(f(X)+s*g(X)) using the values of s and X produced by running CVX with the reported feasible result? If 0 <= s <= 10000 and the maximum eigenvalue is either non-positive, or a small enough positive number to satisfy you as being feasible for practical purposes (i.e., within accepted tolerance), and min eigenvalue of X is nonnegative or negative of sufficiently small magnitude, then you will have the proof in the pudding of feasibility.


#3

Thanks for answering my question. f(X) is linear in X. g(X) is a typo and should be some constant matrix. s in the solution is indeed a very small positive number and X is positive definite if not considering 10^{-9} as zero. But f(X) + s* g(X) gives some small positive eigenvalue such as $10^{-9}$ish.


(Mark L. Stone) #4

10^{-9} is within solver tolerance of zero for the default setting of any of the solvers called by CVX.

The coefficients in f(X) as well as the constant values in g(X) can affect the numerical difficulty(stability) of the problem.

What happens iif you change the bound on s, to, for instance, s <= 10 ?


#5

I tried s=10, 5, 1. All of them give a feasible solution but the order of s is 10^{-8}. Oddly, if I took out the constraint, only asserting s to be nonnegative, the cvx_status is failed.


(Mark L. Stone) #6

If you want someone to make a definitive assessment, you will have to supply reproducible code, including all input data.