Feature request: BnB-DAQP support in cvxpy + cvxpygen

[langestefan]

Hello, thank you for developing this amazing solver!

Would it be possible to add support for the BnB mechanism in cvxpy and cvxpygen?

[darnstrom]

Hi @langestefan

I think this should be possible, and I have been considering this before. One thing that I think would be necessary for DAQP to be a good choice in cvxpy + cvxpygen (which applies more generally than for just the BnB part) is for the canonicalization in cvxpy to yield a dense QP. From my experience, currently a lot of extra variables + equality constraints often gets introduced by cvxpy before passing the QP to a solver. This is fine for sparse solvers such as OSQP, but it is detrimental for the performance of a dense solver like DAQP, which would benefit from eliminating any equality constraint (DAQP is able to handle equality constraints internally, but performance wise it would be a lot better if there was an option to eliminate equality constraints before passing it to DAQP to simplify the canonicalization)

So it would be nice if there was a "dense" canonicalization option in cvxpy such that all equality constraints are eliminated (e.g., through a QR decomposition.) This could then be used for using daqp in cvxpy + cvxpygen.

[PTNobel]

Thanks Dan! We definitely agree that our systems are designed around sparse solvers. And we're definitely open to extending our system to support other stuff. Can you explain what you mean by eliminating equality constraints?

For context, in the QP min. ||Ax - b||_2^2, we add a new equality constraint t = Ax - b and change the objective to t^T t because we're worried about squaring the condition number of A and lowering precision. Are you thinking that we should instead evaluate A^T A for the objective?

[darnstrom]

Hi Parth,
Totally agree that it is important to avoid squaring the condition number if possible. (Although, notice that since DAQP is an active-set method, it can typically deal with badly conditioned problem quite well compared with a first-order method such as OSQP.)

First for some context: underneath the hood, DAQP efficiently solves problems of the form min ||R z - c||^2 subject to A z <= b, where R is an upper-triangular/nonsingular matrix (actually it solves a least-distance problem of the form ||u||^2 subject to Mu <= d, but if you have the form above you can easily transform it into such an LDP.)

For your problem with min ||Ax-b||^2, one can transform it to this form with a QR factorization of A (resulting in no squaring of the condition number).

In the case of equality constraints of the form Ax = b, Then with A = [Q1 Q2][R; 0], you can do the variable change x = xp + Q2 z, where xp is any particular solution to A xp = b. It is then possible to reformulate to problem into another QP in terms of z instead of x, eliminating the equality constraint. Then after you have solved the problem in terms of z you can retrieve the optimal x with x = xp + Q2 z. Adding an option to do such a transformation would be nice!

[PTNobel]

Ah of course. That would be pretty easy to do in our current architecture, I think. By the time QpSolver.apply has been evaluated, we have two (sparse) matrices A x = b and G x <= h.

We could probably extend the DAQP interface to handle this. Stefan if you're interested, the MOSEK interfaces use of Dualize is probably the code path to emulate.

The issue is that CVXPYgen relies on their being an affine mapping from parameters in the original space to parameters in the new space; I guess the question is if Max is open to adding an optional QR transform in the middle of canonicalization for one solver.

[langestefan]

Thanks for chiming in Parth!

So if I understand Daniel correctly, there are two parts:

1. Support for dense QP path in cvxpy canonicalization -> @PTNobel could you create an issue for this in cvxpy, since you are more aware of the internals? Then I can take a look at implementing it.
2. Support for BnB-DAQP in cvxpy -> I will create an issue for that in cvxpy.