Publications
Papers listed by type and year of publication or year of submission if unpublished.
Preprints
In this paper, we present nonconvex exterior-point operator splitting algorithm (NExOS), a novel linearly convergent first-order algorithm tailored for constrained nonconvex learning problems. We consider the problem of minimizing a convex cost function over a nonconvex constraint set, where projection onto the constraint set is single-valued around points of interest. A wide range of nonconvex learning problems have this structure including (but not limited to) sparse and low-rank optimization problems. By exploiting the underlying geometry of the constraint set, NExOS finds a locally optimal point by solving a sequence of penalized problems with strictly decreasing penalty parameters. NExOS solves each penalized problem by applying an outer iteration operator splitting algorithm, which converges linearly to a local minimum of the corresponding penalized formulation under regularity conditions. Furthermore, the local minima of the penalized problems converge to a local minimum of the original problem as the penalty parameter goes to zero. We implement NExOS in the open-source Julia package NExOS.jl, which has been extensively tested on many instances from a wide variety of learning problems. We study several examples of well-known nonconvex learning problems, and we show that in spite of being general purpose, NExOS is able to compute high quality solutions very quickly and is competitive with specialized algorithms.
@article{dasgupta2020,
title={Exterior-point Operator Splitting for Nonconvex Learning},
abstract={In this paper, we present nonconvex exterior-point operator splitting algorithm (NExOS), a novel linearly convergent first-order algorithm tailored for constrained nonconvex learning problems. We consider the problem of minimizing a convex cost function over a nonconvex constraint set, where projection onto the constraint set is single-valued around points of interest. A wide range of nonconvex learning problems have this structure including (but not limited to) sparse and low-rank optimization problems. By exploiting the underlying geometry of the constraint set, NExOS finds a locally optimal point by solving a sequence of penalized problems with strictly decreasing penalty parameters. NExOS solves each penalized problem by applying an outer iteration operator splitting algorithm, which converges linearly to a local minimum of the corresponding penalized formulation under regularity conditions. Furthermore, the local minima of the penalized problems converge to a local minimum of the original problem as the penalty parameter goes to zero. We implement NExOS in the open-source Julia package NExOS.jl, which has been extensively tested on many instances from a wide variety of learning problems. We study several examples of well-known nonconvex learning problems, and we show that in spite of being general purpose, NExOS is able to compute high quality solutions very quickly and is competitive with specialized algorithms.},
author={Das Gupta, S. and Stellato, B. and Van Parys, B. P. G.},
journal = {arXiv e-prints},
archivePrefix = {arXiv},
year={2020},
eprint={2011.04552},
url={https://arxiv.org/abs/2011.04552},
pdf={https://arxiv.org/pdf/2011.04552.pdf},
month={11},
code={https://github.com/Shuvomoy/NExOS.jl}
}The COVID-19 pandemic has created unprecedented challenges worldwide. Strained healthcare providers make difficult decisions on patient triage, treatment and care management on a daily basis. Policy makers have imposed social distancing measures to slow the disease, at a steep economic price. We design analytical tools to support these decisions and combat the pandemic. Specifically, we propose a comprehensive data-driven approach to understand the clinical characteristics of COVID-19, predict its mortality, forecast its evolution, and ultimately alleviate its impact. By leveraging cohort-level clinical data, patient-level hospital data, and census-level epidemiological data, we develop an integrated four-step approach, combining descriptive, predictive and prescriptive analytics. First, we aggregate hundreds of clinical studies into the most comprehensive database on COVID-19 to paint a new macroscopic picture of the disease. Second, we build personalized calculators to predict the risk of infection and mortality as a function of demographics, symptoms, comorbidities, and lab values. Third, we develop a novel epidemiological model to project the pandemic\textquoterights spread and inform social distancing policies. Fourth, we propose an optimization model to reallocate ventilators and alleviate shortages. Our results have been used at the clinical level by several hospitals to triage patients, guide care management, plan ICU capacity, and re-distribute ventilators. At the policy level, they are currently supporting safe back-to-work policies at a major institution and equitable vaccine distribution planning at a major pharmaceutical company, and have been integrated into the US Center for Disease Control's pandemic forecast.
@article {Bertsimas2020.06.26.20141127,
author = {Bertsimas, D. and Boussioux, L. and Cory Wright, R. and Delarue, A. and Digalakis, V. and Jacquillat, A. and Lahlou Kitane, D. and Lukin, G. and Li, M. L. and Mingardi, L. and Nohadani, O. and Orfanoudaki, A. and Papalexopoulos, T. and Paskov, I. and Pauphilet, J. and Skali Lami, O. and Stellato, B. and Tazi Bouardi, H. and Villalobos Carballo, K. and Wiberg, H. and Zeng, C.},
title = {From predictions to prescriptions: A data-driven response to COVID-19},
year = {2020},
doi = {10.1101/2020.06.26.20141127},
publisher = {Cold Spring Harbor Laboratory Press},
url = {https://www.medrxiv.org/content/early/2020/06/29/2020.06.26.20141127},
pdf = {https://www.medrxiv.org/content/early/2020/06/29/2020.06.26.20141127.full.pdf},
journal = {Health Care Management Science (to appear)},
eprint = {2020.06.26.20141127},
code={https://covidanalytics.io},
month = {12},
abstract = {The COVID-19 pandemic has created unprecedented challenges worldwide. Strained healthcare providers make difficult decisions on patient triage, treatment and care management on a daily basis. Policy makers have imposed social distancing measures to slow the disease, at a steep economic price. We design analytical tools to support these decisions and combat the pandemic. Specifically, we propose a comprehensive data-driven approach to understand the clinical characteristics of COVID-19, predict its mortality, forecast its evolution, and ultimately alleviate its impact. By leveraging cohort-level clinical data, patient-level hospital data, and census-level epidemiological data, we develop an integrated four-step approach, combining descriptive, predictive and prescriptive analytics. First, we aggregate hundreds of clinical studies into the most comprehensive database on COVID-19 to paint a new macroscopic picture of the disease. Second, we build personalized calculators to predict the risk of infection and mortality as a function of demographics, symptoms, comorbidities, and lab values. Third, we develop a novel epidemiological model to project the pandemic{\textquoteright}s spread and inform social distancing policies. Fourth, we propose an optimization model to reallocate ventilators and alleviate shortages. Our results have been used at the clinical level by several hospitals to triage patients, guide care management, plan ICU capacity, and re-distribute ventilators. At the policy level, they are currently supporting safe back-to-work policies at a major institution and equitable vaccine distribution planning at a major pharmaceutical company, and have been integrated into the US Center for Disease Control's pandemic forecast.},
prize = {INFORMS Health Applications Society Pierskalla Best Paper Award},
prize_link = {https://www.informs.org/Recognizing-Excellence/Community-Prizes/Health-Applications-Society/Pierskalla-Best-Paper-Award}
}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 = {arXiv e-prints},
year = {2019},
month = {July},
abstract = {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.},
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},
}Journal articles
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{bertsimas2021,
author = {{Bertsimas}, D. and {Stellato}, B.},
title = {The Voice of Optimization},
journal = {Machine Learning},
year = {2021},
month = {Feb},
abstract = {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.},
volume = {110},
issue = {2},
pages = {249--277},
pdf = {https://arxiv.org/pdf/1812.09991.pdf},
url = {https://doi.org/10.1007/s10994-020-05893-5},
code = {https://github.com/bstellato/mlopt}
}Background: Timely identification of COVID-19 patients at high risk of mortality can significantly improve patient management and resource allocation within hospitals. This study seeks to develop and validate a data-driven personalized mortality risk calculator for hospitalized COVID-19 patients. Methods: De-identified data was obtained for 3,927 COVID-19 positive patients from six independent centers, comprising 33 different hospitals. Demographic, clinical, and laboratory variables were collected at hospital admission. The COVID-19 Mortality Risk (CMR) tool was developed using the XGBoost algorithm to predict mortality. Its discrimination performance was subsequently evaluated on three validation cohorts. Findings: The derivation cohort of 3,062 patients has an observed mortality rate of 26.84%. Increased age, decreased oxygen saturation (<= 93%), elevated levels of C-reactive protein (>= 130 mg/L), blood urea nitrogen (>= 18 mg/dL), and blood creatinine (>= 1.2 mg/dL) were identified as primary risk factors, validating clinical findings. The model obtains out-of-sample AUCs of 0.90 (95% CI, 0.87-0.94) on the derivation cohort. In the validation cohorts, the model obtains AUCs of 0.92 (95% CI, 0.88-0.95) on Seville patients, 0.87 (95% CI, 0.84-0.91) on Hellenic COVID-19 Study Group patients, and 0.81 (95% CI, 0.76-0.85) on Hartford Hospital patients. The CMR tool is available as an online application at covidanalytics.io/mortality_calculator and is currently in clinical use. Interpretation: The CMR model leverages machine learning to generate accurate mortality predictions using commonly available clinical features. This is the first risk score trained and validated on a cohort of COVID-19 patients from Europe and the United States.
@article{Bertsimas2020.07.07.20148304,
author = {Bertsimas, D. and Lukin, G. and Mingardi, L. and Nohadani, O. and Orfanoudaki, A. and Stellato, B. and Wiberg, H. and Gonzalez-Garcia, S. and Parra-Calderon, C. L. and Robinson, K. and Schneider, M. and Stein, B. and Estirado, A. and a Beccara, L. and Canino, R. and Dal Bello, M. and Pezzetti, F. and Pan, A.},
title = {COVID-19 Mortality Risk Assessment: An International Multi-Center Study},
journal = {PLOS One},
month = {12},
year = {2020},
doi = {https://doi.org/10.1371/journal.pone.0243262},
abstract = {Background: Timely identification of COVID-19 patients at high risk of mortality can significantly improve patient management and resource allocation within hospitals. This study seeks to develop and validate a data-driven personalized mortality risk calculator for hospitalized COVID-19 patients. Methods: De-identified data was obtained for 3,927 COVID-19 positive patients from six independent centers, comprising 33 different hospitals. Demographic, clinical, and laboratory variables were collected at hospital admission. The COVID-19 Mortality Risk (CMR) tool was developed using the XGBoost algorithm to predict mortality. Its discrimination performance was subsequently evaluated on three validation cohorts. Findings: The derivation cohort of 3,062 patients has an observed mortality rate of 26.84\%. Increased age, decreased oxygen saturation (<= 93\%), elevated levels of C-reactive protein (>= 130 mg/L), blood urea nitrogen (>= 18 mg/dL), and blood creatinine (>= 1.2 mg/dL) were identified as primary risk factors, validating clinical findings. The model obtains out-of-sample AUCs of 0.90 (95\% CI, 0.87-0.94) on the derivation cohort. In the validation cohorts, the model obtains AUCs of 0.92 (95\% CI, 0.88-0.95) on Seville patients, 0.87 (95\% CI, 0.84-0.91) on Hellenic COVID-19 Study Group patients, and 0.81 (95\% CI, 0.76-0.85) on Hartford Hospital patients. The CMR tool is available as an online application at covidanalytics.io/mortality_calculator and is currently in clinical use. Interpretation: The CMR model leverages machine learning to generate accurate mortality predictions using commonly available clinical features. This is the first risk score trained and validated on a cohort of COVID-19 patients from Europe and the United States.},
url = {https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0243262},
pdf = {https://www.medrxiv.org/content/early/2020/07/19/2020.07.07.20148304.full.pdf}
}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},
volume = {12},
number = {4},
pages = {637--672},
year = {2020},
month = {October},
abstract = {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.},
code = {https://osqp.org},
pdf = {https://arxiv.org/pdf/1711.08013.pdf},
url = {https://doi.org/10.1007/s12532-020-00179-2},
prize = {2020 Mathematical Programming Computation Best Paper Award},
prize_link = {http://mpc.zib.de/}
}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},
abstract = {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.},
pdf = {https://stanford.edu/~boyd/papers/pdf/admm_infeas.pdf},
url = {https://link.springer.com/article/10.1007%2Fs10957-019-01575-y},
}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\: \mu 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\: \mu s\) are required to run our algorithm for horizon $N=1$ and \(17.27\: \mu 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},
abstract = {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\: \mu 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\: \mu s\) are required to run our algorithm for horizon $N=1$ and \(17.27\: \mu 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.},
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/},
pdf = {http://arxiv.org/pdf/1510.05578.pdf},
url = {http://dx.doi.org/10.1109/TPEL.2016.2584678},
}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\"obaum, 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 = {October},
issn = {0018-9286},
abstract = {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.},
code = {https://github.com/oxfordcontrol/SwitchTimeOpt.jl},
doi = {10.1109/TAC.2017.2697681},
pdf = {http://arxiv.org/pdf/1608.08597.pdf},
url = {https://doi.org/10.1109/TAC.2017.2697681},
}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},
abstract = {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.},
pdf = {http://arxiv.org/pdf/1509.08398.pdf},
url = {http://dx.doi.org/10.1080/00031305.2016.1186559},
}Conference proceedings
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.
@inproceedings{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.},
abstract = {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.},
booktitle = {{IEEE} Conference on Decision and Control ({CDC})},
year = {2020},
month = {12},
url = {https://arxiv.org/abs/2004.03736},
pdf = {https://arxiv.org/pdf/2004.03736.pdf},
code = {https://github.com/StanfordASL/coco},
}Mixed-integer convex programming (MICP) is a popular modeling framework for solving discrete and combinatorial optimization problems arising in various settings. Despite advances in efficient solvers for numerical optimization problems, MICPs remain challenging to solve for real-time control in applications requiring solution rates of 10-100Hz. Seeking to bridge this gap, we present an approach that leverages results from supervised learning and parametric programming to quickly solve for feasible solutions to MICPs. This approach consists of (1) an offline phase where a classifier is trained on a codebook consisting of solved MICPs and (2) an online step where the network yields candidate strategies given a new set of problem parameters. Unlike other data-driven approaches for solving MICPs, we show that our approach can tackle a broad category of problems that can be modeled as MICPs and how our framework can handle problems with a different number of discrete decision variables than the problems in the training set. Finally, we demonstrate the efficacy of our proposed approach through numerical experiments showing improved solution times and optimality compared to existing approaches for solving MICPs.
@inproceedings{anonymous2020coco,
title={CoCo: Learning Strategies for Online Mixed-Integer Control},
author={Cauligi, A. and Culbertson, P. and Stellato, B. and Schwager, M. and Pavone, M.},
booktitle={Learning Meets Combinatorial Algorithms at NeurIPS2020},
month = {Dec},
year={2020},
url={https://openreview.net/forum?id=51goIqq88gF},
code = {https://github.com/StanfordASL/coco},
pdf = {https://openreview.net/pdf?id=51goIqq88gF},
abstract = {Mixed-integer convex programming (MICP) is a popular modeling framework for solving discrete and combinatorial optimization problems arising in various settings. Despite advances in efficient solvers for numerical optimization problems, MICPs remain challenging to solve for real-time control in applications requiring solution rates of 10-100Hz. Seeking to bridge this gap, we present an approach that leverages results from supervised learning and parametric programming to quickly solve for feasible solutions to MICPs. This approach consists of (1) an offline phase where a classifier is trained on a codebook consisting of solved MICPs and (2) an online step where the network yields candidate strategies given a new set of problem parameters. Unlike other data-driven approaches for solving MICPs, we show that our approach can tackle a broad category of problems that can be modeled as MICPs and how our framework can handle problems with a different number of discrete decision variables than the problems in the training set. Finally, we demonstrate the efficacy of our proposed approach through numerical experiments showing improved solution times and optimality compared to existing approaches for solving MICPs.},
}Many control policies used in applications compute 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 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 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 program with respect to its parameters. A longer version of this paper, which illustrates our method on many examples, is available at https://web.stanford.edu/ boyd/papers/learning_cocps.html.
@InProceedings{pmlr-v120-agrawal20a,
title = {Learning Convex Optimization Control Policies},
author = {Agrawal, A. and Barratt, S. and Boyd, S. and Stellato, B.},
booktitle = {Proceedings of the 2nd Conference on Learning for Dynamics and Control},
pages = {361--373},
year = {2020},
volume = {120},
series = {Proceedings of Machine Learning Research},
month = {Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v120/agrawal20a/agrawal20a.pdf},
url = {http://proceedings.mlr.press/v120/agrawal20a.html},
abstract = {Many control policies used in applications compute 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 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 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 program with respect to its parameters. A longer version of this paper, which illustrates our method on many examples, is available at https://web.stanford.edu/ boyd/papers/learning_cocps.html.},
code = {https://github.com/cvxgrp/cocp}
}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 = {July},
abstract = {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.},
pdf = {/downloads/publications/2018/miosqp_ecc.pdf},
}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 = {December},
abstract = {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.},
pdf = {https://stanford.edu/~boyd/papers/pdf/osqp_embedded.pdf},
url = {https://ieeexplore.ieee.org/document/8263928},
code = {https://github.com/oxfordcontrol/osqp_codegen_benchmarks},
}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\:\mu 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\:\mu s\) are required to run our algorithm for horizon \(N=1\) and \(17.27\:\mu 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 = {December},
abstract = {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\:\mu 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\:\mu s\) are required to run our algorithm for horizon \(N=1\) and \(17.27\:\mu 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.},
pdf = {/downloads/publications/2016/pels_cdc2016.pdf},
url = {https://doi.org/10.1109/CDC.2016.7798474},
}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 = {December},
abstract = {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.},
pdf = {/downloads/publications/2016/switchtimeopt2016.pdf},
url = {https://doi.org/10.1109/CDC.2016.7799384},
}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\:\mu 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 = {July},
abstract = {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\:\mu 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.},
pdf = {/downloads/publications/2016/pel_ecc2016.pdf},
url = {http://ieeexplore.ieee.org/document/7810275/},
}Theses
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},
abstract = {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.},
pdf = {/downloads/publications/stellato_thesis.pdf},
url = {https://ora.ox.ac.uk/objects/uuid:b8a7323c-e36e-45ec-ae8d-6c9eb4350629},
}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},
abstract = {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.},
pdf = {/downloads/publications/stellato_master_thesis.pdf},
url = {http://dx.doi.org/10.3929/ethz-a-010266857},
}