patrick-kidger / patrick-kidger/diffrax
Passing additional state between subsequent RHS evaluations?
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 2.1k
- Forks
- 189
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 1
Description
Hi there :)
I want to solve many ODEs which involve a small parameterised convex QP problem as a part of evaluating the right hand side. The QP is of the standard form:
min_x x' Q x + p' x
s.t. Ax <= b
where the parameter p changes continuously, being a continuous function of the ODE state (specifically, I am solving the hamiltonian system given by Pontryagin's minimum principle in optimal control). Up until now, I've only addressed relatively small examples where it is easy to hand-write a brute force active set solver that basically considers all possible active sets, solves every possible KKT system, and in the end selects among those solutions the one with lowest objective that is within constraints.
I would like to approach more challenging systems, where the QP has enough constraints to render this basic approach completely infeasible. Instead, I'd like to use a general convex QP solver -- but because the parameter changes continously, we would benefit greatly from warm starting it with the previous solution.
Now my central question: would it be possible in diffrax to reuse primal/dual information from the last call? This would mathematically not break pureness of the RHS function, as the solution is still the same but we will find it more efficiently. However, from an implementation perspective it obviously would.
Some alternatives I've considered:
- Collect a number of pre-solved points for different parameter values, then at runtime warm-start any suitable convex solver with the closest one. Or, fit a small NN to approximate the map from QP parameter to primal/dual information for a similar warm starting scheme.
- Somehow precompute and/or approximate the solution map (without subsequent "solution polishing"), either starting from explicit convex optimisation (which has a bit less severe, but ultimately similar scalability issues as my current brute-force solution), or from amortised optimistion.
- Recognise that diffrax, or perhaps even jax, are not the best practical solution to this, and use a different ODE solver where additional state is less of an issue.
- Split the ODE up into different parts where the active set remains constant (making the QP solution linear in the parameter). Find the spot where the active set changes, and start the next part of the ODE with corresponding RHS there. a bit like this. Viewed from this angle we essentially have a hybrid system, where the RHS function "jumps" every time the active set changes -- maybe general hybrid system simulation tools could be useful here?
- Extend the ODE state with primal and dual information of the QP solution. Endow the ODE with dynamics that correspond to a continuous time convex optimiser to make sure the QP solution stays (close to) optimal. Probably keeping the QP solution accurate will render the system very stiff and unpleasant. Probably a contraption like this would be better formulated as a DAE though.
I'm thankful about any thoughts and suggestions :) (also i realise that alternative 5 and maybe others are a bit outlandish and are definitely not the practical solution here, just including it for completeness' sake)
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
No file, test, or entry point is named in the issue. Start by reviewing how diffrax evaluates RHS functions and carries solver state, then determine whether warm-start information can be supported without changing solver semantics. Done would require an agreed API, implementation scope, and tests for the proposed state-passing behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100