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
Additional Information
- C. Boonyasiriwat
- Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
- Email: chaiwoot@yahoo.com
- K. Sikorski
- Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
- Email: sikorski@cs.utah.edu
- C. Tsay
- Affiliation: Computer Science and Information Management, Providence University 200 Chung-chi Rd., Shalu Taichung 43301, Taiwan
- Email: cwtsay@pu.edu.tw
- Received by editor(s): October 3, 2008
- Received by editor(s) in revised form: April 23, 2010
- Published electronically: November 30, 2010
- © Copyright 2010 American Mathematical Society
- Journal: Math. Comp. 80 (2011), 1703-1723
- MSC (2010): Primary 47H10, 65H10; Secondary 65Y20, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-2010-02443-3
- MathSciNet review: 2785475
Dedicated: We dedicate this paper to the memory of Leonid Khachiyan, collaborator and friend, who introduced the circumscribed ellipsoid algorithm as the first way of solving linear programming problems in polynomial time.