How to ensure constraints are not violated?

1

Hi, I am trying to solve an LMI with minimizing frobenius norm over all feasible solutions defined as satisfying (XA)’+XA < 0 and X has some elements constrained to be zero where A is a given matrix and X the variable. This is how I defined the problem using cvx:

n = 56;
nuls = find(form_X == 0);
cvx_begin sdp
    variable X(n,n)
    X(nuls)==0
    minimize norm(X,'fro')
    (X*A)'+(X*A) <= -10^-10*eye(n)
cvx_end

form_X is a matrix containing ones and zeros. CVX tells me this is feasible when I omit the minimisation (all constraints are satisfied), but when I try to minimize, it gives me an infeasible solution and say its Inaccurate/solved. My question is: Is there a way to force the solution into the feasible set? By the way I tried changing cvx_precision with no better result.
Thanks for your help.

2

Generally speaking, no, there is no way to ensure that the problem is precisely feasible. You have to be prepared to accept slight deviations from feasibility. This is the nature of numerical solvers, I am afraid.

But in fact, the real problem with your model. If I may hazard a guess, you’re actually trying to implement a strict inequality (X*A)' + (X*A) < 0. But as the documentation says, CVX cannot differentiate between strict and non-strict feasibilities. So if you had used 0, CVX would simply return the all-zeros value for X.

To fix this, you’ve tried to add a small offset of -10^-10*eye(n) to force strict feasibility. But in that same documentation above, it says this:

Note that the bound needs to be large
enough so that the underlying solver
considers it numerically significant.

Trying to obtain a matrix with values near 10^-10 is simply not practical with the numerical solvers CVX uses, or for that matter, with any numerical solver. In fact, I wouldn’t be surprised if the solvers are effectively driving the entire matrix X to zero, even though you’re trying to prevent this from happening.

What you need to do is re-think your model. I understand why X=0 would not be useful to you, but nor is any value of X buried within the noise of a solver’s numerical errors. You need to think about a new constraint to add to your model that forces X to take on “reasonable” values. For instance, consider this:

(X*A)' + (X*A) <= -eye(n)

Obviously, in perfect arithmetic, this is actually the same as your model, but everything is scaled up by 10^10. But now the problem is much more numerically friendly. CVX will produce more reasonable results, and if you really want -10^-10*eye(n), you can just multiply the value of X that comes out of the model by -10^-10 to get it back.

3

Thank You mcg for your quick answer. However, the problem remains even with using -eye(n) instead of -10^-10*eye(n) i.e. without minimizing the problem is solved (feasible), and with minimizing it becomes infeasible. So as a solution maybe, is there a way to define my own data type in cvx and use it like we do with diagonal, banded, …?

4

I’m not sure what you mean, honestly, by defining a new data type, but it is likely not possible. The only thing I can suggest is trying one of the other solvers to see if it does a better job.