American Institute of Mathematical Sciences

Advanced
July  2015, 35(7): 2997-3013. doi: 10.3934/dcds.2015.35.2997

Steplength thresholds for invariance preserving of discretization methods of dynamical systems on a polyhedron

Zoltán Horváth 1, , Yunfei Song 2, and  Tamás Terlaky 2,

1. 

Department of Mathematics and Computational Sciences, Széchenyi István University, 9026 Győr, Egyetem tér 1, Hungary
2. 

Department of Industrial and Systems Engineering, Lehigh University, 200 West Packer Avenue, Bethlehem, PA, 18015-1582, United States, United States

Received  June 2014 Revised  October 2014 Published  January 2015

Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically compute the steplength threshold. For rational function type discretization methods we derive a valid steplength threshold for invariance preserving, which can be computed by using an analogous algorithm as in the first case. The relationship between the previous two types of discretization methods and the forward Euler method is studied. Finally, we show that, for the forward Euler method, the largest steplength threshold for invariance preserving can be computed by solving a finite number of linear optimization problems.
Keywords: invariance preserving., Dynamical system, discretization method, invariant set, polyhedron.
Mathematics Subject Classification: Primary: 34A30, 37M25, 65K0.
Citation: Zoltán Horváth, Yunfei Song, Tamás Terlaky. Steplength thresholds for invariance preserving of discretization methods of dynamical systems on a polyhedron. Discrete and Continuous Dynamical Systems, 2015, 35 (7) : 2997-3013. doi: 10.3934/dcds.2015.35.2997
References:
[1]

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Nashua, 1998.

[2]

G. Bitsoris, On the positive invariance of polyhedral sets for discrete-time systems, System and Control Letters, 11 (1998), 243-248. doi: 10.1016/0167-6911(88)90065-5.

[3]

F. Blanchini, Set invariance in control, Automatica, 35 (1999), 1747-1767. doi: 10.1016/S0005-1098(99)00113-2.

[4]

F. Blanchini and S. Miani, Constrained stabilization of continuous-time linear systems, Systems and Control Letters, 28 (1996), 95-102. doi: 10.1016/0167-6911(96)00013-8.

[5]

F. Blanchini, S. Miani, C. E. T. Dórea and J. C. Hennet, Discussion on: '(A, B)- invariance conditions of polyhedral domains for continuous-time systems by C. E. T. Dórea and J.-C. Hennet', European Journal of Control, 5 (1999), 82-86. doi: 10.1016/S0947-3580(99)70142-1.

[6]

S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM Studies in Applied Mathematics, Philadelphia, 1994. doi: 10.1137/1.9781611970777.

[7]

E. B. Castelan and J. C. Hennet, On invariant polyhedra of continuous-time linear systems, IEEE Transactions on Automatic Control, 38 (1993), 1680-1685. doi: 10.1109/9.262058.

[8]

C. E. T. Dórea and J. C. Hennet, (A, B)-invariance conditions of polyhedral domains for continuous-time systems, European Journal of Control, 5 (1999), 70-81.

[9]

C. E. T. Dórea and J. C. Hennet, (A,B)-invariant polyhedral sets of linear discrete time systems, Journal of Optimization Theory and Applications, 103 (1999), 521-542. doi: 10.1023/A:1021727806358.

[10]

E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems, Springer-Verlag, New York, 1993.

[11]

N. J. Higham, Functions of Matrices: Theory and Computation, Society for Industrial and Applied Mathematics, Philadelphia, 2008. doi: 10.1137/1.9780898717778.

[12]

R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1990.

[13]

Z. Horváth, Invariant cones and polyhedra for dynamical systems, in Proceeding of the International Conference in Memoriam Gyula Farkas, Cluj Univ. Press, Cluj-Napoca, 2006, 65-74.

[14]

Z. Horváth, On the positivity step size threshold of Runge-Kutta methods, Applied Numerical Mathematics, 53 (2005), 341-356. doi: 10.1016/j.apnum.2004.08.026.

[15]

Z. Horváth, Y. Song and T. Terlaky, Invariance Preserving Discretization Methods of Dynamical Systems, Lehigh University, Department of Industrial and Systems Engineering, Technical Report 14T-009, 2014.

[16]

Z. Horváth, Y. Song and T. Terlaky, A Novel Unified Approach to Invariance in Control, Lehigh University, Department of Industrial and Systems Engineering, Technical Report 14T-003, 2014.

[17]

J. F. B. M. Kraaijevanger, Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems, Numerische Mathematik, 48 (1986), 303-322. doi: 10.1007/BF01389477.

[18]

R. Loewy and H. Schneider, Positive operators on the $n$-dimensional ice cream cone, Journal of Mathematical Analysis and Applications, 49 (1975), 375-392. doi: 10.1016/0022-247X(75)90186-9.

[19]

C. Roos, T. Terlaky and J.-Ph. Vial, Interior Point Methods for Linear Optimization, Springer Science, Heidelberg, 2006.

[20]

M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numerische Mathematik, 42 (1983), 271-290. doi: 10.1007/BF01389573.

[21]

R. Stern and H. Wolkowicz, Exponential nonnegativity on the ice cream cone, SIAM Journal on Matrix Analysis and Applications, 12 (1991), 160-165. doi: 10.1137/0612012.

[22]

B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Lectures Series, American Mathematical Society, 2002.

[23]

J. Vandergraft, Spectral properties of matrices which have invariant cones, SIAM Journal on Applied Mathematics, 16 (1968), 1208-1222. doi: 10.1137/0116101.

show all references

References:
[1]

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Nashua, 1998.

[2]

G. Bitsoris, On the positive invariance of polyhedral sets for discrete-time systems, System and Control Letters, 11 (1998), 243-248. doi: 10.1016/0167-6911(88)90065-5.

[3]

F. Blanchini, Set invariance in control, Automatica, 35 (1999), 1747-1767. doi: 10.1016/S0005-1098(99)00113-2.

[4]

F. Blanchini and S. Miani, Constrained stabilization of continuous-time linear systems, Systems and Control Letters, 28 (1996), 95-102. doi: 10.1016/0167-6911(96)00013-8.

[5]

F. Blanchini, S. Miani, C. E. T. Dórea and J. C. Hennet, Discussion on: '(A, B)- invariance conditions of polyhedral domains for continuous-time systems by C. E. T. Dórea and J.-C. Hennet', European Journal of Control, 5 (1999), 82-86. doi: 10.1016/S0947-3580(99)70142-1.

[6]

S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM Studies in Applied Mathematics, Philadelphia, 1994. doi: 10.1137/1.9781611970777.

[7]

E. B. Castelan and J. C. Hennet, On invariant polyhedra of continuous-time linear systems, IEEE Transactions on Automatic Control, 38 (1993), 1680-1685. doi: 10.1109/9.262058.

[8]

C. E. T. Dórea and J. C. Hennet, (A, B)-invariance conditions of polyhedral domains for continuous-time systems, European Journal of Control, 5 (1999), 70-81.

[9]

C. E. T. Dórea and J. C. Hennet, (A,B)-invariant polyhedral sets of linear discrete time systems, Journal of Optimization Theory and Applications, 103 (1999), 521-542. doi: 10.1023/A:1021727806358.

[10]

E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems, Springer-Verlag, New York, 1993.

[11]

N. J. Higham, Functions of Matrices: Theory and Computation, Society for Industrial and Applied Mathematics, Philadelphia, 2008. doi: 10.1137/1.9780898717778.

[12]

R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1990.

[13]

Z. Horváth, Invariant cones and polyhedra for dynamical systems, in Proceeding of the International Conference in Memoriam Gyula Farkas, Cluj Univ. Press, Cluj-Napoca, 2006, 65-74.

[14]

Z. Horváth, On the positivity step size threshold of Runge-Kutta methods, Applied Numerical Mathematics, 53 (2005), 341-356. doi: 10.1016/j.apnum.2004.08.026.

[15]

Z. Horváth, Y. Song and T. Terlaky, Invariance Preserving Discretization Methods of Dynamical Systems, Lehigh University, Department of Industrial and Systems Engineering, Technical Report 14T-009, 2014.

[16]

Z. Horváth, Y. Song and T. Terlaky, A Novel Unified Approach to Invariance in Control, Lehigh University, Department of Industrial and Systems Engineering, Technical Report 14T-003, 2014.

[17]

J. F. B. M. Kraaijevanger, Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems, Numerische Mathematik, 48 (1986), 303-322. doi: 10.1007/BF01389477.

[18]

R. Loewy and H. Schneider, Positive operators on the $n$-dimensional ice cream cone, Journal of Mathematical Analysis and Applications, 49 (1975), 375-392. doi: 10.1016/0022-247X(75)90186-9.

[19]

C. Roos, T. Terlaky and J.-Ph. Vial, Interior Point Methods for Linear Optimization, Springer Science, Heidelberg, 2006.

[20]

M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numerische Mathematik, 42 (1983), 271-290. doi: 10.1007/BF01389573.

[21]

R. Stern and H. Wolkowicz, Exponential nonnegativity on the ice cream cone, SIAM Journal on Matrix Analysis and Applications, 12 (1991), 160-165. doi: 10.1137/0612012.

[22]

B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Lectures Series, American Mathematical Society, 2002.

[23]

J. Vandergraft, Spectral properties of matrices which have invariant cones, SIAM Journal on Applied Mathematics, 16 (1968), 1208-1222. doi: 10.1137/0116101.

[1]

Michal Fečkan, Michal Pospíšil. Discretization of dynamical systems with first integrals. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3543-3554. doi: 10.3934/dcds.2013.33.3543
[2]

Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002
[3]

Rui Kuang, Xiangdong Ye. The return times set and mixing for measure preserving transformations. Discrete and Continuous Dynamical Systems, 2007, 18 (4) : 817-827. doi: 10.3934/dcds.2007.18.817
[4]

Mikhail B. Sevryuk. Invariant tori in quasi-periodic non-autonomous dynamical systems via Herman's method. Discrete and Continuous Dynamical Systems, 2007, 18 (2&3) : 569-595. doi: 10.3934/dcds.2007.18.569
[5]

Zeng-Zhen Tan, Rong Hu, Ming Zhu, Ya-Ping Fang. A dynamical system method for solving the split convex feasibility problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 2989-3011. doi: 10.3934/jimo.2020104
[6]

Matti Lassas, Eero Saksman, Samuli Siltanen. Discretization-invariant Bayesian inversion and Besov space priors. Inverse Problems and Imaging, 2009, 3 (1) : 87-122. doi: 10.3934/ipi.2009.3.87
[7]

Sho Matsumoto, Jonathan Novak. A moment method for invariant ensembles. Electronic Research Announcements, 2018, 25: 60-71. doi: 10.3934/era.2018.25.007
[8]

Michihiro Hirayama. Periodic probability measures are dense in the set of invariant measures. Discrete and Continuous Dynamical Systems, 2003, 9 (5) : 1185-1192. doi: 10.3934/dcds.2003.9.1185
[9]

Ji Li, Kening Lu, Peter W. Bates. Invariant foliations for random dynamical systems. Discrete and Continuous Dynamical Systems, 2014, 34 (9) : 3639-3666. doi: 10.3934/dcds.2014.34.3639
[10]

Luca Dieci, Timo Eirola, Cinzia Elia. Periodic orbits of planar discontinuous system under discretization. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2743-2762. doi: 10.3934/dcdsb.2018103
[11]

Luis C. García-Naranjo, Mats Vermeeren. Structure preserving discretization of time-reparametrized Hamiltonian systems with application to nonholonomic mechanics. Journal of Computational Dynamics, 2021, 8 (3) : 241-271. doi: 10.3934/jcd.2021011
[12]

Rafael de la Llave, Jason D. Mireles James. Parameterization of invariant manifolds by reducibility for volume preserving and symplectic maps. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4321-4360. doi: 10.3934/dcds.2012.32.4321
[13]

Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[14]

Chui-Jie Wu, Hongliang Zhao. Generalized HWD-POD method and coupling low-dimensional dynamical system of turbulence. Conference Publications, 2001, 2001 (Special) : 371-379. doi: 10.3934/proc.2001.2001.371
[15]

Ivan Werner. Equilibrium states and invariant measures for random dynamical systems. Discrete and Continuous Dynamical Systems, 2015, 35 (3) : 1285-1326. doi: 10.3934/dcds.2015.35.1285
[16]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete and Continuous Dynamical Systems, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129
[17]

Nasab Yassine. Quantitative recurrence of some dynamical systems preserving an infinite measure in dimension one. Discrete and Continuous Dynamical Systems, 2018, 38 (1) : 343-361. doi: 10.3934/dcds.2018017
[18]

Yaofeng Su. Almost surely invariance principle for non-stationary and random intermittent dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6585-6597. doi: 10.3934/dcds.2019286
[19]

Nils Ackermann, Thomas Bartsch, Petr Kaplický. An invariant set generated by the domain topology for parabolic semiflows with small diffusion. Discrete and Continuous Dynamical Systems, 2007, 18 (4) : 613-626. doi: 10.3934/dcds.2007.18.613
[20]

Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems and Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (96)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy