Algorithm 825: A deep-cut bisection envelope algorithm for fixed points

ABSTRACT

We present the BEDFix (Bisection Envelope Deep-cut Fixed point) algorithm for the problem of approximating a fixed point of a function of two variables. The function must be Lipschitz continuous with constant 1 with respect to the infinity norm; such functions are commonly found in economics and game theory. The computed approximation satisfies a residual criterion given a specified error tolerance. The BEDFix algorithm improves the BEFix algorithm presented in Shellman and Sikorski [2002] by utilizing "deep cuts," that is, eliminating additional segments of the feasible domain which cannot contain a fixed point. The upper bound on the number of required function evaluations is the same for BEDFix and BEFix, but our numerical tests indicate that BEDFix significantly improves the average-case performance. In addition, we show how BEDFix may be used to solve the absolute criterion fixed point problem with significantly better performance than the simple iteration method, when the Lipschitz constant is less than but close to 1. BEDFix is highly efficient when used to compute residual solutions for bivariate functions, having a bound on function evaluations that is twice the logarithm of the reciprocal of the tolerance. In the tests described in this article, the number of evaluations performed by the method averaged 31 percent of this worst-case bound. BEDFix works for nonsmooth continuous functions, unlike methods that require gradient information; also, it handles functions with minimum Lipschitz constants equal to 1, whereas the complexity of simple iteration approaches infinity as the minimum Lipschitz constant approaches 1. When BEDFix is used to compute absolute criterion solutions, the worst-case complexity depends on the logarithm of the reciprocal of 1-q, where q is the Lipschitz constant, as well as on the logarithm of the reciprocal of the tolerance.

REFERENCES

• 1: Eugene L. Allgower , Kurt Georg, Numerical continuation methods: an introduction, Springer-Verlag New York, Inc., New York, NY, 1990
• 2: Birkhoff, G. 1917. Dynamic systems with two degrees of freedom. Trans. AMS 18, 199.
• 3: Bountis, T. and Helleman, R. 1981. On the stability of periodic orbits of two-dimensional mappings. J. Math. Phys. 22, 1867.
• 4: Eaves, B. 1972. Homotopies for computation of fixed points. Math. Prog. 3, 1, 1--22.
• 5: Eaves, B. and Saigal, R. 1972. Homotopies for computation of fixed points on unbounded regions. Math. Prog. 3, 2, pp. 225--237.
• 6: Greene, J. 1979. A method for determining a stochastic transition. J. Math. Phys. 20, 1183--1201.
• 7: Helleman, R. 1977. Statistical Mechanics and Statistical Methods in Theory and Application: On the Iterative Solution of a Stochastic Mapping. U. Landman, Ed. Plenum, New York, 343.
• 8: Hénon, M. 1969. Numerical study of quadratic area-preserving mappings. Quart. Appl. Math. 27, 291--312.
• 9: M. D. Hirsch , C. H. Papadimitriou, Exponential lower bounds for finding Brouwer fixed points, Journal of Complexity, v.5 n.4, p.379-416, Dec. 1989 [doi>10.1016/0885-064X(89)90017-4]
• 10: Howland, J. and Vaillancourt, R. 1985. Attractive cycles in the iteration of meromorphic functions. Num. Math. 46, 323--337.
• 11: Z. Huang , L. Khachiyan , K. Sikorski, Approximating fixed points of weakly contracting mappings, Journal of Complexity, v.15 n.2, p.200-213, June 1999 [doi>10.1006/jcom.1999.0504]
• 12: A. S. Nemirovsky, On optimality of Krylov's information when solving linear operator equations, Journal of Complexity, v.7 n.2, p.121-130, June 1991 [doi>10.1016/0885-064X(91)90001-E]
• 13: Scarf, M. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 1328--1343.
• 14: Spencer Shellman , K. Sikorski, A two-dimensional bisection envelope algorithm for fixed points, Journal of Complexity, v.18 n.2, p.641-659, June 2002 [doi>10.1006/jcom.2001.0606]
• 15: Krzysztof A. Sikorski, Optimal solution of nonlinear equations, Oxford University Press, Inc., New York, NY, 2001
• 16: Ferdinand Verhulst, Nonlinear differential equations and dynamical systems, Springer-Verlag New York, Inc., New York, NY, 1990
• 17: Michael N. Vrahatis, An efficient method for locating and computing periodic orbits of nonlinear mappings, Journal of Computational Physics, v.119 n.1, p.105-119, June 1995 [doi>10.1006/jcph.1995.1119]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms, Performance

Keywords:
Fixed points, economics, game theory, nonlinear partial differential equations