Adding Extra LMI Constraint

[joshua pilipovsky]

Hello,

I am currently working on a stochastic optimal control problem where I try to steer a probability distribution from some initial state to some final state. To make a long story short, the final covariance is dependent on the control variable, let's say sigmaf = f(K), where K is the control variable and sigmaf is the final covariance that I set myself for the problem. The whole formula is sigmaf = En * (I+BK) * sigmaY * (I+BK)' * En', for reference. The constant covariance sigmaf is a 2x2 matrix in my problem. Moreover, this function f(K) is quadratic in K, which can be seen from the formula. The whole point of this equality constraint is that I want the controller to steer the covariance to sigmaf at time T. The problem with this is that it is not convex, so what I do is I relax the constraint so that sigmaf >= f(K), so that the controller steers the final state to a covariance that is lower than sigmaf. This is now a convex constraint, which I can write as an LMI and put it into a SDP solver such as sdpt3. This works well, and I get great solutions.

What I want to try to do now is maximize the final covariance that I get, given that it must be less than or equal to sigmaf. This is to ensure my solutions are more conservative and robust to disturbances. The way to do this, naturally, is to maximize the logdet of the final covariance, and add that into the overall cost. So, what I tried to do is introduce a new optimization variable called sigmaN, add -logdet(sigmaN) into the cost, and add the constraint sigmaN <= f(K), which can be written as an LMI just as before. This way, I now have sigmaN <= f(K) in addition to sigmaf >= f(K), so it is trying to maximize the final covariance while keeping it lower than sigmaf. The problem is that when I implement this addition into the code, the solver (sdpt3) never converges, and in fact diverges and stops. I am wondering if there is any way to implement what I am trying to do into the SDP. Thank you in advance!

[Johan Löfberg]

Impossible to answer without reproducible code

logdet can easily lead to ill-conditioned problem where one can get arbitrary objective by creating indefinitely thin ellipsoid etc

[joshua pilipovsky]

I've attached the code for the problem. Specifically look at line 95 (new constraint), and lines 110-112 (objective function), which I've commented out. If you run it without those lines, the sdp solver works perfectly, but when I try to add the maximization over the final ellipsoid, it fails to work. Thank you

[Johan Löfberg]

As far as I can tell, you get equally crappy solutions in both cases, but sdpt3 simply happens to report lack of proress in one of them

>> value(sigN)

ans =

   1.0e+08 *

    2.9799    0.0000    0.0000    0.0000

    0.0000    2.9799    0.0000    0.0000

    0.0000    0.0000    2.9799    0.0000

    0.0000    0.0000    0.0000    2.9799

[joshua pilipovsky]

I'm referring to the solution when I don't use sigN at all. The SDP can handle my other costs, but when I try to add the logdet cost and constraint, it doesn't work.

[Johan Löfberg]

misunderstood you

This

Constraints = [Constraints, [-sigN Z; Z' -eye((N+1)*nx)] >= 0];
JsigN = -gamma*logdet(sigN)

makes no sense as you get conflicting definiteness constraints on sigN, and trivially -eye() cannot be positive definite

[Johan Löfberg]

looks like you are trying to apply a schur complement on a nonconvex quadratic x^2-y >=0, which is impossible

[joshua pilipovsky]

Yes, you are absolute right, I didn't catch that. Are there any solvers capable of solving the problem with a convex objective and nonconvex quadratic constraint?

[Johan Löfberg]

A semidefinite programming problem with a nonconvex quadratic semidefinite constraint? Basically no. penbmi is technically developed for that, but in practice you cannot expect it to work