The computation of convex invariant sets        via Newton's method

R. Baier; M. Dellnitz; M. Hessel-von Molo; S. Sertl; I. G. Kevrekidis

doi:10.3934/jcd.2014.1.39

Article Contents

2014, Volume 1, Issue 1: 39-69. Doi: 10.3934/jcd.2014.1.39

This issue Previous Article Global invariant manifolds near a Shilnikov homoclinic bifurcation Next Article Continuation and collapse of homoclinic tangles

The computation of convex invariant sets via Newton's method

1.
Chair of Applied Mathematics, University of Bayreuth, 95440 Bayreuth
2.
Chair of Applied Mathematics, University of Paderborn, 33098 Paderborn
3.
Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ 08544

Received: July 2012

Revised: February 2014

Published: January 2014

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 65J15, 52A20, 37M99, 26E25, 54C60.

Citation:

Related Papers

Cited by

References

[1]	J.-P. Aubin, Mutational and Morphological Analysis. Tools for Shape Evolution and Morphogenesis, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1999.doi: 10.1007/978-1-4612-1576-9.
[2]	R. Baier, C. Büskens, I. A. Chahma and M. Gerdts, Approximation of reachable sets by direct solution methods of optimal control problems, Optim. Meth. Softw., 22 (2007), 433-452.doi: 10.1080/10556780600604999.
[3]	R. Baier and E. M. Farkhi, Directed derivatives of convex compact-valued mappings, 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.
[4]	R. Baier and E. M. Farkhi, The directed subdifferential of DC functions, 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.
[5]	R. Baier and M. Hessel-von Molo, Newton's method and secant method for set-valued mappings, 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.
[6]	R. Baier and G. Perria, Set-valued Hermite interpolation, J. Approx. Theory, 163 (2011), 1349-1372.doi: 10.1016/j.jat.2010.11.004.
[7]	R. Baier and E. M. Farkhi, Differences of convex compact sets in the space of directed sets. I. The space of directed sets, Set-Valued Anal., 9 (2001), 217-245.doi: 10.1023/A:1012046027626.
[8]	R. Baier and E. M. Farkhi, Differences of convex compact sets in the space of directed sets. II. Visualization of directed sets, Set-Valued Anal., 9 (2001), 247-272.doi: 10.1023/A:1012009529492.
[9]	W.-J. Beyn, The numerical computation of connecting orbits in dynamical systems, 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.
[10]	F. Blanchini, Set invariance in control, Automatica, 35 (1999), 1747-1767.doi: 10.1016/S0005-1098(99)00113-2.
[11]	M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - set oriented numerical methods for dynamical systems, in Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems (ed. B. Fiedler), Springer, (2001), 145-174.
[12]	M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numer. Math., 75 (1997), 293-317.doi: 10.1007/s002110050240.
[13]	M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior, SIAM J. Numer. Anal., 36 (1999), 491-515.doi: 10.1137/S0036142996313002.
[14]	V. F. Demyanov and A. M. Rubinov, Constructive Nonsmooth Analysis, 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).
[15]	L. Dieci, J. Lorenz and R. D. Russell, Numerical calculation of invariant tori, SIAM J. Sci. Statist. Comput., 12 (1991), 607-647, http://link.aip.org/link/?SCE/12/607/1.doi: 10.1137/0912033.
[16]	N. S. Dimitrova and S. M. Markov, Interval methods of Newton type for nonlinear equations, Pliska Stud. Math. Bulgar., 5 (1983), 105-117.
[17]	T. Donchev and E. M. Farkhi, Fixed set iterations for relaxed Lipschitz multimaps, Nonlinear Anal., 53 (2003), 997-1015.doi: 10.1016/S0362-546X(03)00036-1.
[18]	H. Hadwiger, Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt, Math. Z., 53 (1950), 210-218.doi: 10.1007/BF01175656.
[19]	E. Hansen, A multidimensional interval Newton method, Reliab. Comput., 12 (2006), 253-272.doi: 10.1007/s11155-006-9000-y.
[20]	A. J. Homburg, H. M. Osinga and G. Vegter, On the computation of invariant manifolds of fixed points, ZAMM Z. Angew. Math. Phys., 46 (1995), 171-187.doi: 10.1007/BF00944751.
[21]	C. S. Hsu, Global analysis by cell mapping, Internat. J. Bifurc. Chaos Appl. Sci. Engrg., 2 (1992), 727-771.doi: 10.1142/S0218127492000422.
[22]	L. V. Kantorovich, On Newton's method for functional equations, Dokl. Akad. Nauk SSSR, 59 (1948), 1237-1240.
[23]	L. V. Kantorovich, The majorant principle and Newton's method, Dokl. Akad. Nauk SSSR, 76 (1951), 17-20.
[24]	L. V. Kantorovich and G. P. Akilov, Functional Analysis, 2nd edition, Pergamon Press, Oxford, 1982, Translated from the Russian by H. L. Silcock.
[25]	I. G. Kevrekidis, R. Aris, L. D. Schmidt and S. Pelikan, Numerical computation of invariant circles of maps, 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.
[26]	I. G. Kevrekidis, C. W. Gear and G. Hummer, Equation-free: The computer-aided analysis of complex multiscale systems, AIChE Journ., 50 (2004), 1346-1354.doi: 10.1002/aic.10106.
[27]	I. G. Kevrekidis, C. W. Gear, J. M. Hyman, P. G. Kevrekidis, O. Runborg and C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: enabling microscopic simulators to perform system-level analysis, Commun. Math. Sci., 1 (2003), 715-762, http://projecteuclid.org/getRecord?id=euclid.cms/1119655353.doi: 10.4310/CMS.2003.v1.n4.a5.
[28]	D. Klatte and B. Kummer, Nonsmooth equations in optimization. Regularity, calculus, methods and applications, vol. 60 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, 2002.
[29]	B. Krauskopf, H. M. Osinga, E. J. Doedel, M. E. Henderson, J. Guckenheimer, A. Vladimirsky, M. Dellnitz and O. Junge, A survey of methods for computing (un)stable manifolds of vector fields, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15 (2005), 763-791.doi: 10.1142/S0218127405012533.
[30]	R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing (Arch. Elektron. Rechnen), 4 (1969), 187-201.
[31]	R. Krawczyk, Einschlieş ung von Nullstellen mit Hilfe einer Intervallarithmetik, Computing (Arch. Elektron. Rechnen), 5 (1970), 356-370.
[32]	E. Kreuzer, Analysis of chaotic systems using the cell mapping approach, Arch. Appl. Mech., 55 (1985), 285-294.doi: 10.1007/BF00538223.
[33]	S. M. Markov, Some applications of extended interval arithmetic to interval iterations, Comput. Suppl., 2 (1980), 69-84.
[34]	K. Nickel, Das Auflösungsverhalten von nichtlinearen Fixmengen-Systemen, in Iterative solution of nonlinear systems of equations (Oberwolfach, 1982), vol. 953 of Lecture Notes in Math., Springer, Berlin, (1982), 106-124.
[35]	D. Pallaschke and R. Urbański, Pairs of Compact Convex Sets, vol. 548 of Mathematics and Its Applications, Kluwer Academic Publishers, Dordrecht, 2002.
[36]	G. Perria, Set-valued Interpolation, vol. 79 of Bayreuth. Math. Schr., Department of Mathematics, University of Bayreuth, Germany, 2007.
[37]	B. T. Polyak, Convexity of quadratic transformations and its use in control and optimization, J. Optim. Theory Appl., 99 (1998), 553-583.doi: 10.1023/A:1021798932766.
[38]	B. T. Polyak, Convexity of nonlinear image of a small ball with applications to optimization, Set-Valued Anal., 9 (2001), 159-168, Special issue on Wellposedness in Optimization and Related Topics (Gargnano, 1999).doi: 10.1023/A:1011287523150.
[39]	L. S. Pontryagin, Linear differential games. II, Sov. Math., Dokl., 8 (1967), 910-912.
[40]	R. T. Rockafellar, Convex Analysis, vol. 28 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 1970.
[41]	A. M. Rubinov and I. S. Akhundov, Difference of compact sets in the sense of Demyanov and its application to non-smooth analysis, Optimization, 23 (1992), 179-188.doi: 10.1080/02331939208843757.
[42]	P. Saint-Pierre, Newton and other continuation methods for multivalued inclusions, Set-Valued Anal., 3 (1995), 143-156.doi: 10.1007/BF01038596.
[43]	C. I. Siettos, C. C. Pantelides and I. G. Kevrekidis, Enabling dynamic process simulators to perform alternative tasks: A time-stepper-based toolkit for computer-aided analysis, Ind. Engrg. Chem. Res., 42 (2003), 6795-6801.doi: 10.1021/ie021062w.
[44]	C. Theodoropoulos, Y.-H. Qian and I. G. Kevrekidis, "Coarse'' stability and bifurcation analysis using time-steppers: A reaction-diffusion example, Proc. Natl. Acad. Sci., 97 (2000), 9840-9843, http://www.pnas.org/content/97/18/9840.abstract.doi: 10.1073/pnas.97.18.9840.
[45]	L. S. Tuckerman and D. Barkley, Bifurcation analysis for timesteppers, 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.
[46]	X. Wang, Convergence of Newton's method and inverse function theorem in Banach space, Math. Comp., 68 (1999), 169-186.doi: 10.1090/S0025-5718-99-00999-0.
[47]	T. Yamamoto, A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions, Numer. Math., 49 (1986), 203-220.doi: 10.1007/BF01389624.