Closed-form gradient for generic case

[klamike]

Theorem 3 of https://arxiv.org/pdf/2402.02596 shows that the gradient we are looking for (the objective of the completion wrt y) is always equal to $b - Ax$ where $x$ is a dual-optimal solution to the completion problem (corresponding to the equality constraints). That paper is only for LP but I think it holds more generally. If so we can compute the gradient without relying DiffOpt in the generic case.

That lets us continue despite jump-dev/DiffOpt.jl#282 not being merged yet. Note also that L2ODLL would rather use the QuadraticProgram for which objective sensitivity is not available (nor being worked on, AFAICT)

cc @andrewrosemberg @mtanneau

Need to be careful in the quadratic objective case.

[klamike]

The docs now have some sentences on this. Namely, need to watch out for when we predict quadratic slack variables $w$ -- in that case the gradient should be $(Q+Q^\top)w - Q^\top x$

[mtanneau]

the gradient we are looking for (the objective of the completion wrt y) is always equal to b − A x where x is a dual-optimal solution to the completion problem (corresponding to the equality constraints).

Yes if by "generic case" you mean equality constraints + <some constraints on $x$ that are used to do the completion>. The result can be proven in a more general case using Lagrangian duality (by relaxing the equality constraints into a partial Lagragian).
Computing $b - Ax$ requires $x$, which means solving the primal problem.

Need to be careful in the quadratic objective case.

Can you elaborate on this?

[klamike]

I think you may have the notation confused (which is my fault, I haven't added a notations section to the docs). We are predicting $y$ and recovering $z$. $x$ in this case refers to the dual variable of the affine constraints in the completion model (where $-A^\top y$ is on the RHS)

[klamike]

By "quadratic case" I meant when you have a convex QP with bounds on all the variables. In that case, L2ODLL will use bound decomposition, so the NN will predict $y$ and $w$, so we need gradients for both

[klamike]

Should be clearer once I fix the objectives of the completion duals... #1