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]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[2]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[3]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[4]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[5]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[6]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[7]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164
[8]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[9]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[10]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[11]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045
[12]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020273
[13]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049
[14]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[16]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351
[17]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075
[18]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216
[19]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341
[20]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (58)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences