Merge LPGD into diffcp

[a-paulus]

Pull request for enabling LPGD differentiation of the conic program in diffcp.

LPGD info

LPGD computes informative replacements for the true derivatives in degenerate cases as efficient finite differences. For the forward derivatives this implementation just computes standard finite differences (with an additional optional regularization term). For adjoint derivatives we compute finite differences between gradients of the conic program Lagrangian, evaluated at the original solution and a perturbed solution, requiring only one (two if double-sided) additional solver evaluations. See the paper for a detailed derivation of the LPGD adjoint derivatives as the gradient of an envelope function to the linearized loss. Note that in the limit of small perturbations tau, LPGD computes the true derivatives (if they exist). For larger tau the computed derivatives do not match the true derivatives but can provide more informative signal.

Code

LPGD can be enabled with the mode=LPGD argument of solve_and_derivative. It also requires passing the perturbation strength tau (and optionally the regularization strength rho) with derivative_kwargs=dict(tau=0.1, rho=0.1). Alternatively the derivative kwargs can be passed directly, e.g. adjoint_derivative(dx, dy, ds, tau=0.1, rho=0.1)

In the code the main addition are the methods derivative_lpgd/adjoint_derivative_lpgd in cone_program.py. These methods internally call compute_perturbed_solution/ compute_adjoint_perturbed_solution to get the solution to a perturbed optimization problem, and then return the derivatives as finite differences.

For testing, the existing diffcp examples are included as modified versions using LPGD differentiation.

Note on implementation: If activated, the optional regularization requires solving a quadratic cone problem, i.e. setting P!=0. For this reason we added an optional P=None kwarg to solve_internal which is passed to the solver if quadratic objectives are supported.

[SteveDiamond]

This is great! I'm not sure what the failing builds are about.

[PTNobel]

The CI issues are a symptom of the master branch CI being broken. Fixing it is on my goals for the long weekend. I'd love a chance to review this PR carefully before merging, but on a quick pass it looks great Anselm! Is there any timeline you need this merged by?

[a-paulus]

Glad to hear you like it! There is no rush to merge it from my side, please take your time to carefully review it.