American Institute of Mathematical Sciences

Advanced
September  2022, 18(5): 3771-3786. doi: 10.3934/jimo.2021135

Direct optimal control for time-delay systems via a lifted multiple shooting algorithm

Canghua Jiang 1,, , Cheng Jin 1, , Ming Yu 1, and  Zongqi Xu 2,

1. 

School of Electrical Engineering and Automation, Hefei University of Technology, Hefei 230009, China
2. 

CRSC Research & Design Institute Group Co., Ltd., Beijing 100070, China

* Corresponding author: Canghua Jiang

Received  May 2021 Revised  May 2021 Published  September 2022 Early access  August 2021

Fund Project: The first author is supported by the Natural Science Foundation of Anhui Province, China, under Grant 2008085MF216

Aiming at efficient solution of optimal control problems for continuous nonlinear time-delay systems, a multiple shooting algorithm with a lifted continuous Runge-Kutta integrator is proposed. This integrator is in implicit form to remove the restriction of smaller integration step sizes compared with delays. A tangential predictor is applied in the integrator such that Newton iterations required can be reduced considerably. If one Newton iteration is applied, the algorithm has the same structure as direct collocation algorithms whereas derives a condensed nonlinear programming problem. Then, the solution of variational sensitivity equation is decoupled from forward simulation by utilizing the implicit function theorem. Under certain conditions, this function evaluation and derivative computation procedure is proved to be convergent with a global order. Complexity analysis shows that the computational cost can be largely reduced by this lifted multiple shooting algorithm. Then, parallelizable optimal control solver can be constructed by embedding this algorithm in a general-purpose nonlinear programming solver. Simulations on a numerical example demonstrate that the computational speed of multi-threading implementation of this algorithm is increased by $ 36\% $ compared with non-lifted one, and increased by a factor of $ 6.64 $ compared with traditional sequential algorithm; meanwhile, the accuracy loss is negligible.

Keywords: Delay systems, nonlinear control systems, optimal control, optimization methods, Runge-Kutta methods.
Mathematics Subject Classification: Primary: 49M37, 93C23; Secondary: 37M15.
Citation: Canghua Jiang, Cheng Jin, Ming Yu, Zongqi Xu. Direct optimal control for time-delay systems via a lifted multiple shooting algorithm. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3771-3786. doi: 10.3934/jimo.2021135
References:
[1]

A. Bellen and M. Zennaro, Numerical Methods for Delay Differential Equations, Numerical Mathematics and Scientific Computation. The Clarendon Press, Oxford University Press, New York, 2003. doi: 10.1093/acprof:oso/9780198506546.001.0001.

[2]

J. T. Betts, S. L. Campbell and K. C. Thompson, Optimal control software for constrained nonlinear systems with delays, in IEEE International Symposium on Computer-Aided Control System Design (CACSD), IEEE, Denver, CO, 2011,444–449.

[3]

L. T. Biegler, Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, MOS-SIAM Series on Optimization, Vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719383.

[4]

Q. Chai, R. Loxton, K. L. Teo and C. Yang, Time-delay estimation for nonlinear systems with piecewise-constant input, Appl. Math. Comput., 219 (2013), 9543-9560.  doi: 10.1016/j.amc.2013.03.015.

[5]

Q. Chai, R. Loxton, K. L. Teo and C. Yang, A unified parameter identification method for nonlinear time-delay systems, J. Ind. Manag. Optim., 9 (2013), 471-486.  doi: 10.3934/jimo.2013.9.471.

[6]

M. Diehl, H. J. Ferreau and N. Haverbeke, Efficient numerical methods for nonlinear MPC and moving horizon estimation, in Nonlinear Model Predictive Control, Lecture Notes in Control and Information Sciences, Vol. 384, Springer, Berlin, Heidelberg, 2009,391–417. doi: 10.1007/978-3-642-01094-1_32.

[7]

A. Griewank, Evaluating Derivatives, Principles and Techniques of Algorithmic Differentiation, Frontiers in Applied Mathematics, Vol. 19, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.

[8]

W. Horbelt, J. Timmer and H. U. Voss, Parameter estimation in nonlinear delayed feedback systems from noisy data, Physics Letter A, 299 (2002), 513-521.  doi: 10.1016/S0375-9601(02)00748-X.

[9]

C. Jiang, Z. Guo, X. Li, H. Wang and M. Yu, An efficient adjoint computational method based on lifted IRK integrator and exact penalty function for optimal control problems involving continuous inequality constraints, Discrete Contin. Dyn. Syst. Ser. S, 13 (2020), 1845-1865.  doi: 10.3934/dcdss.2020109.

[10]

C. Jiang, S. Wu, X. Li and C. Yu, An efficient algorithm to state-delay identification based on a collocation integrator and adjoint sensitivity propagation, in Proc. of the 38th Chinese Control Conf., Guangzhou, 2019, 1905–1910. doi: 10.23919/ChiCC.2019.8865925.

[11]

C. Jiang, K. Xie, C. Yu, M. Yu, H. Wang, Y. He and K. L. Teo, A sequential computational approach to optimal control problems for differential-algebraic systems based on efficient implicit Runge-Kutta integration, Appl. Math. Model., 58 (2018), 313-330.  doi: 10.1016/j.apm.2017.05.015.

[12]

S. M. Lenz, J. P. Schlöder and H. G. Bock, Numerical computation of derivatives in systems of delay differential equations, Math. Comput. Simulation, 96 (2014), 124-156.  doi: 10.1016/j.matcom.2013.08.003.

[13]

Q. Lin, R. Loxton and K. L. Teo, The control parameterization method for nonlinear optimal control: A survey, J. Ind. Manag. Optim., 10 (2014), 275-309.  doi: 10.3934/jimo.2014.10.275.

[14]

Q. Lin, R. Loxton, C. Xu and K. L. Teo, Parameter estimation for nonlinear time-delay systems with noisy output measurements, Automatica J. IFAC, 60 (2015), 48-56.  doi: 10.1016/j.automatica.2015.06.028.

[15]

C. Liu, R. Loxton and K. L. Teo, Switching time and parameter optimization in nonlinear switched systems with multiple time-delays, J. Optim. Theory Appl., 163 (2014), 957-988.  doi: 10.1007/s10957-014-0533-7.

[16]

R. Loxton, K. L. Teo and V. Rehbock, An optimization approach to state-delay identification, IEEE Trans. Automat. Control, 55 (2010), 2113-2119.  doi: 10.1109/TAC.2010.2050710.

[17]

R. Quirynen, S. Gros and M. Diehl, Inexact newton-type optimization with iterated sensitivities, SIAM J. Optim., 28 (2018), 74-95.  doi: 10.1137/16M1079002.

[18]

R. Quirynen, S. Gros, B. Houska and M. Diehl, Lifted collocation integrators for direct optimal control in ACADO toolkit, Math. Program. Comput., 9 (2017), 527-571.  doi: 10.1007/s12532-017-0119-0.

[19]

J.-P. Richard, Time-delay systems: An overview of some recent advances and open problems, Automatica J. IFAC, 39 (2003), 1667-1694.  doi: 10.1016/S0005-1098(03)00167-5.

[20]

X. Tang and H. Xu, Multiple-interval pseudospectral approximation for nonlinear optimal control problems with time-varying delays, Appl. Math. Model., 68 (2019), 137-151.  doi: 10.1016/j.apm.2018.09.039.

[21]

K. L. Teo, C. J. Goh and K. H. Wong, A Unified Computational Approach to Optimal Control Problems, Pitman Monographs and Surveys in Pure and Applied Mathematics, Vol. 55, Longman Scientific & Technical, Harlow. Copublished in the United States with John Wiley & Sons, Inc., New York, 1991.

[22]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., Ser. A, 106 (2006), 25-57.  doi: 10.1007/s10107-004-0559-y.

[23]

D. Wu, Y. Bai and C. Yu, A new computational approach for optimal control problems with multiple time-delay, Automatica J. IFAC, 101 (2019), 388-395.  doi: 10.1016/j.automatica.2018.12.036.

[24]

C. Yu, Q. Lin, R. Loxton, K. L. Teo and G. Wang, A hybrid time-scaling transformation for time-delay optimal control problems, J. Optim. Theory Appl., 169 (2016), 876-901.  doi: 10.1007/s10957-015-0783-z.

show all references

References:
[1]

A. Bellen and M. Zennaro, Numerical Methods for Delay Differential Equations, Numerical Mathematics and Scientific Computation. The Clarendon Press, Oxford University Press, New York, 2003. doi: 10.1093/acprof:oso/9780198506546.001.0001.

[2]

J. T. Betts, S. L. Campbell and K. C. Thompson, Optimal control software for constrained nonlinear systems with delays, in IEEE International Symposium on Computer-Aided Control System Design (CACSD), IEEE, Denver, CO, 2011,444–449.

[3]

L. T. Biegler, Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, MOS-SIAM Series on Optimization, Vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719383.

[4]

Q. Chai, R. Loxton, K. L. Teo and C. Yang, Time-delay estimation for nonlinear systems with piecewise-constant input, Appl. Math. Comput., 219 (2013), 9543-9560.  doi: 10.1016/j.amc.2013.03.015.

[5]

Q. Chai, R. Loxton, K. L. Teo and C. Yang, A unified parameter identification method for nonlinear time-delay systems, J. Ind. Manag. Optim., 9 (2013), 471-486.  doi: 10.3934/jimo.2013.9.471.

[6]

M. Diehl, H. J. Ferreau and N. Haverbeke, Efficient numerical methods for nonlinear MPC and moving horizon estimation, in Nonlinear Model Predictive Control, Lecture Notes in Control and Information Sciences, Vol. 384, Springer, Berlin, Heidelberg, 2009,391–417. doi: 10.1007/978-3-642-01094-1_32.

[7]

A. Griewank, Evaluating Derivatives, Principles and Techniques of Algorithmic Differentiation, Frontiers in Applied Mathematics, Vol. 19, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.

[8]

W. Horbelt, J. Timmer and H. U. Voss, Parameter estimation in nonlinear delayed feedback systems from noisy data, Physics Letter A, 299 (2002), 513-521.  doi: 10.1016/S0375-9601(02)00748-X.

[9]

C. Jiang, Z. Guo, X. Li, H. Wang and M. Yu, An efficient adjoint computational method based on lifted IRK integrator and exact penalty function for optimal control problems involving continuous inequality constraints, Discrete Contin. Dyn. Syst. Ser. S, 13 (2020), 1845-1865.  doi: 10.3934/dcdss.2020109.

[10]

C. Jiang, S. Wu, X. Li and C. Yu, An efficient algorithm to state-delay identification based on a collocation integrator and adjoint sensitivity propagation, in Proc. of the 38th Chinese Control Conf., Guangzhou, 2019, 1905–1910. doi: 10.23919/ChiCC.2019.8865925.

[11]

C. Jiang, K. Xie, C. Yu, M. Yu, H. Wang, Y. He and K. L. Teo, A sequential computational approach to optimal control problems for differential-algebraic systems based on efficient implicit Runge-Kutta integration, Appl. Math. Model., 58 (2018), 313-330.  doi: 10.1016/j.apm.2017.05.015.

[12]

S. M. Lenz, J. P. Schlöder and H. G. Bock, Numerical computation of derivatives in systems of delay differential equations, Math. Comput. Simulation, 96 (2014), 124-156.  doi: 10.1016/j.matcom.2013.08.003.

[13]

Q. Lin, R. Loxton and K. L. Teo, The control parameterization method for nonlinear optimal control: A survey, J. Ind. Manag. Optim., 10 (2014), 275-309.  doi: 10.3934/jimo.2014.10.275.

[14]

Q. Lin, R. Loxton, C. Xu and K. L. Teo, Parameter estimation for nonlinear time-delay systems with noisy output measurements, Automatica J. IFAC, 60 (2015), 48-56.  doi: 10.1016/j.automatica.2015.06.028.

[15]

C. Liu, R. Loxton and K. L. Teo, Switching time and parameter optimization in nonlinear switched systems with multiple time-delays, J. Optim. Theory Appl., 163 (2014), 957-988.  doi: 10.1007/s10957-014-0533-7.

[16]

R. Loxton, K. L. Teo and V. Rehbock, An optimization approach to state-delay identification, IEEE Trans. Automat. Control, 55 (2010), 2113-2119.  doi: 10.1109/TAC.2010.2050710.

[17]

R. Quirynen, S. Gros and M. Diehl, Inexact newton-type optimization with iterated sensitivities, SIAM J. Optim., 28 (2018), 74-95.  doi: 10.1137/16M1079002.

[18]

R. Quirynen, S. Gros, B. Houska and M. Diehl, Lifted collocation integrators for direct optimal control in ACADO toolkit, Math. Program. Comput., 9 (2017), 527-571.  doi: 10.1007/s12532-017-0119-0.

[19]

J.-P. Richard, Time-delay systems: An overview of some recent advances and open problems, Automatica J. IFAC, 39 (2003), 1667-1694.  doi: 10.1016/S0005-1098(03)00167-5.

[20]

X. Tang and H. Xu, Multiple-interval pseudospectral approximation for nonlinear optimal control problems with time-varying delays, Appl. Math. Model., 68 (2019), 137-151.  doi: 10.1016/j.apm.2018.09.039.

[21]

K. L. Teo, C. J. Goh and K. H. Wong, A Unified Computational Approach to Optimal Control Problems, Pitman Monographs and Surveys in Pure and Applied Mathematics, Vol. 55, Longman Scientific & Technical, Harlow. Copublished in the United States with John Wiley & Sons, Inc., New York, 1991.

[22]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., Ser. A, 106 (2006), 25-57.  doi: 10.1007/s10107-004-0559-y.

[23]

D. Wu, Y. Bai and C. Yu, A new computational approach for optimal control problems with multiple time-delay, Automatica J. IFAC, 101 (2019), 388-395.  doi: 10.1016/j.automatica.2018.12.036.

[24]

C. Yu, Q. Lin, R. Loxton, K. L. Teo and G. Wang, A hybrid time-scaling transformation for time-delay optimal control problems, J. Optim. Theory Appl., 169 (2016), 876-901.  doi: 10.1007/s10957-015-0783-z.

Figure 1.  Forward simulation by multi-threading
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Connection of state trajectories in two shooting intervals
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Control trajectories
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  State trajectories
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Computational times with $ s_\mathrm{pc} = \mathrm{false} $ or $ \mathrm{true} $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Time complexity per shooting interval
flops
Newton iter. $ pqL[\frac{2}{3}(rn_x)^3] $
Sensitivity propagation (11) $ pq[p n_u n_x^2](n_\tau r+1)^2 $
(12) $ pq[n_p n_x^2](n_\tau r+1)^2 $
Continuity constraints (15) $ (n_\tau+1)(n_c+1)[(pn_u+n_p)n_x^2] $
(16) $ (n_\tau+1)(n_c+1)[(pn_u+n_p)n_x^2](n_\tau r+1) $
Tangential prediction (18) $ pq[n_x(n_x+n_u)(r+1)](n_\tau r+1) $
(19) $ pq[n_x(n_x+n_u)(r+1)]r $
Table Options

Download as excel

flops
Newton iter. $ pqL[\frac{2}{3}(rn_x)^3] $
Sensitivity propagation (11) $ pq[p n_u n_x^2](n_\tau r+1)^2 $
(12) $ pq[n_p n_x^2](n_\tau r+1)^2 $
Continuity constraints (15) $ (n_\tau+1)(n_c+1)[(pn_u+n_p)n_x^2] $
(16) $ (n_\tau+1)(n_c+1)[(pn_u+n_p)n_x^2](n_\tau r+1) $
Tangential prediction (18) $ pq[n_x(n_x+n_u)(r+1)](n_\tau r+1) $
(19) $ pq[n_x(n_x+n_u)(r+1)]r $
Table 2.  Space complexity per shooting interval
Memory usage
Forward simulation (7e) $ pqrn_\tau n_x $
(8b) $ (n_\tau+1)(n_c+1)n_x $
Sensitivity propagation (10b) $ pqrn_\tau(1+rn_\tau)(n_x+n_u)n_x $
(10c) $ (n_\tau+1)(n_c+1)(1+rn_\tau)(n_x+n_u)n_x $
(11b) $ p^2qrn_\tau n_u n_x $
(12b) $ pqrn_\tau n_p n_x $
Tangential prediction $ (\sigma,\theta) $ $ pn_u+n_p $
(7b) $ pqrn_x $
(9) $ pqr(1+rn_\tau)(n_x+n_u)n_x $
(10a) $ pq(1+rn_\tau)(n_x+n_u)n_x $
Table Options

Download as excel

Memory usage
Forward simulation (7e) $ pqrn_\tau n_x $
(8b) $ (n_\tau+1)(n_c+1)n_x $
Sensitivity propagation (10b) $ pqrn_\tau(1+rn_\tau)(n_x+n_u)n_x $
(10c) $ (n_\tau+1)(n_c+1)(1+rn_\tau)(n_x+n_u)n_x $
(11b) $ p^2qrn_\tau n_u n_x $
(12b) $ pqrn_\tau n_p n_x $
Tangential prediction $ (\sigma,\theta) $ $ pn_u+n_p $
(7b) $ pqrn_x $
(9) $ pqr(1+rn_\tau)(n_x+n_u)n_x $
(10a) $ pq(1+rn_\tau)(n_x+n_u)n_x $
Table 3.  Computational time (CPU time for $ s = 1 $ and clock time for $ s>1 $) and cost for different $ (s,p,q) $
$ s $ $ p $ $ q $ total time (ms) cost
1 64 1 1337 0.891539
1 8 8 1065 0.899012
2 4 8 405 0.906770
4 2 8 263 0.899053
8 1 8 362 0.899096
Table Options

Download as excel

$ s $ $ p $ $ q $ total time (ms) cost
1 64 1 1337 0.891539
1 8 8 1065 0.899012
2 4 8 405 0.906770
4 2 8 263 0.899053
8 1 8 362 0.899096
[1]

Sihong Shao, Huazhong Tang. Higher-order accurate Runge-Kutta discontinuous Galerkin methods for a nonlinear Dirac model. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 623-640. doi: 10.3934/dcdsb.2006.6.623
[2]

Antonella Zanna. Symplectic P-stable additive Runge—Kutta methods. Journal of Computational Dynamics, 2022, 9 (2) : 299-328. doi: 10.3934/jcd.2021030
[3]

Elisa Giesecke, Axel Kröner. Classification with Runge-Kutta networks and feature space augmentation. Journal of Computational Dynamics, 2021, 8 (4) : 495-520. doi: 10.3934/jcd.2021018
[4]

Antonia Katzouraki, Tania Stathaki. Intelligent traffic control on internet-like topologies - integration of graph principles to the classic Runge--Kutta method. Conference Publications, 2009, 2009 (Special) : 404-415. doi: 10.3934/proc.2009.2009.404
[5]

Akram Kheirabadi, Asadollah Mahmoudzadeh Vaziri, Sohrab Effati. Linear optimal control of time delay systems via Hermite wavelet. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 143-156. doi: 10.3934/naco.2019044
[6]

Da Xu. Numerical solutions of viscoelastic bending wave equations with two term time kernels by Runge-Kutta convolution quadrature. Discrete and Continuous Dynamical Systems - B, 2017, 22 (6) : 2389-2416. doi: 10.3934/dcdsb.2017122
[7]

Z. Foroozandeh, Maria do rosário de Pinho, M. Shamsi. On numerical methods for singular optimal control problems: An application to an AUV problem. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2219-2235. doi: 10.3934/dcdsb.2019092
[8]

Martin Benning, Elena Celledoni, Matthias J. Ehrhardt, Brynjulf Owren, Carola-Bibiane Schönlieb. Deep learning as optimal control problems: Models and numerical methods. Journal of Computational Dynamics, 2019, 6 (2) : 171-198. doi: 10.3934/jcd.2019009
[9]

Xiaowei Pang, Haiming Song, Xiaoshen Wang, Jiachuan Zhang. Efficient numerical methods for elliptic optimal control problems with random coefficient. Electronic Research Archive, 2020, 28 (2) : 1001-1022. doi: 10.3934/era.2020053
[10]

Chunjuan Hou, Yanping Chen, Zuliang Lu. Superconvergence property of finite element methods for parabolic optimal control problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 927-945. doi: 10.3934/jimo.2011.7.927
[11]

Eugene Kashdan, Dominique Duncan, Andrew Parnell, Heinz Schättler. Mathematical methods in systems biology. Mathematical Biosciences & Engineering, 2016, 13 (6) : i-ii. doi: 10.3934/mbe.201606i
[12]

Gildas Besançon, Didier Georges, Zohra Benayache. Towards nonlinear delay-based control for convection-like distributed systems: The example of water flow control in open channel systems. Networks and Heterogeneous Media, 2009, 4 (2) : 211-221. doi: 10.3934/nhm.2009.4.211
[13]

Tayel Dabbous. Adaptive control of nonlinear systems using fuzzy systems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 861-880. doi: 10.3934/jimo.2010.6.861
[14]

Zhen-Zhen Tao, Bing Sun. Space-time spectral methods for a fourth-order parabolic optimal control problem in three control constraint cases. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022080
[15]

Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001
[16]

Ta T.H. Trang, Vu N. Phat, Adly Samir. Finite-time stabilization and $H_\infty$ control of nonlinear delay systems via output feedback. Journal of Industrial and Management Optimization, 2016, 12 (1) : 303-315. doi: 10.3934/jimo.2016.12.303
[17]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1
[18]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[19]

Liangquan Zhang, Qing Zhou, Juan Yang. Necessary condition for optimal control of doubly stochastic systems. Mathematical Control and Related Fields, 2020, 10 (2) : 379-403. doi: 10.3934/mcrf.2020002
[20]

Elena Goncharova, Maxim Staritsyn. Optimal control of dynamical systems with polynomial impulses. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4367-4384. doi: 10.3934/dcds.2015.35.4367

2021 Impact Factor: 1.411

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy