Circumscribed ellipsoid algorithm for fixed-point problems

Boonyasiriwat, C.; Sikorski, K.; Tsay, C.

doi:10.1090/S0025-5718-2010-02443-3

Circumscribed ellipsoid algorithm for fixed-point problems
HTML articles powered by AMS MathViewer

by C. Boonyasiriwat, K. Sikorski and C. Tsay PDF

Math. Comp. 80 (2011), 1703-1723 Request permission

Abstract:

We present a new implementation of the almost optimal Circumscribed Ellipsoid (CE) Algorithm for approximating fixed points of nonexpanding functions, as well as of functions that may be globally expanding, however, are nonexpanding/contracting in the direction of fixed points. Our algorithm is based only on function values, i.e., it does not require computing derivatives of any order. We utilize the absolute and residual termination criteria with respect to the second norm. The numerical results confirm that the CE algorithm is much more efficient than the simple iteration algorithm whenever the Lipschitz constant is close to 1. We also compare it with the Newton-Raphson method. In some tests the Newton-Raphson method is more efficient than the CE method, especially when the problem size is large. However, the CE algorithm is an excellent method for low dimensional functions with discontinuities and/or low regularity. Our implementation can be downloaded from http://www.cs.utah.edu/$\sim$sikorski/cea.

References

A. Ageev, V. Vassin, E.N. Bessonova, and V.M. Markusevich, Radiosounding ionosphere on two frequencies. Algorithmic analysis of fredholm-stiltjes integral equation, in: Theoretical problems in geophysics (in Russian), (1997), 100–118.
E. L. Allgower, Application of a fixed point search algorithm to nonlinear boundary value problems having several solutions, Fixed points: algorithms and applications (Proc. First Internat. Conf., Clemson Univ., Clemson, S.C., 1974) Academic Press, New York, 1977, pp. 87–111. MR 0448858
Eugene L. Allgower and Kurt Georg, Numerical continuation methods, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR 1059455, DOI 10.1007/978-3-642-61257-2
Jan Andres and Lech Górniewicz, Topological fixed point principles for boundary value problems, Topological Fixed Point Theory and Its Applications, vol. 1, Kluwer Academic Publishers, Dordrecht, 2003. MR 1998968, DOI 10.1007/978-94-017-0407-6
S. Banach, Sur les opérations dans les ensembles abstraits et leur application aux équations integrales, Fund. Math. 3 (1922), 133–181.
Robert G. Bland, Donald Goldfarb, and Michael J. Todd, The ellipsoid method: a survey, Oper. Res. 29 (1981), no. 6, 1039–1091. MR 641676, DOI 10.1287/opre.29.6.1039
C. Boonyasiriwat, Circumscribed ellipsoid algorithm for fixed point problems, Master’s thesis, University of Utah, Salt Lake City, UT, 2004.
Ch. Boonyasiriwat, K. Sikorski, and Ch. Xiong, A note on two fixed point problems, J. Complexity 23 (2007), no. 4-6, 952–961. MR 2372002, DOI 10.1016/j.jco.2007.04.004
Kim C. Border, Fixed point theorems with applications to economics and game theory, Cambridge University Press, Cambridge, 1985. MR 790845, DOI 10.1017/CBO9780511625756
Ali Bouaricha and Robert B. Schnabel, Algorithm 768: TENSOLVE: a software package for solving systems of nonlinear equations and nonlinear least-squares problems using tensor methods, ACM Trans. Math. Software 23 (1997), no. 2, 174–195. MR 1671795, DOI 10.1145/264029.264032
L. E. Brouwer, Über abbildungen von mannigfaltigkeiten, Mathematische Annalen (1912), no. 71, 97–115.
James R. Bunch, Christopher P. Nielsen, and Danny C. Sorensen, Rank-one modification of the symmetric eigenproblem, Numer. Math. 31 (1978/79), no. 1, 31–48. MR 508586, DOI 10.1007/BF01396012
R. M. Corless, G. W. Frank, and J. Graham Monroe, Chaos and continued fractions, Phys. D 46 (1990), no. 2, 241–253. MR 1083721, DOI 10.1016/0167-2789(90)90038-Q
Xi Chen and Xiaotie Deng, On algorithms for discrete and approximate Brouwer fixed points [extended abstract], STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 323–330. MR 2181632, DOI 10.1145/1060590.1060638
J. J. Dongarra and D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S139–S154. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879400, DOI 10.1137/0908018
B. Curtis Eaves, Homotopies for computation of fixed points, Math. Programming 3 (1972), 1–22. MR 303953, DOI 10.1007/BF01584975
B. Curtis Eaves and Romesh Saigal, Homotopies for computation of fixed points on unbounded regions, Math. Programming 3 (1972), 225–237. MR 314028, DOI 10.1007/BF01584991
C. B. García, C. E. Lemke, and H. Luethi, Simplicial approximation of an equilibrium point for non-cooperative $N$-person games, Mathematical programming (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1972) Math. Res. Center Publ., No. 30, Academic Press, New York, 1973, pp. 227–260. MR 0439238
Gene H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 15 (1973), 318–334. MR 329227, DOI 10.1137/1015032
Ming Gu and Stanley C. Eisenstat, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl. 15 (1994), no. 4, 1266–1276. MR 1293916, DOI 10.1137/S089547989223924X
Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis, Exponential lower bounds for finding Brouwer fixed points, J. Complexity 5 (1989), no. 4, 379–416. MR 1028904, DOI 10.1016/0885-064X(89)90017-4
James Lucien Howland and Rémi Vaillancourt, Attractive cycles in the iteration of meromorphic functions, Numer. Math. 46 (1985), no. 3, 323–337. MR 791694, DOI 10.1007/BF01389489
Z. Huang, L. Khachiyan, and K. Sikorski, Approximating fixed points of weakly contracting mappings, J. Complexity 15 (1999), no. 2, 200–213. MR 1693888, DOI 10.1006/jcom.1999.0504
Mark Jeppson, A search for the fixed points of a continuous mapping, Mathematical topics in economic theory and computation (Sympos. Math. Econom., SIAM Fall Meeting, Univ. Wisconsin, Madison, Wis., 1971) Soc. Indust. Appl. Math., Philadelphia, Pa., 1972, pp. 122–129. MR 0408236
L. G. Khachiyan, A polynomial algorithm in linear programming, Yingyong Shuxue yu Jisuan Shuxue 2 (1980), 1–3 (Chinese). Translated from the Russian by Ke Gang Hao. MR 639296
L. G. Hačijan, Polynomial algorithms in linear programming, Zh. Vychisl. Mat. i Mat. Fiz. 20 (1980), no. 1, 51–68, 260 (Russian). MR 564776
O. H. Merril, Application and extensions of an algorithm that computes fixed points of a certain upper semi-continuous point of set mapping, Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1972.
Orin H. Merrill, A summary of techniques for computing fixed points of continuous mappings, Mathematical topics in economic theory and computation (sympos. Math. Econom., SIAM Fall Meeting, Univ. Wisconsin, Madison, Wis., 1971) Soc. Indust. Appl. Math., Philadelphia, Pa., 1972, pp. 130–149. MR 0408235
J. J. More, B. S. Garbow, and K. E. Hillstrom, User guide for minpack-1, Argonne National Laboratory Report ANL-80-74, Argonne, 1980.
A. Neumaier, A better estimate for fixed points of contractions, Z. Angew. Math. Mech. 62 (1982), no. 11, 627. MR 694062, DOI 10.1002/zamm.19820621108
G. Perestonina, I.L. Prutkin, L.Ya. Timerkhanova, and V. Vassin, Solving three-dimensional inverse problems of gravimetry and magnetometry for three layer medium (in Russian), Math. Modeling 15 (2003), no. 2, 69–76.
J. Rutter, A serial implementation of cuppen’s divide and conquer algorithm for the symmetric eigenvalue problem, Technical Report CS-94-225, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, March 1994. LAPACK Working Note 69, 1994.
Herbert Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math. 15 (1967), 1328–1343. MR 242483, DOI 10.1137/0115116
Herbert E. Scarf, The core of an $N$ person game, Econometrica 35 (1967), 50–69. MR 234735, DOI 10.2307/1909383
Herbert Scarf, The computation of economic equilibria, Cowles Foundation Monograph, No. 24, Yale University Press, New Haven, Conn.-London, 1973. With the collaboration of Terje Hansen. MR 0391909
Spencer Shellman and K. Sikorski, A two-dimensional bisection envelope algorithm for fixed points, J. Complexity 18 (2002), no. 2, 641–659. Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). MR 1919453, DOI 10.1006/jcom.2001.0625
Spencer Shellman and K. Sikorski, Algorithm 825: a deep-cut bisection envelope algorithm for fixed points, ACM Trans. Math. Software 29 (2003), no. 3, 309–325. MR 2002734, DOI 10.1145/838250.838255
Spencer Shellman and K. Sikorski, A recursive algorithm for the infinity-norm fixed point problem, J. Complexity 19 (2003), no. 6, 799–834. MR 2040430, DOI 10.1016/j.jco.2003.06.001
Spencer Shellman and K. Sikorski, Algorithm 848: a recursive fixed-point algorithm for the infinity-norm case, ACM Trans. Math. Software 31 (2005), no. 4, 580–586. MR 2272347, DOI 10.1145/1114268.1114276
K. Sikorski, Fast algorithms for the computation of fixed points, Robustness in identification and control (Torino, 1988) Appl. Inform. Tech., Plenum, New York, 1989, pp. 49–58. MR 1041089, DOI 10.1007/978-1-4615-9552-6_{4}
Krzysztof A. Sikorski, Optimal solution of nonlinear equations, Oxford University Press, Oxford, 2001. MR 1827804
K. Sikorski, C. W. Tsay, and H. Woźniakowski, An ellipsoid algorithm for the computation of fixed points, J. Complexity 9 (1993), no. 1, 181–200. Festschrift for Joseph F. Traub, Part I. MR 1213495, DOI 10.1006/jcom.1993.1013
K. Sikorski and H. Woźniakowski, Complexity of fixed points. I, J. Complexity 3 (1987), no. 4, 388–405. MR 919096, DOI 10.1016/0885-064X(87)90008-2
D. C. Sorensen and Ping Tak Peter Tang, On the orthogonality of eigenvectors computed by divide-and-conquer techniques, SIAM J. Numer. Anal. 28 (1991), no. 6, 1752–1775. MR 1135764, DOI 10.1137/0728087
Roman Srzednicki, A generalization of the Lefschetz fixed point theorem and detection of chaos, Proc. Amer. Math. Soc. 128 (2000), no. 4, 1231–1239. MR 1691005, DOI 10.1090/S0002-9939-99-05467-2
Françoise Tisseur and Jack Dongarra, A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures, SIAM J. Sci. Comput. 20 (1999), no. 6, 2223–2236. MR 1703274, DOI 10.1137/S1064827598336951
C. W. Tsay, Fixed point computation and parallel algorithms for solving wave equations, Ph.D. thesis, University of Utah, Salt Lake City, UT, 1994.
V. Vassin, Ill-posed problems with a priori information: Methods and applications, Institute of Mathematics and Mechanics, Russian Academy of Sciences, Ural Subdivision, 2005.
V. V. Vasin and A. L. Ageev, Ill-posed problems with a priori information, Inverse and Ill-posed Problems Series, VSP, Utrecht, 1995. MR 1374573, DOI 10.1515/9783110900118
V. Vassin and E. Eremin, Feyer type operators and iterative processes (in Russian), Russian Academy of Sciences, Ural Subdivision, Ekaterinburg, 2005.
V. Vassin and T.I. Sereznikova, Two stage method for approximation of nonsmooth solutions and reconstruction of noisy images (in Russian), Automatica and Telemechanica (2004), no. 2.
Layne T. Watson, A globally convergent algorithm for computing fixed points of $C^{2}$ maps, Appl. Math. Comput. 5 (1979), no. 4, 297–311. MR 544868, DOI 10.1016/0096-3003(79)90020-1
Zong Ben Xu and Xing Zhong Shi, A comparison of point and ball iterations in the contractive mapping case, Computing 49 (1992), no. 1, 75–85 (English, with English and German summaries). MR 1182443, DOI 10.1007/BF02238651
Nobito Yamamoto, A numerical verification method for solutions of boundary value problems with local uniqueness by Banach’s fixed-point theorem, SIAM J. Numer. Anal. 35 (1998), no. 5, 2004–2013. MR 1639986, DOI 10.1137/S0036142996304498
Zaifu Yang, Computing equilibria and fixed points, Theory and Decision Library. Series C: Game Theory, Mathematical Programming and Operations Research, vol. 21, Kluwer Academic Publishers, Boston, MA, 1999. The solution of nonlinear inequalities. MR 1788059, DOI 10.1007/978-1-4757-4839-0