Splitting algorithms: efficient lightweight solvers for real-time embedded nonlinear MPC

Model predictive control (MPC) has become a popular strategy to implement feedback control loops for a variety of systems. Since most systems are nonlinearby nature, nonlinear MPC (NMPC) offers a more accurate modeling than linear MPC, but it leads to nonconvex and much more complicated problems. At every sampling step, NMPC requires the solution of a nonlinear program (NLP) that has to be computed within sampling time, thus imposing an imperative demand for algorithmic speed and efficiency.

A usual approach to this type of problems is sequential quadratic programming (SQP), which requires the solution of a quadratic program at every iteration and, consequently, inner iterative procedures. As a result, each outer iteration may become computationally very expensive. This constitute a severe drawback for all those applications in which the solver is embedded on a simple platform with low memory and limited computational power. On the contrary, "splitting algorithms" such as the proximal (projected) gradient typically involve elementary operations and negligible memory allocation, but are extremely sensitive to problem conditioning and may require prohibitively many iterations before converging to a satisfactory solution.

In this talk we combine basic favorable properties of the forward-backward envelope (FBE) to design a globally convergent, fast, and lightweight algorithm perfectly suited for embedded applications. The algorithm, named PANOC (Proximal Averaged Newton method for Optimal Control), is of linesearch type and combines the global convergence of the projected gradient method with the fast local behavior of L-BFGS-type directions, yet maintaining the operational simplicity of the former method. Unlike classical linesearch methods, it does not require differentiability assumptions nor is it limited to "descent directions", and thus differs substantially from early FBE-based minimization algorithms. The proposed methodology is validated on a lab-scale vehicle that has to autonomously move in an obstructed environment to a reference position. Numerical results show that PANOC can be up to two orders of magnitude faster than interior point and SQP-based solvers, as well as previous FBE-based minimization algorithms operating a classical linesearch.

Bio:
Andreas Themelis is a postdoctoral researcher at the Department of Electrical Engineering (ESAT) of KU Leuven, Belgium, since January 2019. AGer obtaining MSc and BSc degrees in MathemaJcs from the University of Florence (Italy), he received a joint PhD degree in Electrical Engineering from KU Leuven (Belgium) and in Control, Decision and System Sciences from IMT Lucca (Italy) in December 2018. His research focuses on the convergence analysis and Newton-type acceleraJon of spliUng algorithms for nonsmooth and nonconvex problems, aiming at developing high-level compeJJve algorithms with low computaJonal and memory requirements that can run on simple plaXorms and are thus well suited for embedded applicaJons.