Partial condensing solution

[a1gituser]

Hi,

Is it expected that the solution of the QP when partial condensing is turned off is different from the solution when PC is activated? Are the two solutions expected to be exactly the same?

thanks in advance!

[giaf]

Not sure if I get the question correctly, but the solution of the OCP QP should be exactly the same as the solution at the end of the sequence partial_condensing+partially_dense_ocp_qp_solution+partial_expansion, up to numerical errors (and bugs).

Do you have an instance where they are not the same?

[a1gituser]

hi @giaf,

What I'm noticing is that the solver takes a lot more iterations when partial condensing is activated. In a lot of cases it reaches the maximum number of iterations while the same cases with PC off converge in a very reasonable number of iterations.

I believe the issue is about algorithmic options being used. So, maybe these questions may provide the answers I'm seeking:

1. When using partial condensing can I set ric_alg to any of its values (0 or 1)? Or if PC is on then ric_alg can only be set to 0?
2. Can I change the value of lq_fact independently of the value of ric_alg? Or are they tied together, so that, for example, if I pick ric_alg = 0 then lq_fact must be 0 or 1, but if ric_alg=1 then lq_fact can only be 2. Are there any such 'rules' for these options?

thank you!

[giaf]

In general I would not expect very different behavior of the solver with and without partial condensing. I mean, the numerics and the timings are different, but there are the same active constraints at the solution, it's just a reformulation. If you say that you consistently see very different convergence behavior with the same options, it would be great if you could share a minimal example such that I can investigate the issue.

About the Riccati algorithm, there are two options:

• 0 : classical implementation, where the Riccati recursion matrix P is not factorized. This is more general and works also for indefinite P as long as the reduced Hessian is positive definite.
• 1 : square root implementation, where in order to reduce the asymptotic complexity the matrix P is factorized using Cholesky factorization. This requires P to be positive (semi) definite, so a sufficient condition for that is that the full space Hessian of your QP is positive definite.

About lq_fact, this controls (besides other things like enabling iterative refinement) the switch to a more accurate implementation of the square root Riccati algorithm, that makes use QR factorization, and that has similar requirements about positive definiteness of the full space Hessian of the QP. In case you use lq_fact=2 with ric_alg=0, you would still enable the other stuff (like iterative refinement) but the Riccati factorization would fall back to the classical Riccati recursion without QR factorization, since it doesn't exist a more accurate QR version of the classical Riccati recursion that could also work for indefinite full-space Hessian.

Long story short,

• if your full space Hessian is indefinite (but still the reduced Hessian positive definite), you must use ric_alg=0. Asking for higher accuracy with lq_fact has little effect as it can not switch to a QR factorization, but it can still enable the other stuff like iterative refinement.
• if your full space Hessian is positive (semi) definite (and the reduced Hessian strictly positive definite), you can use any algorithm, with more options regarding speed/accuracy trade off.

About partial condensing, by default it makes use of a condensing algorithm that has N^2 complexity and is analogue to the square-root Riccati recursion, so similar limitations apply (i.e. full space hessian positive (semi) definite).

• in case the full space Hessian is indefinite, you should switch to the equivalent of the classical Riccati recursion (ric_alg=0 in the condensing options), or to the N^3 condensing algorithm cond_alg=1.
• in case the full space Hessian is positive (semi) definite, again you can use any algorithm.

Final summary:

• if your full space Hessian is indefinite (but reduced Hessian still positive definite), use ric_alg=0 in both the partial condensing itself and in the following IPM.
• if your full space Hessian is positive definite, just use whatever you like based on your speed/accuracy preferences.

[a1gituser]

Hi @giaf,

Many thanks for the detailed explanation. This is very helpful. I have one quick follow-up question: is there any documentation related to cond_alg = 1 vs 0?

thanks!

[giaf]

The algorithms are described in Section 9 of my PhD thesis https://orbit.dtu.dk/en/publications/algorithms-and-methods-for-high-performance-model-predictive-cont

[a1gituser]

Thank you for the documents. I will review these.

Also, is there a way to provide an initial guess for the MPC problem when using partial condensing? Some methods that allow me to go from full problem solution to partially condensed solution? (e.g, the opposite to d_part_cond_qp_expand_sol?)

[giaf]

If you solve a sequence of similar QPs, you could provide to the partially condense IPM the solution of the previous partially condensed QP.

Other than that, currently it is not implemented the "condensing" of a solution / initial guess, also because in general an initial guess is of limited help. If of interest, it can be implemented with relatively little effort.

[a1gituser]

If you solve a sequence of similar QPs, you could provide to the partially condense IPM the solution of the previous partially condensed QP.

Other than that, currently it is not implemented the "condensing" of a solution / initial guess, also because in general an initial guess is of limited help. If of interest, it can be implemented with relatively little effort.

Thank you for the quick response. It may not be of immediate use, but just wanted to make sure there wasn't something already in place.