Comments (2)
A good example of this might be (approximate) matrix factorizations and/or preconditioners, which we need both for iterations of Newton's method, and for backward solves.
from jaxopt.
I've been thinking about this for equality constrained QP solving. Preconditioners might accelerate this a lot. Ideally, we'd like to compute the preconditioner once, and
- Share it between forward and backward pass
- Share it across k outer loop iterations, e.g. if the jaxopt solver solves an inner optimization problem.
I'm looking into preconditioning through Ruiz Equilibration, described in the OSQP paper, section 5.1. I think we could wrap the EqualityConstrainedQP solver in a PreconditionedSolver class. The PreconditionedSolver class would have an API like
@dataclass
class PreconditionedEqualityConstrainedQP:
qp_solver: EqualityConstrainedQP
def init_precond_params(self, params_obj, params_eq):
# Ruiz equilibration code
# This returns (c, D, E) in the paper's notation, ie necessary items for the back and forth preconditioning transformation.
return precond_params
def precondition_problem(params_obj, params_eq):
# Applies preconditioning
return precond_params_obj, precond_params_eq
def recover_solution(self, precond_params, precond_solution):
return solution # of the original, unpreconditioned problem
def run(self, params_obj, params_eq, precond_params, **kwargs):
precond_params_obj, precond_params_eq = self.precondition_problem(params_obj, params_eq, precond_params)
precond_solution = self.qp_solver.run(precond_params_obj, precond_params_eq, **kwargs)
return self.recover_solution(precond_params, precond_solution)
Pros:
- No modification to QP solver
- share preconditioner across forward/backward
- can share preconditioner across outer iterations: the user chooses when to run
preconditioner.init_precond_params
. - The backward leverages the backward on the preconditioned problem, and then applies preconditioning.
Cons:
- This one is not matvec compatible
- Not sure if this is generalizable to other solvers (?)
Let me know what you think! I can work on this next week if you think it's a good idea.
from jaxopt.
Related Issues (20)
- Document solver attributes
- Add usage examples for the documentations HOT 4
- LevenbergMarquardt do not seems to work with non-flat input. HOT 1
- Parallel execution of multiple optimization processes HOT 3
- OSQP should inherit from IterativeSolver HOT 1
- Number of gradient evaluations not applicable to scipy's gradient-free optimizers
- Constrained Optimization and Spanning Tree Polytope HOT 4
- ScipyMinimize(method="TNC") is broken HOT 2
- PolyakSGD should take an optional parameter f_star
- Implicitly differentiate the KKT conditions HOT 5
- OSQP solvers with fun set and no init_params have misleading error message HOT 8
- BoxOSQP does not work without equality constraints HOT 5
- Type precision issue in BoxOSQP HOT 10
- Garbage collection issues HOT 1
- Wrong failure diagnostic print outs from `ZoomLineSearch` under `vmap` HOT 3
- Attempted boolean conversion of traced array - for hager-zhang HOT 2
- Expression tree API like CVXPY HOT 3
- Unnecessary recompilation of _while_loop_lax HOT 8
- Add type annotations
- Consider switching to pyproject.toml
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from jaxopt.