Hyperparameters for tuning the preconditioning and how to inspect the result?

First of all, I want to thank you for your great work. OSQP works like a charm and seems to be very robust.

I am currently playing around with a quadratic program whose matrix M (equation 32 in https://web.stanford.edu/~boyd/papers/pdf/osqp.pdf) has a condition of roughly ~6e+20 so clearly the problem is ill-conditioned. OSQP still gives me a solution in less than 100 iterations when setting eps_rel = 0.005 and eps_abs = 0.005 that is close to the solution that I get when setting the values very small and increasing the maximum iterations. I was quite suprised by this.
Your paper states that you use a preconditioning of the problem using matrix equilibration. Are there any hyperparameters that I could play with?
Where in your code could I look for the result of this preconditioning to see how much the condition number decreased?

In parallel, I am of course looking into ways of formulating my problem in a way that does not lead to such bad conditioning and diagnose which constraints/costs are mainly responsible for the high condition number.
The conditon of matrix A is ~13 while the hessian has some rows that are all zero. This results because some states of my dynamic system should not be punished and are free to vary while beeing constrained in matrix A. The upper block M1 = [P A’] of M has a condition number ~ 90.

Thank you in advance and best regards,

Manuel

If the solution is very close to one you get using many more iterations, then it seems likely that the polishing step has succeeded in the solver. If that is the case then you will get a very high accuracy solution, even if your \eps parameters are relatively large.

Regarding the conditioning: OSQP uses a modification of the Ruiz scaling, described in the OSQP paper in algorithm 2 here. The only parameter that can be tuned is the scaling parameter, which is the number of iterations that we apply in that algorithm. You could also try changing the sigma parameter, since we the KKT matrix that is actually factored within the solver is \sigma I plus the scaled matrix P matrix.

All of this scaling is done within code in the scaling.c source file. There is no nice way of returning the pre- or post- scaling condition number though. In general, a badly conditioned P is not a problem though, e.g. problems with only a semidefinite P (or even 0) are still fine.

Thank you for your quick reply!
I will dive into that part of osqp in a debugging session soon.

May I ask for a general advice?
What is the most crucial part of the QP that one should get straight in order to make OSQP able to solve it very efficient? Is it really the condition of M or something else?
Knowing this would be very helpfull because it would give me a quick check that allows me to see if changes are helpfull for OSQP internally. I assume this is very complex to answer since many parts of OSQP and parameters will be important. However maybe there is kind of a rule of thumb that one can use.

Best regards,

Manuel

It is not obvious at all what makes for an easily solvable problem or not. In general some problems are more difficult to scale than others, but it’s not as simple as saying that the matrix has to be well conditioned or not.

Thanks again for taking your time to answer.
I was already guessing that it would not be that easy. Looking at the paper, one quickly realizes that there is much “magic” under the hood of OSQP to make it as versatile as it is. I played around with the hyperparameters a bit and it seems that you guys did your homework since they really hit a sweetspot. Only adaption of eps_abs and eps_rel seems to be necessary for my use-cases.
I will also do my homework and dive into Convex Optimization a little bit deeper since it’s much fun.
Again congrats for the great work. OSQP is really awesome.