Predictive Control for Linear and Hybrid Systems

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.