Source-linked AI summary
Differentiating Through a Cone Program
Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, Walaa M. Moursi
TL;DR
The paper addresses efficient computation of derivatives for convex cone-program solution maps where those derivatives exist. It implicitly differentiates a homogeneous self-dual residual map and solves the resulting systems iteratively, producing derivative and adjoint operators. An open-source Python implementation supports large problems, including one with 4,515,000 coefficient elements.
Problem
The problem is to compute derivatives of cone-program solution maps where they exist, enabling sensitivity analysis with respect to problem coefficients.
Method
The method implicitly differentiates the residual map of a homogeneous self-dual embedding and uses iterative linear-system solves to compute derivative and adjoint linear maps.
Results
The implementation computes perturbation responses and gradients with respect to cone-program coefficients, including an example involving 4,515,000 elements.
Takeaways & Limitations
The open-source Python package returns derivative and adjoint operators as abstract linear maps for integration into automatic-differentiation systems.
Takeaways & Limitations
The implementation assumes a fixed sparsity pattern for A, although differentiation with respect to every entry remains possible by making A dense.
Abstract
from arXiv · showhide
We consider the problem of efficiently computing the derivative of the solution map of a convex cone program, when it exists. We do this by implicitly differentiating the residual map for its homogeneous self-dual embedding, and solving the linear systems of equations required using an iterative method. This allows us to efficiently compute the derivative operator, and its adjoint, evaluated at a vector. These correspond to computing an approximate new solution, given a perturbation to the cone program coefficients (i.e., perturbation analysis), and to computing the gradient of a function of the solution with respect to the coefficients. Our method scales to large problems, with numbers of coefficients in the millions. We present an open-source Python implementation of our method that solves a cone program and returns the derivative and its adjoint as abstract linear maps; our implementation can be easily integrated into software systems for automatic differentiation.
1 Introduction
The paper studies efficient sensitivity analysis for cone-program solutions, which are meaningful where the solution map is single-valued. It connects implicit differentiation with automatic differentiation and provides an implementation for differentiating through cone programs.
- Cone programs: Cone programs minimize a linear objective over the intersection of a subspace and a convex cone, encompassing linear, second-order cone, and semidefinite programs.Every convex optimization problem can be expressed as a cone program.
- Motivation: Because the solution map can be set-valued, perturbation effects are studied in neighborhoods where it is single-valued and therefore an implicit function of the problem data.The paper targets efficient calculation of these perturbation effects.
- Related work: Implicit differentiation has long been used to study optimization sensitivity and has recently been applied to quadratic programs, stochastic optimization, simulators, control, and games.The paper builds on this established sensitivity-analysis framework.
- Automatic differentiation: Automatic differentiation computes exact derivatives of differentiable-function compositions and commonly represents atomic derivatives as abstract linear maps.Reverse-mode AD uses adjoints to efficiently differentiate scalar-valued functions.
- Contribution: The paper gives conditions for differentiability of cone-program solution maps, derives the derivative and adjoint, and provides an open-source Python package.The formulation uses the residual map of a homogeneous self-dual embedding and exploits cone projections, linear solves, and sparsity.
2 The solution map and its derivative
The paper represents a primal-dual cone program through a homogeneous self-dual embedding and its normalized residual map. Under differentiability and invertibility conditions, the solution map is locally differentiable, with derivatives obtained through the chain of embedding, implicit-solution, and recovery maps.
- Primal-dual conic program: A primal-dual cone program uses primal feasibility, dual feasibility, cone membership, and complementary slackness to define its solutions.The primal and dual problems optimize c^T x and b^T y subject to their respective cone constraints.
- The solution map: The solution map sends problem data (A, b, c) to a unique primal-dual solution when the conic program has exactly one solution.The cone is fixed, and the map is expressed as S = φ ◦ s ◦ Q.
- Homogeneous self-dual embedding: The embedding maps problem data to a skew-symmetric matrix, solves a normalized residual equation, and maps the embedding solution back to the primal-dual variables.The embedding variable is partitioned as z = (u, v, w), and N(z,Q)=0 with w>0 characterizes recoverable solutions.
- Derivative of the solution map: The derivative of the full solution map is obtained by applying the chain rule to Q, s, and φ.The recovery map φ is differentiable when the relevant dual-cone projection is differentiable.
- Residual map derivatives: The normalized residual map is affine in Q, so its derivative with respect to Q always exists.Differentiability with respect to z additionally depends on differentiability of the cone projection and requires w ≠ 0.
- Differentiability conditions: If DzN(z,Q) is invertible at a solution where the cone projection is differentiable, the implicit function theorem gives a locally unique differentiable embedding solution.The resulting solution map is differentiable on a neighborhood of Q.
3 Implementation
The implementation computes derivatives and adjoints of cone-program solutions as abstract linear maps, using iterative linear solves and supporting sparse problem data. An open-source Python package applies these maps and demonstrates them on a semidefinite program.
- The implementation exploits a fixed sparsity pattern in A, computing derivatives only for its nonzero entries while allowing dense derivatives when needed.
- The derivative maps coefficient perturbations (dA, db, dc) to solution perturbations (dx, dy, ds), while the adjoint maps solution-space perturbations back to coefficient space.
- LSQR solves the large linear systems using only multiplication by M and M^T, avoiding dense factorization when M is impractical to form.The method defines M = ((Q−I)DΠ(z)+I)/w.
- Python implementation: The Python package provides solve_and_derivative, which returns a primal-dual solution plus functions applying the derivative and its adjoint.The inputs are a SciPy sparse matrix, NumPy arrays, and a cone dictionary.
- Python implementation: The package supports Cartesian products of several standard cones, including zero, positive, second-order, positive semidefinite, exponential, and dual exponential cones.Projection derivatives for these cones are mostly available analytically.