Min –max model predictive control as a quadratic program D. Mun˜oz de la Pen˜a, T. Alamo, D.R. Ramı´rez and E.F. Camacho Abstract: The implementation of min– max model predictive control for constrained linear systems with bounded additive uncertainties and quadratic cost functions is dealt with. This type of controller has been shown to be a continuous piecewise affine function of the state vector by geometrical methods. However, no algorithm for computing the explicit solution has been given. Here, it is shown that the min – max optimisation problem can be expressed as a multiparametric quadratic program, and so, the explicit form of the controller may be determined by standard multi-parametric techniques.
1
Introduction
Model predictive control (MPC) is one of the control techniques that is able to cope with model uncertainties in an explicit way [1]. One approach used in MPC when uncertainties are present is to minimise the objective function for the worst possible case. This strategy is known as min –max and was originally proposed by Witsenhausen [2] in the context of robust receding control and in Campo and Morari [3] in the context of robust MPC. In this paper, we consider bounded additive uncertainties. For other approaches, the readers are referred to various studies [4– 7 and references therein]. Min – max MPC schemes can be classified into open-loop and feedback min – max controllers. Feedback min– max MPC obtains a sequence of feedback control laws that minimises the worst-case cost, while assuring robust constraint handling. It requires the solution of a very high-dimensional problem that makes its practical implementation very hard [8]. For cost functions based on k.k1 and k.k1 norm, the explicit solution has been obtained [7, 9]. This result has not been extended to quadratic cost functions, although approximate solutions have been given under a stochastic approach in Sakizlis et al. [10]. Open-loop min –max MPC obtains a single control input sequence that minimises the worst-case cost [2, 11]. This formulation is conservative and underestimates the set of feasible input trajectories. The solution proposed in the literature is to minimise a sequence of control corrections efforts to a given linear feedback stabilising control law for the nominal plant. In this way, some kind of feedback is introduced in the prediction without increasing the computational effort [12, 13]. In this paper, we consider the constrained open-loop min – max MPC with linear feedback control law and quadratic cost functions. For these controllers, the size of the optimisation problem depends exponentially on the # The Institution of Engineering and Technology 2006 doi:10.1049/iet-cta:20060016 Paper first received 10th January and in revised form 24th April 2006 The authors are with the Departamento de Ingenierı´a de Sistemas y Automa´tica, Universidad de Sevilla, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain
prediction horizon. The piecewise linearity of this class of min – max MPC has been proved by the authors using geometrical methods in Ramirez and Camacho [14] and heuristic algorithms to compute the solution have been given in Muno˜z de la Pen˜a et al. [15, 16]. In this paper, we show that the min– max optimisation problem can be expressed as a multi-parametric quadratic program (mpQP) problem, so the explicit form of the controller may be determined by standard multi-parametric techniques. Recently, a method for obtaining approximated solutions for constrained nonlinear systems has been proposed by Grancharora and Johansen [17].
2
Problem formulation
Consider the discrete time-invariant linear system with bounded uncertainties xkþ1 ¼ Axk þ Buk þ Dwk
ð1Þ
where xk [ Rnx is the state, uk [ Rnu the control input and wk [ Rnw the uncertainty that is supposed to be bounded, that, is wk [ W, where W is a closed polyhedron that contains the origin. Open-loop min– max MPC obtains a single control input sequence that minimises the worst-case cost [3]. This formulation is conservative and underestimates the set of feasible input trajectories. One solution proposed in the literature is to minimise a sequence of control corrections efforts to a given linear feedback stabilising control law for the nominal plant. In this way, some kind of feedback is introduced in the prediction equation without increasing the computational effort [12, 13]. The control input is given by uk ¼ Kxk þ vk , where K is chosen in order to achieve some desired property for the non-constrained problem such as stability or LQR optimality. The MPC controller will compute the optimal sequence of correction control inputs vk . The dynamics of the system can be rewritten as xkþ1 ¼ AK xk þ Bvk þ Dwk
E-mail:
[email protected]
AK ¼ ðA þ BKÞ
328
IET Control Theory Appl., Vol. 1, No. 1, January 2007
For the system described (i.e. linear systems and additive uncertainties), it is possible to reduce the number of constraints defining the feasible set SF . It can be seen that definition (5) is equivalent to
The objective function is defined as V ðx; v; wÞ ¼
N 1 X
½xj ðx; v; wÞT Qxj ðx; v; wÞ
j¼0
þ uj ðx; v; wÞT Ruj ðx; v; wÞ
SF ¼ fðx; vÞjFx þ Gv dg
þ xN ðx; v; wÞT PxN ðx; v; wÞ
where d is a vector such that its ith entry satisfies di ¼ mi þ minw[WN Miw, and mi and Mi are the ith element and row of vector m and matrix M, respectively. The cost function, V(x, v, w), is a quadratic function of x, v and w. That is, taking into account (2), matrices Hx , Hv and Hw can be found [1] in such a way that
with Q 0, P 0 and R . 0. T ]T The initial state is x0 ¼ x. Vector v ¼ [vT0 , vT1 , . . . , vN21 is the sequence of correction control inputs, and T w ¼ [wT0 , wT1 , . . . , wN21 ]T represents a possible sequence of input disturbances to the system. Variables xj (x, v, w) and uj (x, v, w) are the predicted state and control input, respectively, and are given by xj ðx; v; wÞ ¼ AKj x þ
j X
AKi1 Bvji þ
i¼1
j X
AKi1 Dwji
i¼1
ð2Þ
uj ðx; v; wÞ ¼ Kxj ðx; v; wÞ þ vj We consider state and input constraints xk (x, v, w) [ X and uk (x, v, w) [ U, where X and U are polyhedral sets. In order to achieve stability, a polyhedral terminal region constraint, xN (x, v, w) [ V, will also be taken into account. Note that, in this formulation, any time-varying linear constraint can be taken into account, as, for example, operational constraints of the form
V ðx; v; wÞ ¼ kH x x þ H v v þ H w wk22 Function V(x, v, w) is convex in w, thus the maximum will be attained at least at one of the vertices wi of the polyhedron WN [18, Theorem 3.4.6]. The maximiser may not be unique and the maximum can also be attained at another vector w Ver(WN), where Ver(WN) is the set of vertices of WN . However, the maximum is unique and that is what is needed to solve the inner maximisation problem (the maximiser is indeed irrelevant). This way, the maximum can be obtained evaluating the cost function at the set of vertices of the polyhedron WN , denoted by V (WN). We conclude that PN (x) can be rewritten as J ðxÞ ¼ min max kH x x þ H v v þ H w wk22 v
s.t. Fx þ Gv d
Ok uk ðx; v; wÞ Lk xk ðx; v; wÞ þ ok For simplicity of the notation, only state and input constraints are considered. The min – max constrained predictive controller results in the solution of the following optimisation problem denoted by P(x) J ðxÞ ¼ min max V ðx; v; wÞ v
w[WN
subject to xj ðx; v; wÞ [ X ;
ð3Þ
8w [ WN ; j ¼ 1; . . . ; N
xN ðx; v; wÞ [ V;
8w [ WN
uj ðx; v; wÞ [ U ;
8w [ WN ; j ¼ 0; . . . ; N 1 ð4Þ
where WN # RNnw denotes the set of possible disturbance sequences of length N WN ¼ W W W where denotes the cartesian product. This optimisation problem is solved at each sample instant. An optimal vector of control correction signals v (x) is obtained [i.e. the optimiser to (3) and (4)] and the control input u0(x) ¼ Kx þ v0 (x) ¼ KMPC(x) is applied. All this is done in a receding horizon manner [1]. 2.1
In order to implement the proposed controller, problem (3) subject to constraints (4) has to be solved at each sampling time. Let us define the feasible set SF as the pairs (x, v) which satisfy constraints (4). Taking into account (2), as X and U are polyhedral regions, matrices F, G, m and M can be found [1] such that the feasible set SF can be expressed as
IET Control Theory Appl., Vol. 1, No. 1, January 2007
ð6Þ
The complexity of this optimisation problem is very high. The max function is convex but its evaluation requires the computation of the cost function for each possible vertex of WN . The number of these vertices depends exponentially with the prediction horizon N. 3
Min– max as an mpQP
It has been shown by geometrical methods [14] that a min – max MPC with a quadratic objective function and linear constraints turns out to be a piecewise affine function of the state. We show in this section that the min– max problem (3) can be expressed as an mpQP problem and that the explicit min – max MPC controller can be obtained using multi-parametric techniques. If V(x, v, 0) (the part of the cost function that does not depend on the uncertainty) is added and subtracted from the cost function V(x, v, w), the min– max problem can be expressed as J ðxÞ ¼ min V ðx; v; 0Þ þ g v;g
subject to Fx þ Gv d
g V ðx; v; wÞ V ðx; v; 0Þ;
8w [ VðWN Þ
with
Min – max MPC computation
SF ¼ fðx; vÞjFx þ Gv m þ Mw; 8w [ WN g
w[VðWN Þ
ð5Þ
V ðx; v; wÞ V ðx; v; 0Þ ¼ wT H Tw H w w þ 2wT H Tw ðH x x þ H v vÞ These constraints are all affine on x and v; however, it is important to remark that each one of them is defined by a different gain on v that depends on the the vertex (2wTHTw Hv), so they cannot be reduced in the same way as constraints (4) (although standard constraint reduction techniques may be applied). 329
In order to obtain an equivalent problem in which the functional does not depend on the state vector, we introduce the following variable change z W v þ ½H Tv H v 1 H Tv H x x then, the min– max problem defined in (3), P(x), is equivalent to J ðxÞ ¼ xT Yx þ min z;g
1 T z Hz þ g 2
subject to G m z þ gm g Wm þ S m x G c z Wc þ S c x
ð7Þ ð8Þ ð9Þ
The positive definiteness of R implies that H is positive definite (H ¼ 2HTv Hv 0) [19]. The linear inequalities described by matrices Gm , gm , Wm and Sm correspond to the maximisation of the functional. The number of these inequalities, as the number of possible vertices, is exponential with the prediction horizon N. The inequalities defined by Gc , Wc and Sc represent the robust constraints of the problem. The matrices that define (7), (8) and (9) can be obtained from the problem parameters as follows H ¼ 2H Tv H v Constraints (9) are defined by the following matrices G c ¼ F;
Wc ¼ d
S c ¼ ½G F½H Tv H v 1 H Tv H x For each vertex wi of WN , a different linear constraint is defined. These constraints define (8) as follows eTi G m
¼
eTi gm
¼ 1
eTi Wm
2wTi H Tw H v
¼ wTi H Tw H w wi
eTi S m ¼ 2wTi H Tw ½I H v ½H Tv H v 1 H v H x where ei is the ith column of the identity matrix of appropriate dimension. It is important to note that the functional is still strictly convex because H 0 and g is the maximum of a set of linear functions. Thus that the optimisation problem has a unique optimiser z , g and dual degeneracy cannot take place [18]. Also, in the optimum, there is always at least one constraint out of Gm , gm , Wm and Sm that is satisfied in a tight way, that is, satisfied with the equality sign, because for any input correction trajectory v, there is at least one vertex where the function takes the maximum value for all possible uncertainties. 3.1
Explicit solution
The explicit solution v (x) of an mpQP problem is characterised by a partition of the feasible set of states SF into a set of regions denoted by CRi . Each region has a corresponding affine function of the state [ CRi ¼ SF v ðxÞ ¼ Ki x þ qi 8x [ CRi ; This piecewise affine function satisfies v ðxÞ ¼ arg min max V ðx; v; wÞ v
w[WN
subject to (4). Using this explicit form, it is possible to implement KMPC(x) in a very efficient manner. 330
The active vertex constraints set of a solution defines the vertices in which the max function attains the maximum, whereas the active constraints set defines the constraints of P(x) which are satisfied in a tight way for the optimal solution in a given state vector. mpQP problems have been studied in the literature in the MPC context [19– 21]. However, the mpQP problem addressed in those references is different from the one posed in min – max MPC. The mpQP problem posed in a nominal MPC controller is defined by a definite positive matrix, and therefore invertible. In min– max MPC, the auxiliary variable g does not take part in the quadratic cost and so the resulting matrix is not invertible. Further results on multi-parametric programming are able to deal with this particular type of problem. Algorithms that are able to deal with semi-definite positive mpQP programs have been presented in Tøndel et al. [22] and Spjøtvold et al. [23]. The reader is referred to these works for details on multi-parametric algorithms to obtain the explicit solution of the min –max problem. Remark 1: Degeneracy is a key issue in multi-parametric optimisation. Although primal degeneracy (when the vector of Lagrange multipliers of the optimal solution is not unique) must be taken into account, dual degeneracy (when the optimiser is not unique) cannot occur in min– max problems, as in the case of general mpQP problems with semi-definite positive quadratic matrices [22]. As pointed out before, these problems are strictly convex. This means that the solver does not need to take into account this degenerate situation. 3.2
Complexity
The complexity (i.e. the number of regions) of the explicit solution of an mpQP problem depends on the dimension of the state variable, the degrees of freedom and the number of constraints. The resulting optimisation problem has an exponential number of constraints with the prediction horizon. This fact makes finding the solution, in general, a hard problem. However, as pointed out in Alamo et al. [24], not all possible vertices are implied in the solution. In the aforementioned work, a vertex rejection algorithm is provided which defines a set of vertices C which satisfies max V ðx; v; wÞ ¼ max V ðx; v; wÞ
w[verWN
Table 1: N
w[C
Simulation results nx
nu
nw
Ver
Nrej
Reg
2
2
1
1
4
4
8
4
2
1
1
16
14
33
6
2
1
1
64
38
66
8
2
1
1
256
139
54
2
3
1
1
4
4
106
4
3
1
1
16
12
159
6
3
1
1
64
45
159
7
3
1
1
128
98
362
8
3
1
1
256
101
336
2
4
2
2
16
14
392
3
4
2
2
64
45
1114
4
4
2
2
256
140
2231
5
4
2
2
512
165
3431
IET Control Theory Appl., Vol. 1, No. 1, January 2007
Simulation for diferent uncertainties
N=1
6
10
8
6
4
I=2 A = 10
I=1 A = 10
4
2 I=1 A=[ ]
x2
x2
2
0
0
I=2 A=[ ] −2
−2 −4
−6
I=2 A=9
I=1 A=9
−4
−8
−10 −10
−8
−6
−4
−2
0 x1
2
4
6
8
−6 −10
10
−8
−6
−4
−2
a
0 x1
2
4
6
8
10
b
10
8
8
x1
6
6
x2
4
4
2
2
State trajectory
x2
N=3 10
0 −2
0 −2
−4
−4
−6
−6
−8
−8
−10 −10
−8
−6
−4
−2
0 x1
2
4
6
8
−10
10
0
5
10
15
c
20 Time step k
25
30
35
40
25
30
35
40
d
N=5 10 8
1
6
0.8
4
0.6 0.4 0.2
0
uk
x2
2
0 −2 −0.2 −4 −0.4 −6 −0.6 −8 −10 −10
−0.8 −8
−6
−4
−2
0 x1
2
4
6
8
10
e
−1 0
5
10
15
20 Time step k
f
Fig. 1 State space partition of the min –max controller of system (10) for prediction horizons N ¼ 1, 3, 5 (a, c, e) and closed loop trajectories with a controller with a prediction horizon N ¼ 8 for different values of a constant disturbance wk ( b, d, f )
Although vertex rejection efficiency depends greatly on the problem parameters, from the simulation results observed, the number of constraints can be manageable for a wide family of problems. Table 1 shows the results obtained from the explicit solution obtained by an mpQP solver for several random IET Control Theory Appl., Vol. 1, No. 1, January 2007
systems. Ver is the number of vertices of WN , Nrej the vertices non-rejected and Reg the number of regions of the explicit solution. For explicit solutions with a very high number of regions, different efficient implementation techniques have been proposed [25]. 331
Table 2: Number of vertices of WN (Ver) and number of critical regions (Reg) for different prediction horizons (N ) for system (10) N
1
Ver
2
Reg
4
4
3
5
6
8
10
8
32
64
256
1024
45
71
97
147
201
Example
Consider the double integrator with bounded additive uncertainties 1 1 0 0:1 A¼ ; B¼ ; D¼ ð10Þ 0 1 1 0 The uncertainty satisfies kwkk1 1 and the state and control input are constrained, namely kxkk1 10 and jukj 1. The control performance objectives are described by 1 0 Q¼P¼ 0 1 R ¼ 10, and as linear feedback law is considered, the unconstrained LQR control K ¼ [20.2054 20.7835]. The critical regions of the resulting controller for prediction horizons of 1, 3 and 5 can be seen in Fig. 1. As can be seen, the explicit solution for a prediction horizon of 1 consists of six different regions. However, the optimum solution has the same expression in some of them, so it can be unified in only three polyhedral regions of interest that have been remarked in the figure. It can be seen that where the optimum control law is saturated, the control
Fig. 2 Explicit control law for the min –max controller with a prediction horizon N ¼ 1 for system (10) 332
correction input v has the same gain as the feedback law K ¼ [20.2054 20.7835] but of inverted sign, so the applied input is independent of the state vector. In this figure, vertices I ¼ 1 and I ¼ 2 correspond to w ¼ 1 and w ¼ 21, respectively, whereas constraints A ¼ 9 and A ¼ 10 correspond to u0 21, and u0 1, respectively. The dotted line is the region of the state space where the maximum of the optimum solution is attained at I ¼ [1, 2] and is a lower dimension region. Fig. 1 also shows the simulation results for different constant values of the uncertainty for a controller with a prediction horizon of 8. Table 2 shows the number of vertices of the polyhedra WN and number of critical regions for different prediction horizons. Fig. 2 presents the control algorithm that has to be implemented to obtain the optimum control correction effort v(0) for a prediction horizon of 1. It can be implemented as a look up table. 5
Conclusions
The paper has shown that a min – max MPC with a quadratic objective function can be transformed into an mpQP problem with a semi-definite positive objective function. This allows us to obtain an alternative and more compact proof of the piecewise affine nature of this type of controllers than the one described in literature. The explicit solution of the min – max not only makes possible the implementation in real plants of these controllers, but also gives an insight of the underlying structure. 6
References
1 Camacho, E.F., and Bordons, C.: ‘Model predictive control’ (Springer-Verlag, 2004, 2nd edn.) 2 Witsenhausen, H.S.: ‘A minimax control problem for sampled linear systems’, IEEE Trans. Autom. Control, 1968, 13, (1), pp. 5 –21 3 Campo, P.J., and Morari, M.: ‘Robust model predictive control’. Proc. American Control Conference, 1987, pp. 1021– 1026 4 Kothare, M.V., Balakrishnan, V., and Morari, M.: ‘Robust constrained model predictive control using linear matrix inequalities’, Automatica, 1996, 32, pp. 1361– 1379 5 Wang, Y.J., and Rawlings, J.B.: ‘A new robust model predictive control method I: theory and computation’, J. Process Control, 2003, 13, pp. 231–247 6 Lee, J.H., and Yu, Z.: ‘Worst case formulations of model predictive control for systems with bounded parameters’, Automatica, 1997, 3, (5), pp. 763– 781 7 Bemporad, A., Borreli, F., and Morari, M.: ‘Min–max control of constrained uncertain discrete-time linear systems’, IEEE Trans. Autom. Control, 2003, 48, (9), pp. 1600–1606 8 Scokaert, P.O.M., and Mayne, D.Q.: ‘Min– max feedback model predictive control for constrained linear systems’, IEEE Trans. Autom. Control, 1998, 43, (8), pp. 1136–1142 9 Kerrigan, E.C., and Maciejowski, J.M.: ‘Feedback min-max model predictive control using a single linear program: robust stability and the explicit solution’, Int. J. Robust Nonlinear Control, 2004, 14, pp. 395– 413 10 Sakizlis, V., Kakalis, N.M.P., Dua, V., Perkins, J.D., and Pistikopoulos, E.N.: ‘Design of robust model-based controllers via parametric programming’, Automatica, 2004, 40, pp. 189–201 11 Allwright, J.C., and Papavasiliou, G.C.: ‘On linear programming and robust model-predictive control using impulse-response’, Syst. Control Lett., 1992, 18, pp. 159–164 12 Bemporad, A.: ‘Reducing conservativeness in predictive control of constrained systems with disturbances’. Proc. American Control Conference, Tampa, Florida, USA, 1998, pp. 1384–1389 13 Lo¨fberg, J.: ‘Minimax approaches to robust model predictive control’, PhD thesis, April 2003 14 Ramirez, D.R., and Camacho, E.F.: ‘Piecewise affinity of min–max mpc with bounded additive uncertainties and a quadratic criterion’, Automatica, 2006, 42, pp. 295– 302 15 Mun˜oz de la Pen˜a, D., Ramirez, D.R., Alamo, T., and Camacho, E.F.: ‘Application of an explicit min–max mpc to a scaled laboratory process’, Control Eng. Pract., 2005, 13, (12), pp. 1463–1471 IET Control Theory Appl., Vol. 1, No. 1, January 2007
16 Mun˜oz de la Pen˜a, D., Ramirez, D.R., Alamo, T., and Camacho, E.F.: ‘Explicit solution of min–max mpc with additive uncertainties and quadratic criterion’, Syst. Control Lett., 2006, 55, (4), pp. 266–274 17 Grancharova, A., and Johansen, T.A.: ‘Explicit min–max model predictive control of constrained nonlinear systems with model uncertainty’. Proc. 16th IFAC World Congress, Prague, Czech Republic, 2005 18 Bazaraa, M.S., and Shetty, C.M.: ‘Nonlinear programming. Theory and algorithms’ (John Wiley & Sons, 1979) 19 Bemporad, A., Morari, M., Dua, V., and Pistikopoulos, E.N.: ‘The explicit linear quadratic regulator for constrained systems’, Automatica, 2002, 38, pp. 3– 20 20 Tøndel, P., Johansen, T.A., and Bemporad, A.: ‘An algorithm for multi-parametric quadratic programming and explicit mpc solutions’, Automatica, 2003, 39, (3), pp. 489– 497 21 Seron, M.M., Goodwin, G.C., and De Dona´, J.A.: ‘Finitely parameterised implementation of receding horizon control for
IET Control Theory Appl., Vol. 1, No. 1, January 2007
22 23
24
25
constrained linear systems’. Proc. American Control Conference, Anchorage, AK, 2002, pp. 4481– 4485 Tøndel, P., Johansen, T.A., and Bemporad, A.: ‘Further results on multiparametric quadratic programming’. Proc. Conf. on Decision and Control, Maui, Hawaii, USA, 2003, , pp. 3173– 3178 Spjøtvold, J., Tøndel, P., and Johansen, T.A.: ‘Unique polyhedral representations to continuous selections for convex multiparametric quadratic programs’. Proc. American Control Conference, Portland, OR, USA, 2005, pp. 816– 821 Alamo, T., Mun˜oz de la Pen˜a, D., and Camacho, E.F.: ‘An offline algorithm for reducing the computational burden of a mpc min– max controller’. Proc. 42st IEEE Conf. on Decision and Control, Maui, Hawaii, USA, December 2003, pp. 1433–1437 Grancharova, A., and Johansen, T.A.: ‘Approximate explicit constrained linear model predictive control via orthogonal search tree’, IEEE Trans. Autom. Control, 2003, 48, pp. 810–815
333
