January  2014, 1(1): 39-69. doi: 10.3934/jcd.2014.1.39

The computation of convex invariant sets via Newton's method

1. 

Chair of Applied Mathematics, University of Bayreuth, 95440 Bayreuth, Germany

2. 

Chair of Applied Mathematics, University of Paderborn, 33098 Paderborn, Germany, Germany, Germany

3. 

Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ 08544, United States

Received  July 2012 Revised  February 2014 Published  April 2014

In this paper we present a novel approach to the computation of convex invariant sets of dynamical systems. Employing a Banach space formalism to describe differences of convex compact subsets of $\mathbb{R}^n$ by directed sets, we are able to formulate the property of a convex, compact set to be invariant as a zero-finding problem in this Banach space. We need either the additional restrictive assumption that the image of sets from a subclass of convex compact sets under the dynamics remains convex, or we have to convexify these images. In both cases we can apply Newton's method in Banach spaces to approximate such invariant sets if an appropriate smoothness of a set-valued map holds. The theoretical foundations for realizing this approach are analyzed, and it is illustrated first by analytical and then by numerical examples.
Citation: R. Baier, M. Dellnitz, M. Hessel-von Molo, S. Sertl, I. G. Kevrekidis. The computation of convex invariant sets via Newton's method. Journal of Computational Dynamics, 2014, 1 (1) : 39-69. doi: 10.3934/jcd.2014.1.39
References:
[1]

Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1999. doi: 10.1007/978-1-4612-1576-9.  Google Scholar

[2]

Optim. Meth. Softw., 22 (2007), 433-452. doi: 10.1080/10556780600604999.  Google Scholar

[3]

in Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950) (eds. N. Hadjisavvas and P. M. Pardalos), vol. 54 of Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, Dordrecht-Boston-London, (2001), 501-514. doi: 10.1007/978-1-4613-0279-7_32.  Google Scholar

[4]

in Nonlinear Analysis and Optimization II: Optimization. A Conference in Celebration of Alex Ioffe's 70th and Simeon Reich's 60th Birthdays, June 18-24, (2008), Haifa, Israel (eds. A. Leizarowitz, B. S. Mordukhovich, I. Shafrir and A. J. Zaslavski), vol. 513 of AMS Contemp. Math., AMS and Bar-Ilan University, (2010), 27-43, http://www.ams.org/bookstore-getitem/item=CONM-514. doi: 10.1090/conm/514/10098.  Google Scholar

[5]

in Proceedings on the 8th International Conference on "Large-Scale Scientific Computations'' (LSSC 2011), June 6-10, 2011, Sozopol, Bulgaria (eds. I. Lirkov, S. Margenov and J. Wanśiewski), vol. 7116 of Lecture Notes in Comput. Sci., Springer-Verlag, Berlin-Heidelberg, 2012, 91-98. doi: 10.1007/978-3-642-29843-1_9.  Google Scholar

[6]

J. Approx. Theory, 163 (2011), 1349-1372. doi: 10.1016/j.jat.2010.11.004.  Google Scholar

[7]

Set-Valued Anal., 9 (2001), 217-245. doi: 10.1023/A:1012046027626.  Google Scholar

[8]

Set-Valued Anal., 9 (2001), 247-272. doi: 10.1023/A:1012009529492.  Google Scholar

[9]

IMA J. Numer. Anal., 10 (1990), 379-405, http://imajna.oxfordjournals.org/cgi/content/abstract/10/3/379. doi: 10.1093/imanum/10.3.379.  Google Scholar

[10]

Automatica, 35 (1999), 1747-1767. doi: 10.1016/S0005-1098(99)00113-2.  Google Scholar

[11]

in Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems (ed. B. Fiedler), Springer, (2001), 145-174.  Google Scholar

[12]

Numer. Math., 75 (1997), 293-317. doi: 10.1007/s002110050240.  Google Scholar

[13]

SIAM J. Numer. Anal., 36 (1999), 491-515. doi: 10.1137/S0036142996313002.  Google Scholar

[14]

vol. 7 of Approximation and Optimization, Peter Lang, Frankfurt am Main-Berlin-Bern-New York-Paris-Wien, 1995, Updated and revised English edition of V. F. Demyanov, A. M. Rubinov, Foundations of Nonsmooth Analysis, and Quasidifferentiable Calculus, Optimizatsiya i Operatsiĭ 23, Nauka, Moscow, 1990 (in Russian).  Google Scholar

[15]

SIAM J. Sci. Statist. Comput., 12 (1991), 607-647, http://link.aip.org/link/?SCE/12/607/1. doi: 10.1137/0912033.  Google Scholar

[16]

Pliska Stud. Math. Bulgar., 5 (1983), 105-117.  Google Scholar

[17]

Nonlinear Anal., 53 (2003), 997-1015. doi: 10.1016/S0362-546X(03)00036-1.  Google Scholar

[18]

Math. Z., 53 (1950), 210-218. doi: 10.1007/BF01175656.  Google Scholar

[19]

Reliab. Comput., 12 (2006), 253-272. doi: 10.1007/s11155-006-9000-y.  Google Scholar

[20]

ZAMM Z. Angew. Math. Phys., 46 (1995), 171-187. doi: 10.1007/BF00944751.  Google Scholar

[21]

Internat. J. Bifurc. Chaos Appl. Sci. Engrg., 2 (1992), 727-771. doi: 10.1142/S0218127492000422.  Google Scholar

[22]

Dokl. Akad. Nauk SSSR, 59 (1948), 1237-1240.  Google Scholar

[23]

Dokl. Akad. Nauk SSSR, 76 (1951), 17-20.  Google Scholar

[24]

2nd edition, Pergamon Press, Oxford, 1982, Translated from the Russian by H. L. Silcock.  Google Scholar

[25]

Phys. D, 16 (1985), 243-251, http://www.sciencedirect.com/science/article/B6TVK-46MNK8Y-2T /2/48df9752ceb87d5170b0eabe206cbfb9. doi: 10.1016/0167-2789(85)90061-2.  Google Scholar

[26]

AIChE Journ., 50 (2004), 1346-1354. doi: 10.1002/aic.10106.  Google Scholar

[27]

Commun. Math. Sci., 1 (2003), 715-762, http://projecteuclid.org/getRecord?id=euclid.cms/1119655353. doi: 10.4310/CMS.2003.v1.n4.a5.  Google Scholar

[28]

vol. 60 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[29]

Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15 (2005), 763-791. doi: 10.1142/S0218127405012533.  Google Scholar

[30]

Computing (Arch. Elektron. Rechnen), 4 (1969), 187-201.  Google Scholar

[31]

Computing (Arch. Elektron. Rechnen), 5 (1970), 356-370.  Google Scholar

[32]

Arch. Appl. Mech., 55 (1985), 285-294. doi: 10.1007/BF00538223.  Google Scholar

[33]

Comput. Suppl., 2 (1980), 69-84.  Google Scholar

[34]

in Iterative solution of nonlinear systems of equations (Oberwolfach, 1982), vol. 953 of Lecture Notes in Math., Springer, Berlin, (1982), 106-124.  Google Scholar

[35]

Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[36]

Department of Mathematics, University of Bayreuth, Germany, 2007.  Google Scholar

[37]

J. Optim. Theory Appl., 99 (1998), 553-583. doi: 10.1023/A:1021798932766.  Google Scholar

[38]

Set-Valued Anal., 9 (2001), 159-168, Special issue on Wellposedness in Optimization and Related Topics (Gargnano, 1999). doi: 10.1023/A:1011287523150.  Google Scholar

[39]

Sov. Math., Dokl., 8 (1967), 910-912. Google Scholar

[40]

vol. 28 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 1970.  Google Scholar

[41]

Optimization, 23 (1992), 179-188. doi: 10.1080/02331939208843757.  Google Scholar

[42]

Set-Valued Anal., 3 (1995), 143-156. doi: 10.1007/BF01038596.  Google Scholar

[43]

Ind. Engrg. Chem. Res., 42 (2003), 6795-6801. doi: 10.1021/ie021062w.  Google Scholar

[44]

Proc. Natl. Acad. Sci., 97 (2000), 9840-9843, http://www.pnas.org/content/97/18/9840.abstract. doi: 10.1073/pnas.97.18.9840.  Google Scholar

[45]

in Numerical methods for bifurcation problems and large-scale dynamical systems (Minneapolis, MN, 1997), vol. 119 of IMA Vol. Math. Appl., Springer, New York, (2000), 453-466. doi: 10.1007/978-1-4612-1208-9_20.  Google Scholar

[46]

Math. Comp., 68 (1999), 169-186. doi: 10.1090/S0025-5718-99-00999-0.  Google Scholar

[47]

Numer. Math., 49 (1986), 203-220. doi: 10.1007/BF01389624.  Google Scholar

show all references

References:
[1]

Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1999. doi: 10.1007/978-1-4612-1576-9.  Google Scholar

[2]

Optim. Meth. Softw., 22 (2007), 433-452. doi: 10.1080/10556780600604999.  Google Scholar

[3]

in Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950) (eds. N. Hadjisavvas and P. M. Pardalos), vol. 54 of Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, Dordrecht-Boston-London, (2001), 501-514. doi: 10.1007/978-1-4613-0279-7_32.  Google Scholar

[4]

in Nonlinear Analysis and Optimization II: Optimization. A Conference in Celebration of Alex Ioffe's 70th and Simeon Reich's 60th Birthdays, June 18-24, (2008), Haifa, Israel (eds. A. Leizarowitz, B. S. Mordukhovich, I. Shafrir and A. J. Zaslavski), vol. 513 of AMS Contemp. Math., AMS and Bar-Ilan University, (2010), 27-43, http://www.ams.org/bookstore-getitem/item=CONM-514. doi: 10.1090/conm/514/10098.  Google Scholar

[5]

in Proceedings on the 8th International Conference on "Large-Scale Scientific Computations'' (LSSC 2011), June 6-10, 2011, Sozopol, Bulgaria (eds. I. Lirkov, S. Margenov and J. Wanśiewski), vol. 7116 of Lecture Notes in Comput. Sci., Springer-Verlag, Berlin-Heidelberg, 2012, 91-98. doi: 10.1007/978-3-642-29843-1_9.  Google Scholar

[6]

J. Approx. Theory, 163 (2011), 1349-1372. doi: 10.1016/j.jat.2010.11.004.  Google Scholar

[7]

Set-Valued Anal., 9 (2001), 217-245. doi: 10.1023/A:1012046027626.  Google Scholar

[8]

Set-Valued Anal., 9 (2001), 247-272. doi: 10.1023/A:1012009529492.  Google Scholar

[9]

IMA J. Numer. Anal., 10 (1990), 379-405, http://imajna.oxfordjournals.org/cgi/content/abstract/10/3/379. doi: 10.1093/imanum/10.3.379.  Google Scholar

[10]

Automatica, 35 (1999), 1747-1767. doi: 10.1016/S0005-1098(99)00113-2.  Google Scholar

[11]

in Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems (ed. B. Fiedler), Springer, (2001), 145-174.  Google Scholar

[12]

Numer. Math., 75 (1997), 293-317. doi: 10.1007/s002110050240.  Google Scholar

[13]

SIAM J. Numer. Anal., 36 (1999), 491-515. doi: 10.1137/S0036142996313002.  Google Scholar

[14]

vol. 7 of Approximation and Optimization, Peter Lang, Frankfurt am Main-Berlin-Bern-New York-Paris-Wien, 1995, Updated and revised English edition of V. F. Demyanov, A. M. Rubinov, Foundations of Nonsmooth Analysis, and Quasidifferentiable Calculus, Optimizatsiya i Operatsiĭ 23, Nauka, Moscow, 1990 (in Russian).  Google Scholar

[15]

SIAM J. Sci. Statist. Comput., 12 (1991), 607-647, http://link.aip.org/link/?SCE/12/607/1. doi: 10.1137/0912033.  Google Scholar

[16]

Pliska Stud. Math. Bulgar., 5 (1983), 105-117.  Google Scholar

[17]

Nonlinear Anal., 53 (2003), 997-1015. doi: 10.1016/S0362-546X(03)00036-1.  Google Scholar

[18]

Math. Z., 53 (1950), 210-218. doi: 10.1007/BF01175656.  Google Scholar

[19]

Reliab. Comput., 12 (2006), 253-272. doi: 10.1007/s11155-006-9000-y.  Google Scholar

[20]

ZAMM Z. Angew. Math. Phys., 46 (1995), 171-187. doi: 10.1007/BF00944751.  Google Scholar

[21]

Internat. J. Bifurc. Chaos Appl. Sci. Engrg., 2 (1992), 727-771. doi: 10.1142/S0218127492000422.  Google Scholar

[22]

Dokl. Akad. Nauk SSSR, 59 (1948), 1237-1240.  Google Scholar

[23]

Dokl. Akad. Nauk SSSR, 76 (1951), 17-20.  Google Scholar

[24]

2nd edition, Pergamon Press, Oxford, 1982, Translated from the Russian by H. L. Silcock.  Google Scholar

[25]

Phys. D, 16 (1985), 243-251, http://www.sciencedirect.com/science/article/B6TVK-46MNK8Y-2T /2/48df9752ceb87d5170b0eabe206cbfb9. doi: 10.1016/0167-2789(85)90061-2.  Google Scholar

[26]

AIChE Journ., 50 (2004), 1346-1354. doi: 10.1002/aic.10106.  Google Scholar

[27]

Commun. Math. Sci., 1 (2003), 715-762, http://projecteuclid.org/getRecord?id=euclid.cms/1119655353. doi: 10.4310/CMS.2003.v1.n4.a5.  Google Scholar

[28]

vol. 60 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[29]

Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15 (2005), 763-791. doi: 10.1142/S0218127405012533.  Google Scholar

[30]

Computing (Arch. Elektron. Rechnen), 4 (1969), 187-201.  Google Scholar

[31]

Computing (Arch. Elektron. Rechnen), 5 (1970), 356-370.  Google Scholar

[32]

Arch. Appl. Mech., 55 (1985), 285-294. doi: 10.1007/BF00538223.  Google Scholar

[33]

Comput. Suppl., 2 (1980), 69-84.  Google Scholar

[34]

in Iterative solution of nonlinear systems of equations (Oberwolfach, 1982), vol. 953 of Lecture Notes in Math., Springer, Berlin, (1982), 106-124.  Google Scholar

[35]

Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[36]

Department of Mathematics, University of Bayreuth, Germany, 2007.  Google Scholar

[37]

J. Optim. Theory Appl., 99 (1998), 553-583. doi: 10.1023/A:1021798932766.  Google Scholar

[38]

Set-Valued Anal., 9 (2001), 159-168, Special issue on Wellposedness in Optimization and Related Topics (Gargnano, 1999). doi: 10.1023/A:1011287523150.  Google Scholar

[39]

Sov. Math., Dokl., 8 (1967), 910-912. Google Scholar

[40]

vol. 28 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 1970.  Google Scholar

[41]

Optimization, 23 (1992), 179-188. doi: 10.1080/02331939208843757.  Google Scholar

[42]

Set-Valued Anal., 3 (1995), 143-156. doi: 10.1007/BF01038596.  Google Scholar

[43]

Ind. Engrg. Chem. Res., 42 (2003), 6795-6801. doi: 10.1021/ie021062w.  Google Scholar

[44]

Proc. Natl. Acad. Sci., 97 (2000), 9840-9843, http://www.pnas.org/content/97/18/9840.abstract. doi: 10.1073/pnas.97.18.9840.  Google Scholar

[45]

in Numerical methods for bifurcation problems and large-scale dynamical systems (Minneapolis, MN, 1997), vol. 119 of IMA Vol. Math. Appl., Springer, New York, (2000), 453-466. doi: 10.1007/978-1-4612-1208-9_20.  Google Scholar

[46]

Math. Comp., 68 (1999), 169-186. doi: 10.1090/S0025-5718-99-00999-0.  Google Scholar

[47]

Numer. Math., 49 (1986), 203-220. doi: 10.1007/BF01389624.  Google Scholar

[1]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021012

[2]

Mikhail Dokuchaev, Guanglu Zhou, Song Wang. A modification of Galerkin's method for option pricing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021077

[3]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[4]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[5]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

[6]

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

[7]

Maolin Cheng, Yun Liu, Jianuo Li, Bin Liu. Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021054

[8]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[9]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075

[10]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161

[11]

Jesús A. Álvarez López, Ramón Barral Lijó, John Hunton, Hiraku Nozawa, John R. Parker. Chaotic Delone sets. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3781-3796. doi: 10.3934/dcds.2021016

[12]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[13]

Skyler Simmons. Stability of Broucke's isosceles orbit. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3759-3779. doi: 10.3934/dcds.2021015

[14]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2677-2698. doi: 10.3934/dcds.2020381

[15]

Jun He, Guangjun Xu, Yanmin Liu. New Z-eigenvalue localization sets for tensors with applications. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021058

[16]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003

[17]

Tôn Việt Tạ. Strict solutions to stochastic semilinear evolution equations in M-type 2 Banach spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021050

[18]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[19]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3241-3271. doi: 10.3934/dcds.2020404

[20]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

 Impact Factor: 

Metrics

  • PDF downloads (81)
  • HTML views (0)
  • Cited by (6)

[Back to Top]