google
Better OSQP's initialization with active set of constraints detection
The problem (issue #342)
Following the discussion of #342 it has been noticed that the default zero initialization for dual variables was harmful for convergence, specially when primal variables are feasible and close from the optimum.
The proposal
From an initial primal and feasible solution, the active constraints can be "guessed". Since the problem is convex, any initialization can be used. Hence, it makes sense to compute un approximation of dual variables that leverage information on the primal variables.
Te idea would be to detect active constraints, for example with u-Ax<min(rtol*(u-l),atol) and Ax-l<min(rtol*(u-l),atol) in method https://github.com/google/jaxopt/blob/a3601fb4ec6e57e1c47bcb55f51a30ef588545ad/jaxopt/_src/osqp.py#L414 Once the active constraints are identified, the resulting QP only contain equality constraints. This allows to compute dual variables by solving the resulting KKT system. This should be better than zero initialization.
Comparison with OSQP original implementation
In the original implementation the warm start of primal variables does not seem to trigger specific code for dual variable initialization. However they do implement a rescaling with Ruiz equilibration. Ruiz equilibration is not part of Jaxopt for now, but I have some draft on my fork. This issue was also raised in #7
