2. College of Chemical and Biological Engineering, Zhejiang University, Hangzhou 310027, China
Model predictive control (MPC) is a widely used method in process industries and fields such as automobile, energy, environment, aerospace and medical treatment, etc [1], [2] because of its ability to effectively handle the complex dynamics of systems with multiple inputs and outputs, system constraints, and conflicting control objectives. A key role played in a MPC framework is the socalled feasible set, i.e. the largest subset of the state space for which there exists a control action satisfying all the constraints [3]. MPCbased controllers will finally result in solving a standard optimal control problems (OCPs) such as linear programming (LP), quadratic programming (QP), semidefinite programming (SDP), dynamic programming (DP), etc. If the corresponding OCP is designed to be stable or recursively feasible, once the initial state is in the feasible set, there always exists an optimal control action at each following sample time.
As stated in [4], a larger feasible set usually means that the corresponding MPC algorithm is less conservative. Thus, when comparing conservativeness of different MPC algorithms, feasible sets are often compared, such as in [5], [6]. Feasible sets can also be used to modify initial work states to ensure feasibility, and its shape description plays an important role in the effectiveness of many of the approaches for approximate explicit MPC [3]. By restricting the state of the second step in the prediction horizon in the feasible set and computing each set iteratively, the algorithm proposed in [7] obtains the recursively feasible set and guarantees recursive feasibility. Even with the consideration of techniques used for stability, feasible sets are closely related with the prediction horizon and system constraints; generally longer horizons and looser system constraints result in larger feasible sets.
Ovalshaped and polyhedral feasible sets are two commonly used convex sets in MPC algorithms. Ellipsoid can be described as a weighted 2norm and its size is related with some measure of the weighted matrix. By performing a maximum volume optimization in terms of the weighted matrix, one can obtain the largest ellipsoid, i.e., the ovalshaped feasible set, such as that shown in [8]. A polyhedron is the intersection of finitely many halfspaces. Computation of a polyhedron is much more complicated than of a ellipsoid. The standard approach to compute polyhedral feasible set is orthogonal projection [9]. However, the orthogonal projection needs the polyhedron to be described by its vertices (Vrepresentation) or the intersection of halfspaces (Hrepresentation), which cannot be applied when the polyhedron is written in linear matrix inequality (LMI) form. Moreover, orthogonal projection often turns out to be computationally intractable in high spatial dimensions. This often happens when the feasible set is computed for MPCbased OCPs with long prediction horizons or with large number of slack variables such as that in some robust MPC [10] and stochastic MPC algorithms [7]. Alternatives to compute feasible set involve parametric linear programming (PLP) methods [11] and set relation methods [3]. However, PLP methods may lead to numerical difficulties due to the nonunicity of the optimizers [12], while set relation methods are only efficient for OCPs without slack variables.
Based on the final OCP derived from MPCbased algorithms, this paper proposes a novel multiparametric programming problem where the final OCP involves both spectrahedron (represented by LMI) and polyhedral (represented by a set of inequalities) constraints. According to the geometrical meaning of an inner product of vectors, the maximum length of the projection vector from the feasible set to a unit spherical coordinates vector is computed and the optimal solution is proven to be one of the vertices of the feasible set. After computing all the vertices of the feasible set, the convex hull of these vertices is computed which is equivalent to the feasible set. The simulation results show that the proposed method is especially efficient for low dimensional feasible set computation and avoids the nonunicity problem of optimizers, as well as the memory consumption problem encountered by projection algorithms.
Consider the controlled system to be described as
$ \begin{equation}\label{sys} x_{k+1}=(f+\triangle f)(x_k, u_k, d_k, w_k) \end{equation} $  (1) 
where
$ \begin{eqnarray} &&J(x_k, \theta_k)=\min\limits_{\theta_k}: V(x_k, \theta_k) \nonumber\\ &&{\rm s.t.}\, \, H(x_k, \theta_k)\succeq0, G(x_k, \theta_k)\ge0 \end{eqnarray} $  (2) 
where
The feasible set of OCP (2) is the largest subset of the state space for which there exists a
$ \begin{eqnarray} {F}&\hspace{0.25cm}=&\hspace{0.25cm}\{x \exists \theta_k \text{ such that $J(x, \theta_k)$ is feasible}\}\nonumber\\ &\hspace{0.25cm}=&\hspace{0.25cm}\{xH(x, \theta_k)\succeq0, G(x, \theta_k)\ge0\}. \end{eqnarray} $  (3) 
Definition 1 (Polytope [18]): A bounded convex polyhedron is a polytope or, equivalently, a set
From this definition we can see that a 1simplex is a closed segment, a 2simplex is a triangle and a 3simplex is a tetrahedron. We adopt the convention that the empty set is a polytope of dimension
Thus,
$ \begin{equation}\label{VRepFS} {F}=\{x  x = \lambda_1v_1+\lambda_2v_2+\cdots+\lambda_pv_p\ \text{with}\ \lambda_i\ge0, \sum\limits_{i=1}^{p}\lambda_i=1\} \end{equation} $  (4) 
where
As the value of inner product between two vectors
$ \begin{eqnarray} &&J(x, c)=\max\limits_{x}: c^{T} x \nonumber\\ &&{\rm s.t.}\, \, H(x, \theta_k)\succeq0, G(x, \theta_k)\ge0 \end{eqnarray} $  (5) 
where
We will start with the computation of a 2dimensional feasible set.
A. 2D CaseWhen
Download:


Fig. 1 Feasible set in 2D. 
From Lemma 3 we know that, if we can find all the
1) Let
2) For
3) Compute
4) Let
5) Endfor.
6) Compute the convex hull of points set
From the proof of theorem 1, we know that the optimal
If
Download:


Fig. 2 Feasible set in 3D. 
Again, if we traverse
1) Let
2) For
3) For
4) Compute
5) Let
6) Endfor.
7)
8) Endfor.
9) Compute the convex hull of points set
Parameters
When
$ \begin{eqnarray} c_1&=&\sin \phi_1\nonumber\\ c_2&=&\cos \phi_1 \sin \phi_2\nonumber\\ c_3&=&\cos\phi_1 \cos \phi_2\sin \phi_3\nonumber\\ & \vdots&\nonumber\\ c_{n1}&=&\cos \phi_1 \cdots\cos\phi_{n2}\sin \phi_{n1}\nonumber\\ c_{n}&=&\cos \phi_1 \cdots\cos\phi_{n2}\cos\phi_{n1}. \end{eqnarray} $  (6) 
Theoretically, if we traverse
An alternative is to consider the orthogonal projection if the feasible set is well structured and the projection is computationally tractable. From the definition of orthogonal projection, we know that given
$ \begin{equation}\label{2D} x_{k+1}= \left( \begin{array}{c c} 1&1\\ 0&1\\ \end{array}\right)x_k+ \left( \begin{array}{c} 0.5\\ 1\\ \end{array}\right)u_k+w_k \end{equation} $  (7) 
with system constraints
$ \begin{eqnarray} &&Ax+Bu\in {X}\ominus{S}\nonumber\\[2mm] &&x\in {X}\nonumber\\[2mm] &&u\in {U} \end{eqnarray} $  (8) 
where
Download:


Fig. 3 Feasible set of Example 1 with 
$ \begin{equation}\label{LCSTR} x_{k+1}=Ax_k+Bu_k+B_pp_k+B_qq_k \end{equation} $  (9) 
where
$ \begin{eqnarray*} A&\hspace{0.25cm}=\hspace{0.25cm}&\left( \begin{array}{c c c} 9.827\times10^{1}&9.803\times10^{4}& 1.226\times10^{5} \\ 4.277\times10^{1} & 1.000\times10^{0} & 2.351\times10^{2} \\ 4.649\times10^{2} & 2.043\times10^{1} & 6.953\times10^{1} \\ \end{array}\right) \end{eqnarray*} $ 
$ \begin{eqnarray*} B_p&\hspace{0.25cm}=\hspace{0.25cm}&\left( \begin{array}{c c c} 2.828\times10^{0}& 1.713\times10^{3} &8.495\times10^{7}\\ 1.163\times10^{1}& 3.707\times10^{4}& 1.728\times10^{3}\\ 1.281\times10^{0}& 2.762\times10^{5}&1.873\times10^{4}\\ \end{array}\right) \end{eqnarray*} $ 
$ \begin{eqnarray*} B&\hspace{0.25cm}=\hspace{0.25cm}&\left( \begin{array}{c} 4.961\times10^{4}\\ 1.468\times10^{0}\\ 9.860\times10^{1} \end{array}\right), B_q=\left( \begin{array}{c} 5.193\times10^{7}\\ 1.536\times10^{3}\\ 1.032\times10^{1}\\ \end{array}\right). \end{eqnarray*} $ 
Constraints for this CSTR system are
Using the proposed algorithms in [7], the final OCP involves both spectrahedral and polyhedral constraints. Choose
Download:


Fig. 4 Feasible set for example 2 with 
Download:


Fig. 5 Computation time. 
The implementation was performed on laptop with Intel Core i74600U @ 2.10GHz 2.70GHz and 8 GB RAM. mPPP is solved by cvx tool box [26] in MATLAB and the polyhedron operation and orthogonal projection are realized by the multiparametric toolbox (MPT) [27].
Ⅴ. CONCLUSIONIn this paper, a multiparametric programming problem has been proposed to compute the feasible set of the final OCP derived from MPCbased algorithms and involving both spectrahedral (represented by LMI) and polyhedral (represented by a set of inequalities) constraints. In fact, the forms or even the convexity and linearity of constraints are not restricted as long as assumption 1 holds. The simulation results showed that the proposed method is especially efficient for low dimensional feasible set computation and avoided the nonunicity problem of optimizers. Because the computation procedure just involves solving the basic mPPP repeatedly, memory consumption is not large. Thus, the proposed algorithm avoids the memory depletion problem encountered by projection algorithms. If we choose a large
However, if the dimension of the feasible set is very large, the computational burden of the proposed method would be horrific. One may consider transforming the LMIrepresentation constraints to Hrepresentation using transformation techniques from spectrahedron to polyhedron and then applying the orthogonal projection if the feasible set is well structured and the projection is computationally tractable.
[1]  D. Q. Mayne, "Model predictive control: recent developments and future promise, " Automatica, vol. 50, no. 12, pp. 29672986, Dec. 2014. http://www.sciencedirect.com/science/article/pii/S0005109814005160 
[2]  A. Mesbah, "Stochastic model predictive control: an overview and perspectives for future research, " IEEE Control Syst., vol. 36, no. 6, pp. 3044, Dec. 2016. http://ieeexplore.ieee.org/document/7740982/ 
[3]  F. Scibilia, S. Olaru, and M. Hovd, "On feasible sets for MPC and their approximations, " Automatica, vol. 47, no. 1, pp. 133139, Jan. 2011. http://dl.acm.org/citation.cfm?id=1923254 
[4]  L. T. Xie, L. Xie, and H. Y. Su, "A comparative study on algorithms of robust and stochastic MPC for uncertain systems". Acta Autom. Sinica , vol.43, no.6, pp.969–992, 2017. 
[5]  M. Lorenzen, F. Dabbene, R. Tempo, and F. Allgöwer, "Constrainttightening and stability in stochastic model predictive control, " IEEE Trans. Autom. Control, vol. 62, no. 7, pp. 31653177, Jul. 2017. http://arxiv.org/abs/1511.03488 
[6]  S. V. Raković, B. Kouvaritakis, M. Cannon, C. Panos, and R. Findeisen, "Parameterized tube model predictive control, " IEEE Trans. Autom. Control, vol. 57, no. 11, pp. 27462761, Nov. 2012. http://www.sciencedirect.com/science/article/pii/S0005109815005646 
[7]  L. T. Xie and L. Xie, Linear mismatched model based offsetfree MPC for nonlinear constrained cstr systems with stochastic and deterministic disturbances. Control Engineering Practice, 2018. 
[8]  J. Löfberg, "Minimax approaches to robust model predictive control, " Ph. D. dissertation, Linköping University, Linköping, Sweden, 2003. https://www.researchgate.net/publication/228869742_Minmax_approaches_to_robust_model_predictive_control 
[9]  C. N. Jones, E. C. Kerrigan, and J. M. Maciejowski, "On polyhedral projection and parametric programming, " J. Optim. Theory Appl., vol. 138, no. 2, pp. 207220, Aug. 2008. http://www.ams.org/mathscinetgetitem?mr=2414994 
[10]  S. V. Raković, B. Kouvaritakis, R. Findeisen, and M. Cannon, "Homothetic tube model predictive control, " Automatica, vol. 48, no. 8, pp. 16311638, Aug. 2012. http://www.sciencedirect.com/science/article/pii/S0005109812001768 
[11]  F. Borrelli, A. Bemporad, and M. Morari, "Geometric algorithm for multiparametric linear programming, " J. Optim. Theory Appl., vol. 118, no. 3, pp. 515540, Sep. 2003. http://link.springer.com/article/10.1023/B%3AJOTA.0000004869.66331.5c 
[12]  J. Spjotvold, P. Tondel, and T. A. Johansen, "Continuous selection and unique polyhedral representation of solutions to convex parametric quadratic programs, " J. Optim. Theory Appl., 134, no. 2, pp. 177189, Aug. 2007. http://link.springer.com/article/10.1007/s109570079215z 
[13]  J. A. Primbs and C. H. Sung, "Stochastic receding horizon control of constrained linear systems with state and control multiplicative noise, " IEEE Trans. Autom. Control, vol. 54, no. 2, pp. 221230, Feb. 2009. http://www.researchgate.net/publication/4265686_Stochastic_Receding_Horizon_Control_of_Constrained_Linear_Systems_with_State_and_Control_Multiplicative_Noise 
[14]  M. Cannon, B. Kouvaritakis, S. V. Rakovic, and Q. F. Cheng, "Stochastic tubes in model predictive control with probabilistic constraints, " IEEE Trans. Autom. Control, vol. 56, no. 1, pp. 194200, Jan. 2011. http://ieeexplore.ieee.org/document/5599849 
[15]  A. Bemporad and M. Morari, "Robust model predictive control: A survey, " in Robustness in Identification and Control, A. Garulli and A. Tesi, Eds. London, UK: Springer, 1999, pp. 207226. http://www.springerlink.com/index/n8734746605j8447.pdf 
[16]  G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry. Philadelphia, Pennsylvania, USA: SIAM, 2012. 
[17]  S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004. 
[18]  A. Brondsted, An Introduction to Convex Polytopes. New York, USA: SpringerVerlag, 1983. 
[19]  E. Castillo, A. Cobo, F. Jubete, and R. E. Pruneda, Orthogonal Sets and Polar Methods in Linear Algebra: Applications to Matrix Calculations, Systems of Equations, Inequalities, and Linear Programming. New York, USA: John Wiley & Sons, 2011. 
[20]  K. Kellner, T. Theobald, and C. Trabandt, "Containment problems for polytopes and spectrahedra, " SIAM J. Optim., vol. 23, no. 2, pp. 10001020, May 2013. http://www.oalib.com/paper/3951878 
[21]  M. V. Ramana, "Polyhedra, spectrahedra, and semidefinite programming, " in Topics in Semidefinite and InteriorPoint Methods, Fields Institute Communications, Providence, RI, USA, vol. 18, pp. 2738, 1997. http://www.ams.org/mathscinetgetitem?mr=1607318 
[22]  A. Bhardwaj, P. Rostalski, and R. Sanyal, "Deciding polyhedrality of spectrahedra, " SIAM J. Optim., vol. 25, no. 3, pp. 18731884, Sep. 2015. http://arxiv.org/abs/1102.4367 
[23]  D. Q. Mayne, M. M. Seron, and S. V. Raković, "Robust model predictive control of constrained linear systems with bounded disturbances, " Automatica, vol. 41, no. 2, pp. 219224, Feb. 2005. http://ogma.newcastle.edu.au/vital/access/manager/Repository/uon:361?exact=creator%3A 
[24]  D. Limon, I. Alvarado, T. Alamo, and E. F. Camacho, "Robust tubebased MPC for tracking of constrained linear systems with additive disturbances, " J. Process Control, vol. 20, no. 3, pp. 248260, Mar. 2010. http://www.sciencedirect.com/science/article/pii/S0959152409002169 
[25]  S. N. Čhernikov, "Contraction of finite systems of linear inequalities, " Dokl. Akad. Nauk SSSR, vol. 152, pp. 10751078, 1963. http://www.mathnet.ru/eng/dan28687 
[26]  Michael Grant, Stephen Boyd, and Y. Y. Ye, "CVX users guide, " 2009. 
[27]  M. Herceg, M. Kvasnica, C. N. Jones, and M. Morari, "Multiparametric toolbox 3. 0, " in 2013 European Control Conf. (ECC), Zurich, Switzerland, pp. 502510. 