In previous chapters we have shown how to compute the solution to constrained finite time optimal control problems. Two approaches can be used. The first approach consists of solving a mathematical program for a given initial state. The second approach employs multiparametric programming to compute the solution as an explicit piecewise affine function of the initial state. This implies that for constrained linear systems, a Receding Horizon Control (RHC) policy requires either the on-line solution of a quadratic or linear program, or the evaluation of a piecewise affine on polyhedra function.

In this chapter we focus on efficient on-line methods for the computation of RHC control laws. The main drawback of explicit optimal control laws is that the number of polyhedral regions can grow exponentially with the number of constraints in the optimal control problem. Section 14.1 presents efficient on-line methods for the evaluation of explicit piecewise affine control laws.

If the on-line solution of a quadratic or linear program is preferred, Sections 14.2 and 14.3 briefly discuss how to improve the efficiency of a mathematical programming solver by exploiting the structure of the RHC control problem.

Storage and On-Line Evaluation of the PWA Control Law

In Chapter 11 we have shown how to compute the solution to the constrained finite time optimal control (CFTOC) problem as an explicit piecewise affine function of the initial state. Such a function is computed off-line by using a multiparametric program solver, which divides the state space into polyhedral regions, and for each region determines the linear gain and offset which produces the optimal control action.

This method reveals its effectiveness when applied to Receding Horizon Control (RHC). Having a precomputed solution as an explicit piecewise affine on polyhedra (PPWA) function of the state vector reduces the on-line computation of the RHC control law to a function evaluation, therefore avoiding the on-line solution of a quadratic or linear program.

The main drawback of such an explicit optimal control law is that the number of polyhedral regions can grow dramatically with the number of constraints in the optimal control problem. In this chapter we focus on efficient on-line methods for the evaluation of such a piecewise affine control law.

The operations research community has addressed parameter variations in mathematical programs at two levels: sensitivity analysis, which characterizes the change of the solution with respect to small perturbations of the parameters, and parametric programming, where the characterization of the solution for a full range of parameter values is studied. In this chapter we introduce the concept of multiparametric programming and recall the main results of nonlinear multiparametric programming. The main goal is to make the reader aware of the complexities of general multiparametric nonlinear programming. Later in this book we will use multiparametric programming to characterize and compute the state feedback solution of optimal control problems. There we will only make use of Corollary 5.1 for multiparametric linear programs and Corollary 5.2 for multiparametric quadratic programs, which show that these specific programs are “well behaved.”

Introduction to Multiparametric Programs

Consider the mathematical program

where z is the optimization vector and x is a vector of parameters.We are interested in studying the behavior of the value function J*(x) and the optimizer z*(x) as we vary the parameter x. Mathematical programs where x is a scalar are referred to as parametric programs, while programs where x is a vector are referred to as multiparametric programs.

There are several reasons to look for efficient solvers of multiparametric programs. Typically, mathematical programs are affected by uncertainties due to factors that are either unknown or that will be decided later. Parametric programming systematically subdivides the space of parameters into characteristic regions, which depict the feasibility and corresponding performance as a function of the uncertain parameters, and hence provide the decision maker with a complete map of various outcomes.

Our interest in multiparametric programming arises from the field of system theory and optimal control. For example, for discrete-time dynamical systems, finite time constrained optimal control problems can be formulated as mathematical programs where the cost function and the constraints are functions of the initial state of the dynamical system. In particular, Zadeh and Whalen [293] appear to have been the first ones to express the optimal control problem for constrained discrete-time linear systems as a linear program. We can interpret the initial state as a parameter. By using multiparametric programming we can characterize and compute the solution of the optimal control problem explicitly as a function of the initial state.