End-to-End Learning to Warm-Start for Real-Time Quadratic Optimization

Rajiv Sambharya, Georgina Hall, Brandon Amos, Bartolomeo Stellato
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, PMLR 211:220-234, 2023.

Abstract

First-order methods are widely used to solve convex quadratic programs (QPs) in real-time appli- cations because of their low per-iteration cost. However, they can suffer from slow convergence to accurate solutions. In this paper, we present a framework which learns an effective warm-start for a popular first-order method in real-time applications, Douglas-Rachford (DR) splitting, across a family of parametric QPs. This framework consists of two modules: a feedforward neural network block, which takes as input the parameters of the QP and outputs a warm-start, and a block which performs a fixed number of iterations of DR splitting from this warm-start and outputs a candidate solution. A key feature of our framework is its ability to do end-to-end learning as we differentiate through the DR iterations. To illustrate the effectiveness of our method, we provide generalization bounds (based on Rademacher complexity) that improve with the number of training problems and number of iterations simultaneously. We further apply our method to three real-time applications and observe that, by learning good warm-starts, we are able to significantly reduce the number of iterations required to obtain high-quality solutions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v211-sambharya23a, title = {End-to-End Learning to Warm-Start for Real-Time Quadratic Optimization}, author = {Sambharya, Rajiv and Hall, Georgina and Amos, Brandon and Stellato, Bartolomeo}, booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference}, pages = {220--234}, year = {2023}, editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.}, volume = {211}, series = {Proceedings of Machine Learning Research}, month = {15--16 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v211/sambharya23a/sambharya23a.pdf}, url = {https://proceedings.mlr.press/v211/sambharya23a.html}, abstract = {First-order methods are widely used to solve convex quadratic programs (QPs) in real-time appli- cations because of their low per-iteration cost. However, they can suffer from slow convergence to accurate solutions. In this paper, we present a framework which learns an effective warm-start for a popular first-order method in real-time applications, Douglas-Rachford (DR) splitting, across a family of parametric QPs. This framework consists of two modules: a feedforward neural network block, which takes as input the parameters of the QP and outputs a warm-start, and a block which performs a fixed number of iterations of DR splitting from this warm-start and outputs a candidate solution. A key feature of our framework is its ability to do end-to-end learning as we differentiate through the DR iterations. To illustrate the effectiveness of our method, we provide generalization bounds (based on Rademacher complexity) that improve with the number of training problems and number of iterations simultaneously. We further apply our method to three real-time applications and observe that, by learning good warm-starts, we are able to significantly reduce the number of iterations required to obtain high-quality solutions.} }
Endnote
%0 Conference Paper %T End-to-End Learning to Warm-Start for Real-Time Quadratic Optimization %A Rajiv Sambharya %A Georgina Hall %A Brandon Amos %A Bartolomeo Stellato %B Proceedings of The 5th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2023 %E Nikolai Matni %E Manfred Morari %E George J. Pappas %F pmlr-v211-sambharya23a %I PMLR %P 220--234 %U https://proceedings.mlr.press/v211/sambharya23a.html %V 211 %X First-order methods are widely used to solve convex quadratic programs (QPs) in real-time appli- cations because of their low per-iteration cost. However, they can suffer from slow convergence to accurate solutions. In this paper, we present a framework which learns an effective warm-start for a popular first-order method in real-time applications, Douglas-Rachford (DR) splitting, across a family of parametric QPs. This framework consists of two modules: a feedforward neural network block, which takes as input the parameters of the QP and outputs a warm-start, and a block which performs a fixed number of iterations of DR splitting from this warm-start and outputs a candidate solution. A key feature of our framework is its ability to do end-to-end learning as we differentiate through the DR iterations. To illustrate the effectiveness of our method, we provide generalization bounds (based on Rademacher complexity) that improve with the number of training problems and number of iterations simultaneously. We further apply our method to three real-time applications and observe that, by learning good warm-starts, we are able to significantly reduce the number of iterations required to obtain high-quality solutions.
APA
Sambharya, R., Hall, G., Amos, B. & Stellato, B.. (2023). End-to-End Learning to Warm-Start for Real-Time Quadratic Optimization. Proceedings of The 5th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 211:220-234 Available from https://proceedings.mlr.press/v211/sambharya23a.html.

Related Material