Constrained Controllability of Linear Discrete Time ‎Systems: A sufficient condition based on Farkas' Lemma

Document Type : Original Article


Department of Electrical Engineering, Standard Research Institute, Tehran, Iran


This paper provides sufficient conditions for controllability of discrete time linear systems with input saturation. Controllability is a central notion in linear system theory, optimal quadratic regulators as well as model predictive control algorithms. The more realistic notion of constrained controllability has given less attention probably due to mathematical complications. Most of the existing works on constrained controllability studies the properties of reachable sets. However, there are only a few works which investigate the problem of whether a state is reachable or not. In this paper, a set of sufficient conditions are firstly given for constrained controllability of time varying linear systems in discrete time formulation. The given conditions are obtained using the Farkas’ lemma for alternative inequalities. The obtained results improve existing literature by providing conditions for both null-controllability and controllability regardless of the system stability. A sufficient condition is then given for the special case of time invariant single input linear systems with diagonal Jordan canonical form. Numerical examples are given for clarification.


[1] Kalman, Rudolf Emil. "Contributions to the theory of optimal control." Bol. Soc. Mat. Mexicana 5.2 (1960): 102-119.
[2] Hu, Tingshu, and Zongli Lin. Control systems with actuator saturation: analysis and design. Springer Science & Business Media, 2001.
[3] Share Pasand, Mohammad Mahdi, and Mohsen Montazeri. "Structural properties, LQG control and scheduling of a networked control system with bandwidth limitations and transmission delays." IEEE/CAA Journal of Automatica  Sinica (2017).
[4] Longo, Stefano, et al. Optimal and robust scheduling for networked control systems. CRC press, 2013.
[5] Share Pasand, Mohammad Mahdi, and Mosen Montazeri. "L-Step Reachability and Observability of Networked Control Systems with Bandwidth Limitations: Feasible Lower Bounds on Communication Periods." Asian Journal of Control 19.4 (2017): 1620-1629.
[6] Share Pasand, Mohammad Mahdi, and Mohsen Montazeri. "Structural Properties of Networked Control Systems with Bandwidth Limitations and Delays." Asian Journal of Control 19.3 (2017): 1228-1238.
[7] Share Pasand, Mohammad Mahdi, and Mohsen Montazeri. "Controllability and stabilizability of multi-rate sampled data systems." Systems & Control Letters 113 (2018): 27-30.
[8] Wing, J., and C. Desoer. "The multiple-input minimal time regulator problem (general theory)." IEEE Transactions on Automatic Control 8.2 (1963): 125-136.
[9] Son, Nguyen Khoa. "Controllability of linear discrete-time systems with constrained controls in Banach spaces." Control and Cybernetics 10.1-2 (1981): 5-16.
[10] Sontag, Eduardo D. "An algebraic approach to bounded controllability of linear systems." International Journal of Control 39.1 (1984): 181-188.
[11] Evans, M. E. "The convex controller: controllability in finite time." International journal of systems science 16.1 (1985): 31-47.
[12] Nguyen, K. S. "On the null-controllability of linear discrete-time systems with restrained controls." Journal of optimization theory and applications 50.2 (1986): 313-329.
[13] d'Alessandro, Paolo, and Elena De Santis. "Reachability in input constrained discrete-time linear systems." Automatica 28.1 (1992): 227-229.
[14] Lasserre, Jean B. "Reachable, controllable sets and stabilizing control of constrained linear systems." Automatica 29.2 (1993): 531-536.
[15] Van Til, Robert P., and William E. Schmitendorf. "Constrained controllability of discrete-time systems." International Journal of Control 43.3 (1986): 941-956.
[16] Hu, Tingshu, Daniel E. Miller, and Li Qiu. "Null controllable region of LTI discrete-time systems with input saturation." Automatica 38.11 (2002): 2009-2013.
[17] Hu, Tingshu, Zongli Lin, and Ben M. Chen. "Analysis and design for discrete-time linear systems subject to actuator saturation." Systems & Control Letters 45.2 (2002): 97-112.
[18] Heemels, W. P. M. H., and M. Kanat Camlibel. "Null controllability of discrete-time linear systems with input and state constraints." Decision and Control, 2008. CDC 2008. 47th IEEE Conference on. IEEE, 2008.
[19] Rakovic, Sasa V., et al. "Reachability analysis of discrete-time systems with disturbances." IEEE Transactions on Automatic Control 51.4 (2006): 546-561.
[20] Schmitendorf, W. E., and B. R. Barmish. "Null controllability of linear systems with constrained controls." SIAM Journal on control and optimization 18.4 (1980): 327-345.
[21] Klamka, Jerzy. "Constrained approximate controllability." IEEE Transactions on Automatic Control 45.9 (2000): 1745-1749.
[22] Fashoro, M., O. Hajek, and K. Loparo. "Controllability properties of constrained linear systems." Journal of optimization theory and applications 73.2 (1992): 329-346.
[23] Kurzhanski, Alexander B., and Pravin Varaiya. "Ellipsoidal techniques for reachability under state constraints." SIAM Journal on Control and Optimization 45.4 (2006): 1369-1394.
[24] Kerrigan, Eric C., John Lygeros, and Jan M. Maciejowski. "A geometric approach to reachability computations for constrained discrete-time systems." IFAC Proceedings Volumes 35.1 (2002): 323-328.
[25] Rakovic, Sasa V., Eric C. Kerrigan, and David Q. Mayne. "Reachability computations for constrained discrete-time systems with state-and input-dependent disturbances." 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475). Vol. 4. IEEE, 2003.
[26] Gusev, M. I. "Internal approximations of reachable sets of control systems with state constraints." Proceedings of the Steklov Institute of Mathematics 287.1 (2014): 77-92.
[27] Bravo, José Manuel, Teodoro Alamo, and Eduardo F. Camacho. "Robust MPC of constrained discrete-time nonlinear systems based on approximated reachable sets." Automatica 42.10 (2006): 1745-1751.
[28] Dueri, Daniel, et al. "Finite-horizon controllability and reachability for deterministic and stochastic linear control systems with convex constraints." 2014 American Control Conference. IEEE, 2014.
[29] Faulwasser, Timm, Veit Hagenmeyer, and Rolf Findeisen. "Constrained reachability and trajectory generation for flat systems." Automatica 50.4 (2014): 1151-1159.
[30] Border, Kim C. "Alternative linear inequalities." Cal Tech Lecture Notes (2013).
[31] Dinh, N., and V. Jeyakumar. "Farkas’ lemma: three decades of generalizations for mathematical optimization." Top 22.1 (2014): 1-22.
[32] Dax, Achiya. "Classroom Note: An Elementary Proof of Farkas' Lemma." SIAM review 39.3 (1997): 503-507.
[33] Bartl, David. "A short algebraic proof of the Farkas’ lemma." SIAM Journal on Optimization 19.1 (2008): 234-239.
[34] Bartl, David. "A very short algebraic proof of the Farkas’ Lemma." Mathematical Methods of operations research 75.1 (2012): 101-104.
[35]Antsaklis, Panos J., and Anthony N. Michel. Linear systems. Springer Science & Business Media, 2006.‏
[36] Hristu-Varsakelis, Dimitris. "Short-period communication and the role of zero-order holding in networked control systems." IEEE Transactions on automatic control 53.5 (2008): 1285-1290.