Skip to Main Content

Modelling and Data Analysis
2025. Vol. 15, no. 4, 104–121
doi:10.17759/mda.2025150407
ISSN: 2219-3758 / 2311-9454 (online)

Analysis of the complexity of the algorithm for solving the time-optimization problem for linear discrete-time systems with linear constraints

 
Audio is AI-generated
2

,

PDF (RUS)
Online translation in english
GS
Information
in Google Scholar
Metrics

Abstract

This paper is devoted to analysis of the complexity of the algorithm for solving time-optimization problems for linear discrete-time systems with linear constraints. An algorithm is proposed that uses the construction of null-controllable sets and the calculation of the Minkowski functional. An analytical upper bound for the computational complexity is obtained for the algorithm. Numerical calculations are also performed. The results show that the time required to solve the time-optimization problem depends significantly on the system parameters: with increasing dimension of the state vector and the description complexity of the set of control constraints, the computational costs increase exponentially. It is found that for relatively small state space dimension, the algorithm executes in an acceptable time, but further increases in dimension lead to an increase in computational time. This corresponds to the theoretical complexity estimate and confirms the validity of the chosen approach.

General Information

Keywords: optimal control, time-optimization problem, convex hull, linear programming problem, computational complexity

Journal rubric: Numerical Methods

Article type: scientific article

DOI: https://doi.org/10.17759/mda.2025150407

Received 24.10.2025

Revised 10.11.2025

Accepted

Published

For citation: Kamchiev, N.A., Ibragimov, D.N. (2025). Analysis of the complexity of the algorithm for solving the time-optimization problem for linear discrete-time systems with linear constraints. Modelling and Data Analysis, 15(4), 104–121. (In Russ.). https://doi.org/10.17759/mda.2025150407

© Kamchiev N.A., Ibragimov D.N., 2025

License: CC BY-NC 4.0

References

  1. Беллман, Р. (1960). Динамическое программирование. М.: ИИЛ.
    Bellman, R. (1960). Dynamic programming. Moscow: IIL. (In Russ.).
  2. Ибрагимов Д.Н., Кибзун А.И. (2025). Программная реализация алгоритмов решения задачи быстродействия для линейных систем с дискретным временем. Вестник компьютерных и информационных технологий, 22(3), 12–20. 10.14489/vkit.2025.03.pp.012-020
    Ibragimov D.N., Kibzun A.I. (2025). Software implementation of algorithms for solving the performance problem for linear discrete-time systems. Herald of Computer and Information Technologies (Russia), 22(3), 12–20. 10.14489/vkit.2025.03.pp.012-020 (In Russ.).
  3. Ибрагимов Д.Н., Новожилкин Н.М., Порцева Е.Ю. (2021). О достаточных условиях оптимальности гарантирующего управления в задаче быстродействия для линейной нестационарной дискретной системы с ограниченным управлением. АиТ, (12), 48–72. 10.1134/S000511792112002X
    Ibragimov, D.N., Novozhilin, N.M., Portseva, E.Y. (2021). 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, (82), 2076–2096. https://doi.org/10.1134/S000511792112002X
  4. Ибрагимов Д.Н., Сиротин А.Н. (2017). О задаче быстродействия для класса линейных автономных бесконечномерных систем с дискретным временем и ограниченным управлением. АиТ, (10), 3–32. 10.1134/S0005117917100010
    Ibragimov, D.N., Sirotin, A.N. (2017). On the problem of operation speed for the class of linear infinite-dimensional discrete-time systems with bounded control. Autom Remote Control, (78), 1731–1756. https://doi.org/10.1134/S0005117917100010
  5. Краснощеченко В.И. (2014). Симплекс-метод для решения задачи быстродействия при наличии ограничения на скалярное управление и фазовых ограничений. Инженерный журнал: наука и инновании. (6). URL: http://engjournal.ru/catalog/it/asu/1252.html
    Krasnoshchechenko V.I. (2014). The simplex method for solving the performance problem with scalar control and state constraints. Engineering Journal: Science and Innovation (Russia), (6). URL: http://engjournal.ru/catalog/it/asu/1252.html (In Russ.).
  6. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. I. АиТ, 26(2), 193–207.
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. I.. Automation and Remote Control (Russia), 26(2), 193–207. (In Russ.).
  7. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. АиТ, 26(3), 410–426.
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. II.. Automation and Remote Control (Russia), 26(3), 410–426. (In Russ.).
  8. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. АиТ, 26(8), 1324–1335
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. III.. Automation and Remote Control (Russia), 26(8), 1324–1335. (In Russ.).
  9. Пропой А.И. (1973). Элементы теории оптимальных дискретных процессов. М.: Наука.
    Propoy A.I. (1973). Elements of the theory of optimal discrete processes. Moscow: Nauka. (In Russ.).
  10. Сазанова Л.А. (2002). Устойчивость оптимального синтеза в задаче быстродействия. Известия вузов. Математика, (2), 46–57.
    Sazanova L.A. (2002). Stability of optimal synthesis in the performance problem. University Proceedings. Mathematics (Russia), (2), 46–57. (In Russ.).
  11. Схрейвер А. (1991). Теория линейного и целочисленного программирования. М.: Мир.
    Schrijver A. (1986). Theory of Linear and Integer Programming. England: John Wiley & Sons Ltd.
  12. Abdelhak A., Rachik M. (2010). The Linear Quadratic Minimum-Time Problem for a Class of Discrete Systems. Math. Programming and Operations Research, 59(4), 575–587. 10.1080/02331930801954672
  13. Amato F., Cosentino C., Tommasi G. D., Pironti A., Romano M. (2022). Input–Output Finite-Time Stabilization of Linear Time-Varying DiscreteTime Systems. IEEE Transactions on Automatic Control, 67(9), 4438–4450. 10.1109/TAC.2022.3161374
  14. Barber C. B., Dobkin D. P., Huhdanpaa H. (1996). The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software. 10.1145/235815.235821
  15. Bashein G. (1971). A Simplex Algorithm for On-Line Computation of Time Optimal Controls. IEEE Transactions on Automatic Control, 16(5), 479–482. 10.1109/TAC.1971.1099776
  16. Blanchini F. (1991). Polyhedral Set Constrained Control for Discrete-Time Systems with Unknown Additive Disturbances. IFAC Proceedings Volumes. 24(8), 95–100. 10.1016/s1474-6670(17)54151-8
  17. Blanchini F., Ukovich W. (1993). Linear Programming Approach to the Control of Discrete-Time Periodic Systems with Uncertain Inputs. Journal of Optimization Theory and Applications, 78(3), 523–539. 1007/bf00939880
  18. Chen D., Bako L., Lecoeuche S. (2012). The Minimum-Time Problem for Discrete-Time Linear Systems: A Non-Smooth Optimization Approach. Proceedings of the IEEE International Conference on Control Applications, 196–201. 10.1109/CCA.2012.6402693
  19. Desoer C.A., Wing J. (1961). The Minimal Time Regulator Problem for Linear Sampled-Data Systems: General Theory. Franklin Inst, 272(3), 208–228. 10.1016/0016-0032(61)90784-0
  20. Karmarkar N. (1984). A new polynomial-time algorithm for linear programming.
  21. Keerthi S., Gilbert E. (1987). Computation of Minimum-Time Feedback Control Laws for Discrete-Time Systems with State-Control Constraints. IEEE Transactions on Automatic Control, 32(5), 432–435. 10.1109/tac.1987.1104625
  22. Khachiyan L. G. (1980). Polynomial algorithms in linear programming. S.S.R. Cornput. Maths. Math. Phys, 20(1), 53–72. https://doi.org/10.1016/0041-5553(80)90061-0
  23. Kolev L.V. (1978). Minimum-Fuel Minimum-Time Control of Linear Discrete Systems. International Journal of Control, 27(1), 21–29. 10.1080/00207177808922344
  24. Lasserre J.B. (1993). Reachable, Controllable Sets and Stabilizing Control of Constrained Linear Systems. Automatica, 29(2), 531–536. 1016/0005-1098(93)90152-J
  25. Lee J., Haddad W.M. (2022). Fixed Time Stability and Optimal Stabilisation of Discrete Autonomous Systems. International Journal of Control, 96(9), 2341–2355. 1080/00207179.2022.2092557
  26. Leomanni M., Costante G., Ferrante F. (2022). Time-Optimal Control of a Multidimensional Integrator Chain With Applications. IEEE Control Systems Letters, 6, 2371–2376. 1109/LCSYS.2022.3154351
  27. Lin W.-S. (1986). Time-Optimal Control Strategy for Saturating Linear Discrete Systems. J. Control, 43(5), 1343–1351. 10.1080/00207178608933543
  28. Lini G., Consolini L., Piazzi A. (2009). Minimum-Time Constrained Velocity Planning. IEEE 2009 17th Mediterranean Conference on Control and Automation, 748–753. 10.1109/med.2009.5164633
  29. Scott M. (1986). Time/Fuel Optimal Control of Constrained Linear Discrete Systems. Automatica, 22(6), 711–715. 1016/0005- 1098(86)90008-7
  30. Stamnes O.N., Callafon R.A. (2007). Time-Optimal Input Shaping for DiscreteTime LTI Systems with Application to Seek Profiles of a HDD System. ASME ISPS Conf, 146–148.
  31. Vlieger J.H., Verbruggen H.B., Bruijn P.M. (1982). A Time-Optimal Control Algorithm for Digital Computer Control. Automatica, 18(2), 239–244. 1016/0005-1098(82)90111-x
  32. Weibel C. (2007). Minkowski sums of polytopes: combinatorics and computation. Suisse: EPFL. 10.5075/epfl-thesis-3883
  33. Yang H., Xia Y., Geng Q. (2019). Stabilization on Null Controllable Region. In: Analysis and Synthesis of Delta Operator Systems with Actuator Saturation. Studies in Systems, Decision and Control, 193, 39–65. 10.1007/978-981-13-3660-7_3

Information About the Authors

Nurseyit A. Kamchiev, student of the Department of Computer Modeling of Information and Economic Systems, Moscow Aviation Institute (national research university) (MAI), Moscow, Russian Federation, ORCID: https://orcid.org/0009-0001-1044-7071, e-mail: nurseiitkamchiev@yandex.ru

Danis N. Ibragimov, Candidate of Science (Physics and Matematics), Associate Professor of Educational Center of Institute No. 8 Computer Science and Applied Mathematics, Moscow Aviation Institute (national research university) (MAI), Moscow, Russian Federation, ORCID: https://orcid.org/0000-0001-7472-5520, e-mail: rikk.dan@gmail.com

Conflict of interest

The author declare no conflict of interest.

Metrics

 Web Views

Whole time: 5
Previous month: 0
Current month: 5

 PDF Downloads

Whole time: 2
Previous month: 0
Current month: 2

 Total

Whole time: 7
Previous month: 0
Current month: 7