Optimization Online


Low-complexity method for hybrid MPC with local guarantees

Damian Frick (dafrick***at***control.ee.ethz.ch)
Angelos Georghiou (angelos.georghiou***at***mcgill.ca)
Juan L. Jerez (juanj***at***control.ee.ethz.ch)
Alexander Domahidi (domahidi***at***inspire.ethz.ch)
Manfred Morari (morari***at***control.ee.ethz.ch)

Abstract: Model predictive control problems for constrained hybrid systems are usually cast as mixed-integer optimization problems (MIP). However, commercial MIP solvers are designed to run on desktop computing platforms and are not suited for embedded applications which are typically restricted by limited computational power and memory. To alleviate these restrictions, we develop a novel low-complexity, iterative method for a class of non-convex, non-smooth optimization problems. This class of problems encompasses hybrid model predictive control problems where the dynamics are piece-wise affine (PWA). We give conditions such that the proposed algorithm has fixed points and show that, under practical assumptions, our method is guaranteed to converge locally to local minima. This is in contrast to other low-complexity methods in the literature, such as the non-convex alternating directions method of multipliers (ADMM), for which no such guarantees are known for this class of problems. By interpreting the PWA dynamics as a union of polyhedra we can exploit the problem structure and develop an algorithm based on operator splitting procedures. Our algorithm departs from the traditional MIP formulation, and leads to a simple, embeddable method that only requires matrix-vector multiplications and small-scale projections onto polyhedra. We illustrate the efficacy of the method on two numerical examples, achieving good closed-loop performance with computational times several orders of magnitude smaller compared to state-of-the-art MIP solvers. Moreover, it is competitive with ADMM in terms of suboptimality and computation time, but additionally provides local optimality and local convergence guarantees.

Keywords: Operator splitting, Hybrid model predictive control, Non-smooth and discontinuous problems, Iterative schemes

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Applications -- Science and Engineering (Control Applications )


Download: [PDF]

Entry Submitted: 09/09/2016
Entry Accepted: 09/09/2016
Entry Last Modified: 08/07/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society