Polyhedral Feasible Set Computation of MPC-Based Optimal Control Problems

Lantao Xie^{1}, Lei Xie^{1}, Hongye Su^{1}, Jingdai Wang^{2}

1. State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China; 2. College of Chemical and Biological Engineering, Zhejiang University, Hangzhou 310027, China

Abstract Feasible sets play an important role in model predictive control (MPC) optimal control problems (OCPs). This paper proposes a multi-parametric programming-based algorithm to compute the feasible set for OCP derived from MPC-based algorithms involving both spectrahedron (represented by linear matrix inequalities) and polyhedral (represented by a set of inequalities) constraints. According to the geometrical meaning of the 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 has been proved to be one of the vertices of the feasible set. After computing the vertices, the convex hull of these vertices is determined which equals the feasible set. The simulation results show that the proposed method is especially efficient for low dimensional feasible set computation and avoids the non-unicity problem of optimizers as well as the memory consumption problem that encountered by projection algorithms.

Fund:This work was supported by the Natural Science Foundation of Zhejiang Province (LR17F030002) and the Science Fund for Creative Research Groups of the National Natural Science Foundation of China (61621002).

Corresponding Authors:
Hongye Su
E-mail: hysu@iipc.zju.edu.cn

Lantao Xie, Lei Xie, Hongye Su, Jingdai Wang, "Polyhedral Feasible Set Computation of MPC-Based Optimal Control Problems," IEEE/CAA Journal of Automatica Sinica, vol. 5, no. 4, pp. 765-770, 2018.

[1] D. Q. Mayne, "Model predictive control: recent developments and future promise, " Automatica, vol. 50, no. 12, pp. 2967-2986, Dec. 2014. [2] A. Mesbah, "Stochastic model predictive control: an overview and perspectives for future research, " IEEE Control Syst., vol. 36, no. 6, pp. 30-44, Dec. 2016. [3] F. Scibilia, S. Olaru, and M. Hovd, "On feasible sets for MPC and their approximations, " Automatica, vol. 47, no. 1, pp. 133-139, Jan. 2011. [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, "Constraint-tightening and stability in stochastic model predictive control, " IEEE Trans. Autom. Control, vol. 62, no. 7, pp. 3165-3177, Jul. 2017. [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. 2746-2761, Nov. 2012. [7] L. T. Xie and L. Xie, Linear mismatched model based offset-free 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. [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. 207-220, Aug. 2008. [10] S. V. Raković, B. Kouvaritakis, R. Findeisen, and M. Cannon, "Homothetic tube model predictive control, " Automatica, vol. 48, no. 8, pp. 1631-1638, Aug. 2012. [11] F. Borrelli, A. Bemporad, and M. Morari, "Geometric algorithm for multiparametric linear programming, " J. Optim. Theory Appl., vol. 118, no. 3, pp. 515-540, Sep. 2003. [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. 177-189, Aug. 2007. [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. 221-230, Feb. 2009. [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. 194-200, Jan. 2011. [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. 207-226. [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: Springer-Verlag, 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. 1000-1020, May 2013. [21] M. V. Ramana, "Polyhedra, spectrahedra, and semidefinite programming, " in Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications, Providence, RI, USA, vol. 18, pp. 27-38, 1997. [22] A. Bhardwaj, P. Rostalski, and R. Sanyal, "Deciding polyhedrality of spectrahedra, " SIAM J. Optim., vol. 25, no. 3, pp. 1873-1884, Sep. 2015. [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. 219-224, Feb. 2005. [24] D. Limon, I. Alvarado, T. Alamo, and E. F. Camacho, "Robust tube-based MPC for tracking of constrained linear systems with additive disturbances, " J. Process Control, vol. 20, no. 3, pp. 248-260, Mar. 2010. [25] S. N. Čhernikov, "Contraction of finite systems of linear inequalities, " Dokl. Akad. Nauk SSSR, vol. 152, pp. 1075-1078, 1963. [26] Michael Grant, Stephen Boyd, and Y. Y. Ye, "CVX users guide, " 2009. [27] M. Herceg, M. Kvasnica, C. N. Jones, and M. Morari, "Multi-parametric toolbox 3.0, " in 2013 European Control Conf. (ECC), Zurich, Switzerland, pp. 502-510.