The double description method for the approximation of explicit MPC control laws

A standard model predictive controller (MPC) can be written as a parametric optimization problem whose solution is a piecewise affine (PWA) map from the measured state to the optimal control input. The primary limitation of this optimal `explicit solution¿ is that the complexity can grow quickly with problem size, and so in this paper we seek to compute approximate explicit control laws that can trade-off complexity for approximation error. This computation is accomplished in a two-phase process: First, inner and outer polyhedral approximations of the the convex cost function of the parametric problem are computed with an algorithm based on an extension to the classic double-description method; a convex hull approach. The proposed method has two main advantages from a control point of view: it is an incremental approach, meaning that an approximation of any specified complexity can be produced and it operates on implicitly-defined convex sets, meaning that the optimal solution of the parametric problem is not required. In the second phase of the algorithm, a feasible approximate control law is computed that has the cost function derived in the first phase. For this purpose, a new interpolation method is introduced based on recent work on barycentric interpolation. The resulting control law is continuous, although non-linear and defined over a non-simplical polytopic partition of the state space. The non-simplical nature of the partition generates significantly simpler approximate control laws than current competing methods, as demonstrated on computational examples.