I get very different solutions from SCS and ECOS on the same QP (and the SCS solution violates the equality constraints).

[Mike Roberts]

Hello there,

Please allow me to introduce myself. I am a PhD student at Stanford in the computer graphics group.

I am working on a sequential convex programming approach for a particular trajectory optimization problem. Since I will be repeatedly solving similar QPs, I would like to use the warm start capabilities of the SCS solver in cvxpy. This is why I'm experimenting with the SCS solver. However, during my initial experiments, I noticed that the solutions I get from SCS and ECOS for the same problem are quite different. As a baseline, I also solve the same problem by directly calling CVXOPT.

The CVXOPT and the ECOS solutions agree, and satisfy all the problem constraints. The SCS solution disagrees with both CVXOPT and ECOS, has a much better objective value, but significantly violates the equality constraints for the problem. I have set max_iters=5000 and eps=1e-6 when calling the SCS solver, which are more accurate than the default settings, and I still see this behavior in SCS.

This makes me think that there might be a bug in the SCS solver.

I'm attaching my problem data to this note. I'm also attaching a short self-contained Python script that calls each of the solvers, plots the solutions, and plots the residuals for all the constraints. Note that the residuals for the equality constraints when using CVXOPT and ECOS are always less than 1e-8. However, the residuals for the equality constraints when using SCS range from +0.2 to -0.2, indicating quite significant violations of the equality constraints.

Cheers,

Mike

[Steven Diamond]

Thanks for putting together such a thorough bug report! I ran the script and I noticed that SCS is returning OPTIMAL_INACCURATE as its status. In the SCS output, this looks like Solved/Inaccurate. This means that SCS was not able to solve the problem to the accuracy desired, but did solve it to a lesser accuracy that may be adequate. I suspect most of the bad results you've gotten from SCS have had this status.

In the bigger picture though, you're not going to get 1e-6 accuracy with SCS unless you run it for a ridiculous number of iterations. Have you considered using CVXGEN (http://cvxgen.com/docs/index.html) or QPGEN (http://www.control.lth.se/user/pontus.giselsson/qpgen/)? They will be thousands of times faster than SCS and more accurate. You might even be able to warm start QPGEN.

[Mike Roberts]

Hi Steven,

Thanks for the quick reply. I don't care about getting 1e-6 accuracy from SCS. I was just trying to get the solver to be as accurate as possible. I would like to get more than [-0.2, 0.2] accuracy though. So I guess for now I'll stick to ECOS.

I considered CVXGEN, but I didn't think it would scale to the problem sizes I care about (roughly 5000 variables, roughly 2000 equality constraints, roughly 2000 inequality constraints). Or if it did scale to problems of this size, it wouldn't be significantly faster than ECOS.

I didn't know about QPGEN. Thanks for the pro tip. This might be an excellent fit for my problem. I'll let you know how it goes  :)

Cheers,

Mike