Apparent non-determinism when using OSQP via CVXPY

[timothy-nunn]

Hi,

We are noticing that for some specific Quadratic Programming Problem in CVXPY we are getting two different solutions seemingly randomly.

I have included more context in https://github.com/timothy-nunn/cvxpy-non-determinism which also includes a reproduction of the issue.

We have only observed this issue for this fairly specific set of inputs but have observed the behaviour over multiple operating systems and versions of OSQP.

I will also note that we observe two different logs when running in verbose mode which shows where these two solutions are coming from. One solution is found after 50 iterations and cannot be polished, whilst the other is found after 75 and can be polished:
log.txt

The main questions are:

1. Is this non-determinism expected? Ie are stochastic numerical methods employed in OSQP that would explain these observations.
2. If it is expected, is there a way to eliminate non-determinism in a testing environment?

[imciner2]

Thanks for reaching out. We don't employ randomness or stochasticity in the algorithm, and I actually wouldn't expect it to converge to two solutions if it is a convex problem (we should always be converging to be near the global solution). I haven't tried running it yet, but do you observe the difference starting near where a rho value update has happened? By default OSQP will do an automatic rho update using time measures, so that could be slightly different if some computations take longer certain times. One thing you could try is to fix the rho update interval to a set number of iterations and see if the behaviors change.

[goulart-paul]

@imciner2's explanation about time-based rho updated is very likely the correct one. See osqp/osqp#239, which was the same issue.

[goulart-paul]

Alternative suggestion : in your example, use:

 qsp.solve(verbose=True, solver=cp.CLARABEL)

which uses an interior point method instead. That solver is always deterministic and will also give higher accuracy solutions.

[timothy-nunn]

Hi @imciner2 and @goulart-paul,

Thank you both for your quick replies. Your suggestion about the adaptive rho appears to be the cause of our observations. My (maybe naive) fix for this has been to specify the keyword argument adaptive_rho=False and we are now achieving the same solution every time.

Have you considered documenting this potential behaviour in the rho setp-size section? I think indicating that this non-determinism is possible when the same computations take different times could be valuable to other users. Then again, it seems that this is a rare occurrence.

We will look into the use of Clarabel, thanks for the suggestion.

Thank you very much again,
Tim

[goulart-paul]

I think you might be better served by instead setting adaptive_rho_interval to some positive integer, say 25 or 50, and keeping adaptive_rho = true. That would allow the solver to adapt the rho parameter as needed, but do so in a deterministic way based on iteration count rather than based on the timing of the initial matrix factorization.

I agree that this should be better documented.