Differentiating through a cone program

Journal of Applied and Numerical Optimization2019Vol. 2019(2)

Citations Over TimeTop 10% of 2019 papers

Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, Walaa M. Moursi, M Abadi, P Barham, J Chen, Z Chen, A Davis, J Dean, M Devin, S Ghemawat, G Irving, M Isard, M Kudlur, J Levenberg, R Monga, S Moore, D Murray, B Steiner, P Tucker, V Vasudevan, P Warden, M Wicke, Y Yu, X Zheng, B Amos, I Jimenez, J Sacks, B Boots, Z Kolter, B Amos, Z Kolter, A Agrawal, A Modi, A Passos, A Lavoie, Ashish Agarwal, A Shankar, I Ganichev, J Levenberg, M Hong, R Monga, S Cai, A Agrawal, R Verschueren, S Diamond, S Boyd, A Ali, E Wong, Z Kolter, S Boyd, E Busseti, S Diamond, R Kahn, K Koh, P Nystrup, J Speth, S Boyd, N Parikh, E Chu, B Peleato, J Eckstein, D Bertsimas, A Thiele, A Ben-Tal, B Golany, A Nemirovski, J.-P Vial, P Donti, B Amos, Z Kolter, S Diamond, S Boyd, S Diamond, S Boyd, F De Avila Belbute-Peres, K Smith, K Allen, J Tenenbaum, Z Kolter, A Fu, B Narasimhan, S Boyd, A Griewank, M Innes, G Leibniz, C Ling, F Fang, Z Kolter, J Lfberg, H Markowitz, D Maclaurin, D Duvenaud, R Adams, A Nemirovski, Y Nesterov, A Nemirovskii, B O'donoghue, E Chu, N Parikh, S Boyd, A Paszke, S Gross, S Chintala, G Chanan, E Yang, Z Devito, Z Lin, A Desmaison, L Antiga, A Lerer, C Paige, M Saunders, O Rodrguez, J Fernandez, D Rumelhart, G Hinton, R Williams, S Robinson, M Udell, K Mohan, D Zeng, J Hong, S Diamond, S Boyd, S Van Der Walt, C Colbert, G Varoquaux, R Wengert, Y Ye, M Todd, S Mizuno

Abstract

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.

Citations Over TimeTop 10% of 2019 papers

Abstract

Related Papers