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 & Continuous Dynamical Systems - A, 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, (1998).   Google Scholar

[2]

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

[3]

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

[4]

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

[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.  doi: 10.1016/S0947-3580(99)70142-1.  Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[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.  doi: 10.1023/A:1021727806358.  Google Scholar

[10]

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

[11]

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

[12]

R. Horn and C. Johnson, Matrix Analysis,, Cambridge University Press, (1990).   Google Scholar

[13]

Z. Horváth, Invariant cones and polyhedra for dynamical systems,, in Proceeding of the International Conference in Memoriam Gyula Farkas, (2006), 65.   Google Scholar

[14]

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

[15]

Z. Horváth, Y. Song and T. Terlaky, Invariance Preserving Discretization Methods of Dynamical Systems,, Lehigh University, (2014).   Google Scholar

[16]

Z. Horváth, Y. Song and T. Terlaky, A Novel Unified Approach to Invariance in Control,, Lehigh University, (2014).   Google Scholar

[17]

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

[18]

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

[19]

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

[20]

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

[21]

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

[22]

B. Sturmfels, Solving Systems of Polynomial Equations,, CBMS Lectures Series, (2002).   Google Scholar

[23]

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

show all references

References:
[1]

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization,, Athena Scientific, (1998).   Google Scholar

[2]

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

[3]

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

[4]

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

[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.  doi: 10.1016/S0947-3580(99)70142-1.  Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[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.  doi: 10.1023/A:1021727806358.  Google Scholar

[10]

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

[11]

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

[12]

R. Horn and C. Johnson, Matrix Analysis,, Cambridge University Press, (1990).   Google Scholar

[13]

Z. Horváth, Invariant cones and polyhedra for dynamical systems,, in Proceeding of the International Conference in Memoriam Gyula Farkas, (2006), 65.   Google Scholar

[14]

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

[15]

Z. Horváth, Y. Song and T. Terlaky, Invariance Preserving Discretization Methods of Dynamical Systems,, Lehigh University, (2014).   Google Scholar

[16]

Z. Horváth, Y. Song and T. Terlaky, A Novel Unified Approach to Invariance in Control,, Lehigh University, (2014).   Google Scholar

[17]

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

[18]

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

[19]

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

[20]

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

[21]

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

[22]

B. Sturmfels, Solving Systems of Polynomial Equations,, CBMS Lectures Series, (2002).   Google Scholar

[23]

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

[1]

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

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

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

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

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

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

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

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

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

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
[11]

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

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

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

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

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

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

Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[18]

Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic & Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417
[19]

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

Pierluigi Colli, Shunsuke Kurima. Time discretization of a nonlinear phase field system in general domains. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3161-3179. doi: 10.3934/cpaa.2019142

2018 Impact Factor: 1.143

Tools

Metrics

  • PDF downloads (35)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences