Publications
Journal Articles
2020
-
Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and ControlArXiv e-prints, Mar. 2020
Mixed-integer convex programming (MICP) has seen significant algorithmic and hardware improvements with several orders of magnitude solve time speedups compared to 25 years ago. Despite these advances, MICP has been rarely applied to real-world robotic control because the solution times are still too slow for online applications. In this work, we extend the machine learning optimizer (MLOPT) framework to solve MICPs arising in robotics at very high speed. MLOPT encodes the combinatorial part of the optimal solution into a strategy. Using data collected from offline problem solutions, we train a multiclass classifier to predict the optimal strategy given problem-specific parameters such as states or obstacles. Compared to previous approaches, we use task-specific strategies and prune redundant ones to significantly reduce the number of classes the predictor has to select from, thereby greatly improving scalability. Given the predicted strategy, the control task becomes a small convex optimization problem that we can solve in milliseconds. Numerical experiments on a cart-pole system with walls, a free-flying space robot and task-oriented grasps show that our method provides not only 1 to 2 orders of magnitude speedups compared to state-of-the-art solvers but also performance close to the globally optimal MICP solution.
@article{cauligi2020learning, title = {Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control}, author = {Cauligi, A. and Culbertson, P. and Stellato, B. and Bertsimas, D. and Schwager, M. and Pavone, M.}, journal = {ArXiv e-prints}, archiveprefix = {arXiv}, eprint = {2004.03736}, primaryclass = {cs.RO}, year = {2020}, month = mar, url = {https://arxiv.org/abs/2004.03736}, pdf = {https://arxiv.org/pdf/2004.03736.pdf}, code = {https://github.com/StanfordASL/mlopt-micp} } -
OSQP: An Operator Splitting Solver for Quadratic ProgramsMathematical Programming Computation, Feb. 2020
We present a general purpose solver for convex quadratic programs based on the alternating direction method of multipliers, employing a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix at almost every iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. It can be configured to be division-free once an initial matrix factorization is carried out, making it suitable for real-time applications in embedded systems. In addition, our technique is the first operator splitting method for quadratic programs able to reliably detect primal and dual infeasible problems from the algorithm iterates. The method also supports factorization caching and warm starting, making it particularly efficient when solving parametrized problems arising in finance, control, and machine learning. Our open-source C implementation OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. It is typically ten times faster than competing interior point methods, and sometimes much more when factorization caching or warm start is used. OSQP has already shown a large impact with tens of thousands of users both in academia and in large corporations.
@article{stellato2020, author = {{Stellato}, B. and {Banjac}, G. and {Goulart}, P. and {Bemporad}, A. and {Boyd}, S.}, title = {{OSQP: An Operator Splitting Solver for Quadratic Programs}}, journal = {Mathematical Programming Computation}, year = {2020}, month = feb, code = {https://osqp.org}, pdf = {https://arxiv.org/pdf/1711.08013.pdf}, primaryclass = {math.OC}, url = {https://doi.org/10.1007/s12532-020-00179-2} } -
The Voice of OptimizationMachine Learning (minor revision), Jan. 2020
We introduce the idea that using optimal classification trees (OCTs) and optimal classification trees with-hyperplanes (OCT-Hs), interpretable machine learning algorithms developed in [BD17, BD18], we are able to obtain insight on the strategy behind the optimal solution in any continuous and mixed-integer convex optimization problem as a function of key parameters that affect the problem. In this way, optimization is not a black box anymore. Instead, we redefine optimization as a multiclass classification problem where the predictor gives insights on the logic behind the optimal solution. In other words, OCTs and OCT-Hs give optimization a voice. We show on several realistic examples that the accuracy behind our method is in the 90%-100% range, while even when the predictions are not correct, the degree of suboptimality or infeasibility is very low. We compare optimal strategy predictions of OCTs and OCT-Hs and feed-forward neural networks (NNs) and conclude that the performance of OCT-Hs and NNs is comparable. OCTs are somewhat weaker but often competitive. Therefore, our approach provides a novel, reliable and insightful understanding of optimal strategies to solve a broad class of continuous and mixed-integer optimization problems.
@article{stellato2018b, author = {{Bertsimas}, D. and {Stellato}, B.}, title = {The Voice of Optimization}, journal = {Machine Learning (minor revision)}, year = {2020}, month = jan, adsnote = {Provided by the SAO/NASA Astrophysics Data System}, adsurl = {https://ui.adsabs.harvard.edu/\#abs/2018arXiv181209991B}, archiveprefix = {arXiv}, eprint = {1812.09991}, keywords = {Mathematics - Optimization and Control}, pdf = {https://arxiv.org/pdf/1812.09991.pdf}, primaryclass = {math.OC}, url = {https://arxiv.org/pdf/1812.09991} }
2019
-
Learning Convex Optimization Control PoliciesArXiv e-prints, Dec. 2019
Many control policies used in various applications determine the input or action by solving a convex optimization problem that depends on the current state and some parameters. Common examples of such convex optimization control policies (COCPs) include the linear quadratic regulator (LQR), convex model predictive control (MPC), and convex control-Lyapunov or approximate dynamic programming (ADP) policies. These types of control policies are tuned by varying the parameters in the optimization problem, such as the LQR weights, to obtain good performance, judged by application-specific metrics. Tuning is often done by hand, or by simple methods such as a crude grid search. In this paper we propose a method to automate this process, by adjusting the parameters using an approximate gradient of the performance metric with respect to the parameters. Our method relies on recently developed methods that can efficiently evaluate the derivative of the solution of a convex optimization problem with respect to its parameters. We illustrate our method on several examples.
@article{agrawal2019cocp, author = {Agrawal, Akshay and Barratt, Shane and Boyd, Stephen and Stellato, Bartolomeo}, title = {Learning Convex Optimization Control Policies}, journal = {ArXiv e-prints}, archiveprefix = {arXiv}, eprint = {1912.09529}, primaryclass = {math.OC}, year = {2019}, month = dec, url = {https://arxiv.org/abs/1912.09529}, pdf = {https://arxiv.org/pdf/1912.09529.pdf}, code = {https://github.com/cvxgrp/cocp} } -
Online Mixed-Integer Optimization in MillisecondsINFORMS Journal on Computing (major revision), Jul. 2019
We propose a method to solve online mixed-integer optimization (MIO) problems at very high speed using machine learning. By exploiting the repetitive nature of online optimization, we are able to greatly speedup the solution time. Our approach encodes the optimal solution into a small amount of information denoted as strategy using the Voice of Optimization framework proposed in [BS18]. In this way the core part of the optimization algorithm becomes a multiclass classification problem which can be solved very quickly. In this work we extend that framework to real-time and high-speed applications focusing on parametric mixed-integer quadratic optimization (MIQO). We propose an extremely fast online optimization algorithm consisting of a feedforward neural network (NN) evaluation and a linear system solution where the matrix has already been factorized. Therefore, this online approach does not require any solver nor iterative algorithm. We show the speed of the proposed method both in terms of total computations required and measured execution time. We estimate the number of floating point operations (flops) required to completely recover the optimal solution as a function of the problem dimensions. Compared to state-of-the-art MIO routines, the online running time of our method is very predictable and can be lower than a single matrix factorization time. We benchmark our method against the state-of-the-art solver Gurobi obtaining from two to three orders of magnitude speedups on benchmarks with real-world data.
@article{stellato2019a, author = {{Bertsimas}, D. and {Stellato}, B.}, title = {Online Mixed-Integer Optimization in Milliseconds}, journal = {INFORMS Journal on Computing (major revision)}, year = {2019}, month = jul, adsnote = {Provided by the SAO/NASA Astrophysics Data System}, adsurl = {https://ui.adsabs.harvard.edu/abs/2019arXiv190702206B}, archiveprefix = {arXiv}, eprint = {1907.02206}, keywords = {Mathematics - Optimization and Control}, pdf = {https://arxiv.org/pdf/1907.02206.pdf}, primaryclass = {math.OC}, url = {https://arxiv.org/abs/1907.02206} } -
Infeasibility detection in the alternating direction method of multipliers for convex optimizationJournal of Optimization Theory and Applications, Vol. 183, no. 2, pp. 490-519, 2019
The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive information regarding problem infeasibility for optimization problems with linear or quadratic objective functions and conic constraints, which includes quadratic, second-order cone, and semidefinite programs. In particular, we show that in the limit the iterates either satisfy a set of first-order optimality conditions or produce a certificate of either primal or dual infeasibility. Based on these results, we propose termination criteria for detecting primal and dual infeasibility.
@article{banjac2017, author = {Banjac, G. and Goulart, P. and Stellato, B. and Boyd, S.}, title = {Infeasibility detection in the alternating direction method of multipliers for convex optimization}, journal = {Journal of Optimization Theory and Applications}, year = {2019}, volume = {183}, number = {2}, pages = {490-519}, groups = {quadratic programs}, pdf = {/assets/downloads/publications/2019/admm_infeas.pdf}, url = {http://www.optimization-online.org/DB_HTML/2017/06/6058.html} }
2017
-
Second-Order Switching Time Optimization for Switched Dynamical SystemsIEEE Transactions on Automatic Control, Vol. 62, no. 10, pp. 5407–5414, Oct. 2017
Switching time optimization arises in finite-horizon optimal control for switched systems where, given a sequence of continuous dynamics, one minimizes a cost function with respect to the switching times. We propose an efficient method for computing the optimal switching times for switched linear and nonlinear systems. A novel second-order optimization algorithm is introduced where, at each iteration, the dynamics are linearized over an underlying time grid to compute the cost function, the gradient and the Hessian efficiently. With the proposed method, the most expensive operations at each iteration are shared between the cost function and its derivatives, thereby greatly reducing the computational burden. We implemented the algorithm in the Julia package SwitchTimeOpt allowing the user to easily solve switching time optimization problems. In the case of linear dynamics, many operations can be further simplified and benchmarks show that our approach is able to provide optimal solutions in just a few ms. In the case of nonlinear dynamics, two examples show that our method provides optimal solutions with up to two orders of magnitude time reductions over state-of-the-art approaches.
@article{stellato2017a, author = {Stellato, B. and Ober-Bl{\"o}baum, S. and Goulart, P.}, title = {Second-Order Switching Time Optimization for Switched Dynamical Systems}, journal = {{IEEE} Transactions on Automatic Control}, year = {2017}, volume = {62}, number = {10}, pages = {5407--5414}, month = oct, issn = {0018-9286}, code = {https://github.com/oxfordcontrol/SwitchTimeOpt.jl}, doi = {10.1109/TAC.2017.2697681}, groups = {switching time optimization}, pdf = {http://arxiv.org/pdf/1608.08597.pdf}, url = {https://doi.org/10.1109/TAC.2017.2697681} } -
High-Speed Finite Control Set Model Predictive Control for Power ElectronicsIEEE Transactions on Power Electronics, Vol. 32, no. 5, pp. 4007–4020, May. 2017First Prize Paper Award IEEE Transactions on Power Electronics
Common approaches for direct model predictive control (MPC) for current reference tracking in power electronics suffer from the high computational complexity encountered when solving integer optimal control problems over long prediction horizons. We propose an efficient alternative method based on approximate dynamic programming, greatly reducing the computational burden and enabling sampling times under \(25\: μs\). Our approach is based on the offline minimization of an infinite horizon value function estimate which is then applied to the tail cost of the MPC problem. This allows us to reduce the controller horizon to a very small number of stages while improving overall controller performance. Our proposed algorithm is implemented on a small size FPGA and validated on a variable speed drive system with a three-level voltage source converter. Time measurements showed that only \(5.76\: μs\)are required to run our algorithm for horizon N=1 and \(17.27\: μs\)for N=2 while outperforming state of the art approaches with much longer horizons in terms of currents distortion and switching frequency. To the authors’ knowledge, this is the first time direct MPC for current control has been implemented on an FPGA solving the integer optimization problem in real-time and achieving comparable performance to formulations with long prediction horizons.
@article{stellato2017, author = {Stellato, B. and Geyer, T. and Goulart, P.}, title = {High-Speed Finite Control Set Model Predictive Control for Power Electronics}, journal = {{IEEE} Transactions on Power Electronics}, year = {2017}, volume = {32}, number = {5}, pages = {4007--4020}, month = may, issn = {0885-8993}, prize = {First Prize Paper Award IEEE Transactions on Power Electronics}, prize_link = {https://www.eng.ox.ac.uk/news/1st-prize-for-work-improving-lifespan-and-performance-of-electrical-motors/}, groups = {power electronics}, pdf = {http://arxiv.org/pdf/1510.05578.pdf}, url = {http://dx.doi.org/10.1109/TPEL.2016.2584678} } -
Multivariate Chebyshev Inequality with Estimated Mean and VarianceThe American Statistician, Vol. 71, no. 2, pp. 123–127, 2017
A variant of the well-known Chebyshev inequality for scalar random variables can be formulated in the case where the mean and variance are estimated from samples. In this paper we present a generalization of this result to multiple dimensions where the only requirement is that the samples are independent and identically distributed. Furthermore, we show that as the number of samples tends to infinity our inequality converges to the theoretical multi-dimensional Chebyshev bound.
@article{stellato2017b, author = {Stellato, B. and Van Parys, B. P.G. and Goulart, P.}, title = {Multivariate Chebyshev Inequality with Estimated Mean and Variance}, journal = {The American Statistician}, year = {2017}, volume = {71}, number = {2}, pages = {123--127}, groups = {probability inequalities}, pdf = {http://arxiv.org/pdf/1509.08398.pdf}, url = {http://dx.doi.org/10.1080/00031305.2016.1186559} }
Conference Proceedings
2018
-
Embedded Mixed-Integer Quadratic Optimization Using the OSQP SolverEuropean Control Conference (ECC), Jul. 2018
We present a novel branch-and-bound solver for mixed-integer quadratic programs (MIQPs) that efficiently exploits the first-order OSQP solver for the quadratic program (QP) sub-problems. Our algorithm is very robust, requires no dynamic memory allocation and is division-free once an initial factorization is computed. Thus, it suitable for embedded applications with low computing power. Moreover, it does not require any assumption on the problem data such as strict convexity of the objective function. We exploit factorization caching and warm-starting to reduce the computational cost of QP relaxations during branch-and-bound and over repeated solutions of parametric MIQPs such as those arising in embedded control, portfolio optimization, and machine learning. Numerical examples show that our method, using a simple high-level Python implementation interfaced with the OSQP solver, is competitive with established commercial solvers.
@inproceedings{stellato2018, author = {Stellato, B. and Naik, V. V. and Bemporad, A. and Goulart, P. and Boyd, S.}, title = {Embedded Mixed-Integer Quadratic Optimization Using the {OSQP} Solver}, booktitle = {European Control Conference ({ECC})}, year = {2018}, code = {https://github.com/oxfordcontrol/miosqp}, month = jul, pdf = {/assets/downloads/publications/2018/miosqp_ecc.pdf}, groups = {power electronics, integer programs} }
2017
-
Embedded Code Generation Using the OSQP SolverIEEE Conference on Decision and Control (CDC), Dec. 2017
We introduce a code generation software package that accepts a parametric description of a quadratic program (QP) as input and generates tailored C code that compiles into a fast and reliable optimization solver for the QP that can run on embedded platforms. The generated code is based on OSQP, a novel open-source operator splitting solver for quadratic programming. Our software supports matrix factorization caching and warm starting, and allows updates of the problem parameters during runtime. The generated C code is library-free and has a very small compiled footprint. Examples arising in real-world applications show that the generated code outperforms state-of-the-art embedded and desktop QP solvers.
@inproceedings{banjac2017a, author = {Banjac, G. and Stellato, B. and Moehle, N. and Goulart, P. and Bemporad, A. and Boyd, S.}, title = {Embedded Code Generation Using the {OSQP} Solver}, booktitle = {{IEEE} Conference on Decision and Control ({CDC})}, year = {2017}, month = dec, pdf = {/assets/downloads/publications/2017/osqp_embedded.pdf}, url = {https://ieeexplore.ieee.org/document/8263928}, code = {https://github.com/oxfordcontrol/osqp_codegen_benchmarks}, groups = {quadratic programs} }
2016
-
Real-time FPGA Implementation of Direct MPC for Power ElectronicsIEEE Conference on Decision and Control (CDC), pp. 1471–1476, Dec. 2016
Common approaches for direct model predictive control (MPC) for current reference tracking in power electronics suffer from the high computational complexity encountered when solving integer optimal control problems over long prediction horizons. Recently, an alternative method based on approximate dynamic programming showed that it is possible to reduce the computational burden enabling sampling times under \(25\:μs\)by shortening the MPC horizon to a very small number of stages while improving the overall controller performance. In this paper we implemented this new approach on a small size FPGA and validated it on a variable speed drive system with a three-level voltage source converter. Time measurements showed that only \(5.76\:μs\)are required to run our algorithm for horizon \(N=1\)and \(17.27\:μs\)for \(N=2\)while outperforming state of the art approaches with much longer horizons in terms of currents distortion and switching frequency. To the authors knowledge, this is the first time direct MPC for current control has been implemented on an embedded platform achieving comparable performance to formulations with long prediction horizons.
@inproceedings{stellato2016a, author = {Stellato, B. and Goulart, P.}, title = {Real-time {FPGA} Implementation of Direct {MPC} for Power Electronics}, booktitle = {{IEEE} Conference on Decision and Control ({CDC})}, year = {2016}, pages = {1471--1476}, month = dec, groups = {power electronics}, pdf = {/assets/downloads/publications/2016/pels_cdc2016.pdf}, url = {https://doi.org/10.1109/CDC.2016.7798474} } -
Optimal Control of Switching Times in Switched Linear SystemsIEEE Conference on Decision and Control (CDC), pp. 7228–7233, Dec. 2016
Switching time optimization arises in finite-horizon optimal control for switched systems where, given a sequence of continuous dynamics, we minimize a cost function with respect to the switching times. In this paper we propose an efficient method for computing optimal switching times in switched linear systems. We derive simple expressions for the cost function, the gradient and the Hessian which can be computed efficiently online without performing any integration. With the proposed method, the most expensive computations are decomposed into independent scalar exponentials which can be efficiently computed and parallelized. Simulation results show that our method is able to provide fast convergence and handle efficiently a high number switching times.
@inproceedings{stellato2016b, author = {Stellato, B. and Ober-Bl\"{o}baum, S. and Goulart, P.}, title = {Optimal Control of Switching Times in Switched Linear Systems}, booktitle = {{IEEE} Conference on Decision and Control ({CDC})}, year = {2016}, pages = {7228--7233}, month = dec, groups = {switching time optimization}, pdf = {/assets/downloads/publications/2016/switchtimeopt2016.pdf}, url = {https://doi.org/10.1109/CDC.2016.7799384} } -
High-Speed Direct Model Predictive Control for Power ElectronicsEuropean Control Conference (ECC), pp. 129–134, Jul. 2016
Common approaches for direct model predictive control (MPC) for current reference tracking in power electronics suffer from the high computational complexity encountered when solving integer optimal control problems over long prediction horizons. We propose an efficient alternative method based on approximate dynamic programming, greatly reducing the computational burden and enabling sampling times under \(25\:μs\). Our approach is based on the offline minimization of an infinite horizon cost function estimate which is then applied to the tail cost of the MPC problem. This allows us to reduce the controller horizon to a very small number of stages improving overall controller performance. Our proposed algorithm is validated on a variable speed drive system with a three-level voltage source converter.
@inproceedings{stellato2016, author = {Stellato, B. and Goulart, P.}, title = {High-Speed Direct Model Predictive Control for Power Electronics}, booktitle = {European Control Conference ({ECC})}, year = {2016}, pages = {129--134}, month = jul, groups = {power electronics}, pdf = {/assets/downloads/publications/2016/pel_ecc2016.pdf}, url = {http://ieeexplore.ieee.org/document/7810275/} }
Theses
2017
-
Mixed-Integer Optimal Control of Fast Dynamical SystemsUniversity of Oxford, 2017
Many applications in engineering, computer science and economics involve mixed-integer optimal control problems. Solving these problems in real-time is a challenging task because of the explosion of integer combinations to evaluate. This thesis focuses on the development of new algorithms for mixed-integer programming with an emphasis on optimal control problems of fast dynamical systems with discrete controls. The first part proposes two reformulations to reduce the computational complexity. The first reformulation avoids integer variables altogether. By considering a sequence of switched dynamics, we analyze the switching time optimization problem. Even though it is a continuous smooth problem, it is non-convex and the cost function and derivatives are hard to compute. We develop a new efficient method to compute the cost function and its derivatives. Our technique brings up to two orders of magnitude speedups with respect to state-of-the-art tools. The second approach reduces the number of integer decisions. In hybrid model predictive control (MPC) the computational complexity grows exponentially with the horizon length. Using approximate dynamic programming (ADP) we reduce the horizon length while maintaining good control performance by approximating the tail cost offline. This approach allows, for the first time, the application of such control techniques to fast dynamical systems with sampling times of only a few microseconds. The second part investigates embedded branch-and-bound algorithms for mixed-integer quadratic programs (MIQPs). A core component of these methods is the solution of continuous quadratic programs (QPs). We develop OSQP, a new robust and efficient general-purpose QP solver based on the alternating direction method of multipliers (ADMM) and able, for the first time, to detect infeasible problems. We include OSQP into a custom branch-and-bound algorithm suitable for embedded systems. Our extension requires only a single matrix factorization and exploits warm-starting, thereby greatly reducing the number of ADMM iterations required. Numerical examples show that our algorithm solves small to medium scale MIQPs more quickly than commercial solvers.
@phdthesis{stellato2017d, author = {Stellato, B.}, title = {Mixed-Integer Optimal Control of Fast Dynamical Systems}, school = {University of Oxford}, year = {2017}, groups = {theses}, owner = {sidereus}, pdf = {/assets/downloads/publications/stellato_thesis.pdf}, url = {https://ora.ox.ac.uk/objects/uuid:b8a7323c-e36e-45ec-ae8d-6c9eb4350629}, timestamp = {2017.12.20} }
2014
-
Data-driven chance constrained optimizationETH Zürich, 2014
Traditional optimization methods for decison-making under uncertainty assume perfect model information. In practice, however, such precise knowledge is rarely available. Thus, optimal decisions coming from these approaches can be very sensitive to perturbations and unreliable. Stochastic optimization programs take into account uncertainty but are intractable in general and need to be approximated. Of late, distributionally robust optimization methods have shown to be powerful tools to reformulate stochastic programs in a tractable way. Moreover, the recent advent of cheap sensing devices has caused the explosion of available historical data, usually referred to as “Big Data”. Thus, modern optimization techniques are shifting from traditional methods to data-driven approaches. In this thesis, we derive data-driven tractable reformulations for stochastic optimization programs based on distributionally robust optimization. In the first part of this work we provide our theoretical contributions. New distributionally robust probability bounds are derived and used to reformulate uncertain optimization programs assuming limited information about the uncertainty. Then, we show how this information can be derived from historical data. In the second part of this work, we compare the developed methods to support vector machines in a machine learning setting and to randomized optimization and in a control context.
@mastersthesis{stellato2014, author = {Stellato, B.}, title = {Data-driven chance constrained optimization}, school = {ETH Z\"{u}rich}, year = {2014}, groups = {theses}, pdf = {/assets/downloads/publications/stellato_master_thesis.pdf}, url = {http://dx.doi.org/10.3929/ethz-a-010266857} }