Methods of Numerical Simulation of 0-Controllable Sets of a Linear Discrete Dynamical System with Limited Control Based on Polyhedral Approximation Algorithms

The article deals with the problem of constructing a polyhedral approximation of the 0-controllable sets of a linear discrete-time system with linear control constraints. To carry out the approximation, it is proposed to use two heuristic algorithms aimed at reducing the number of vertices of an arbitrary polyhedron while maintaining the accuracy of the description in the sense of the Hausdorff distance. The reduction of the problem of calculating the distance between nested polyhedra to the problem of convex programming is demonstrated. The issues of optimality of obtained approximations are investigated. Examples are given.

1. Agrachev A.A., Sachkov YU.L. Geometricheskaya teoriya upravleniya [Geometric theory of control]. Moskva: Fizmatlit = Moscow: Physical education. (In Russ).
2. Boltyanskij V.G. Optimal’noe upravlenie diskretnymi sistemami [Optimal control of discrete systems]. Мoskva: Nauka=Moscow: The science. 1973. (In Russ.).
3. Ibragimov D.N., Novozhilin N.M., Portseva E.Yu. On Sufficient Optimality Conditions for a Guaranteed Control in the Speed Problem for a Linear Time-Varying Discrete-Time System with Bounded Control // Autom. Remote Control. 2021. V. 82. No. 12. P. 2076–2096. DOI: 10.31857/S0005231021120047
4. Ibragimov D.N., Novozhilin N.M., Portseva E.Yu. On Sufficient Optimality Conditions for a Guaranteed Control in the Speed Problem for a Linear Time-Varying Discrete- Time System with Bounded Control // Autom. Remote Control. 2021. V. 82. No. 12. P. 2076–2096. DOI: 10.1134/S000511792112002X
5. Ibragimov D.N., Sirotin A.N. O zadache bystrodeistviya dlya klassa lineinykh avtonomnykh beskonechnomernykh sistem s diskretnym vremenem i ogranichennym upravleniem // AIT. 2017. № 10. C. 3–32. DOI: 10.1134/S0005117917100010
6. Ibragimov D.N., Sirotin A.N. On the Problem of Operation Speed for the Class of Linear Infinite-Dimensional Discrete-Time Systems with Bounded Control // Autom. Remote Control. 2017. V. 78. No. 10. P. 1731–1756. DOI: 10.1134/S0005117917100010
7. Kamenev G.K. Chislennoe issledovanie effektivnosti metodov poliedral’noj approksimacii vypuklyh tel [Numerical investigation of the effectiveness of polyhedral approximation methods for convex bodies]. Moskva: Vychislitel’nyj centr RAN = Moscow: Computing Center of the Russian Academy of Sciences. 2010. (In Russ.).
8. Kozlov M.K., Tarasov S.P., Khachiyan L.G. Polinomial'naya razreshimost' vypuklogo kvadratichnogo programmirovaniya // ZH. vychisl. matem. i matem. fiz. 1980. T. 20. № 5. C. 1319–1323.
9. Kozlov M.K., Tarasov S.P., Khachiyan L.G. The polynomial solvability of convex quadratic programming // USSR Computational Mathematics and Mathematical Physics. V. 20. No. 5. P. 223–228. DOI: 10.1016/0041-5553(80)90098-1.
10. Kronover R.M. Fraktaly i khaos v dinamicheskikh sistemakh. Osnovy teorii. [Fractals and chaos in dynamical systems. Fundamentals of theory]. Moskva: Postmarket = Moskow: Postmarket. 2000. (In Russ).
11. Malyshev V.V., Krasil'shchikov M.N., Bobronnikov V.T., Nesterenko O.P., Fedorov A.V. Sputnikovyye sistemy monitoringa. Analiz, sintez i upravleniye. [Satellite monitoring systems. Analysis, synthesis and management]. Moskva: MAI = Moskow: MAI. 2000. (In Russ).
12. Propoj A.I. Elementy teorii optimal’nyh diskretnyh processov [Elements of the theory of optimal discrete processes]. Мoskva: Nauka = Moscow: The science. 1973. (In Russ.).
13. Rokafellar R. Vypuklyj analiz [Convex analysis]. Мoskva: Mir = Moscow: Mir. 1973. (In Russ.).
14. Sirotin A.N. Upravlyaemost' lineinykh diskretnykh sistem s ogranichennym upravleniem i (pochti) periodicheskimi vozmushcheniyami // AIT. 2001. № 5. C. 53–64.
15. Sirotin A.N. Controllability of linear discrete systems with bounded control and (almost) periodic disturbances // Autom. Remote Control. 2001. V. 62. No. 5. P. 724–734. DOI: 10.1023/A:1010266622197.
16. Barber C.B., Dobkin D.P., Huhdanpaa H. The quickhull algorithm for convex hulls // ACM Transactions on Mathematical Software. 1996. Vol. 4. No. 22. P. 469–483. DOI: 10.1145/235815.235821.
17. Benvenuti L., Farina L. The geometry of the reachability set for linear discrete-time systems with positive controls // SIAM Journal on Matrix Analysis and Applications. 2006. Vol. 28. No. 2. P. 306–325. DOI: 10.1137/040612531.
18. Colonius F., Cossich J.A.N., Santana A.J. Controllability properties and invariance pressure for linear discrete-time systems // Journal of Dynamics and Differential Equations. 2022. Vol. 34. P. 5–22. DOI: 10.1007/s10884-021-09966-4.
19. Darup M.S., Mönnigmann M. On general relations between null-controllable and controlled invariant sets for linear constrained systems // 53rd IEEE Conference on Decision and Control. Los Angeles. 2014. P. 6323–6328. DOI: 10.1109/CDC.2014.7040380.
20. Fucheng L., Mengyuan S., Usman Optimal preview control for linear discrete-time periodic systems // Mathematical Problems in Engineering. 2019. P. 1–11. DOI: 10.1155/2019/8434293.
21. Ge S.S., Zhendong S., Lee T.H. Reachability and controllability of switched linear discrete-time systems // IEEE Transactions on Automatic Control. 2001. Vol. 46. No. 9. P. 1437–1441. DOI: 10.1109/9.948473.
22. Heemels W.P.M.H., Camlibel M.K. Null controllability of discrete-time linear systems with input and state constraints // 47th IEEE Conference on Decision and Control. Cancun. 2008. P. 3487–3492. DOI: 10.1109/CDC.2008.4739333.
23. Kaba M.D., Camlibel M.K. A spectral characterization of controllability for linear discrete-time systems with conic constraints // SIAM Journal on Control and Optimization. 2015. Vol. 53. No. 4. P. 2350–2372. DOI: 10.1137/140960967.
24. Kostousova E.K. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms // Mathematical Control and Related Fields. 2021. Vol. 11. No. 3. P. 625–641. DOI: 10.3934/mcrf.2021015.
25. Kurzhanskiy A., Varaiya P. Ellipsoidal Techniques for Reachability Analysis of Discrete- Time Linear Systems // IEEE Transactions on Automatic Control. 2007. Vol. 52. No. 1. P. 26–38. DOI: 10.1109/TAC.2006.887900.
26. Weibel C. Minkowski sums of polytopes: combinatorics and computation. Lausanne: EPFL. 2007. 114 p. DOI: 10.5075/epfl-thesis-3883.
27. Bronshteyn Ye.M., Ivanov L.D. Priblizheniye vypuklykh mnozhestv mnogogrannikami [Approximation of convex sets by polyhedra] // Sibirskiy matematicheskiy zhurnal. 1975. No. 16. P. 1110-1112. (In Russ).