Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Apparent non-determinism when using OSQP via CVXPY #116

Open
timothy-nunn opened this issue Aug 14, 2023 · 5 comments
Open

Apparent non-determinism when using OSQP via CVXPY #116

timothy-nunn opened this issue Aug 14, 2023 · 5 comments

Comments

@timothy-nunn
Copy link

timothy-nunn commented Aug 14, 2023

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
Copy link
Member

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
Copy link
Collaborator

@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
Copy link
Collaborator

goulart-paul commented Aug 14, 2023

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
Copy link
Author

timothy-nunn commented Aug 15, 2023

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
Copy link
Collaborator

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants