## BEDFix

 swMATH ID: 4469 Software Authors: Shellman, Spencer; Sikorski, K. Description: Algorithm 825: A deep-cut bisection envelope algorithm for fixed points 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. Homepage: http://dl.acm.org/citation.cfm?id=838255 Related Software: Algorithm 848; minpack; TENSOLVE Cited in: 9 Publications

### Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
Algorithm 825: A deep-cut bisection envelope algorithm for fixed points. Zbl 1070.65543
Shellman, Spencer; Sikorski, K.
2003
all top 5

### Cited by 14 Authors

 3 Shellman, Spencer D. 3 Sikorski, Krzysztof A. 2 Boonyasiriwat, Ch. 1 Chen, Xi 1 Deng, Xiao-Tie 1 Fearnley, John 1 Gao, David Yang 1 Gordon, Spencer L. 1 Mehta, Ruta 1 Mossay, Pascal 1 Pavlidis, Nicos G. 1 Ruan, Ning 1 Savani, Rahul 1 Vrahatis, Michael N.
all top 5

### Cited in 6 Serials

 2 ACM Transactions on Mathematical Software 2 Journal of Complexity 1 Mathematics of Computation 1 Applied Mathematics and Computation 1 Journal of Computer and System Sciences 1 Fixed Point Theory and Applications
all top 5

### Cited in 7 Fields

 6 Numerical analysis (65-XX) 3 Operator theory (47-XX) 2 Computer science (68-XX) 2 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Algebraic topology (55-XX) 1 Operations research, mathematical programming (90-XX)