BEDFix
swMATH ID:  4469 
Software Authors:  Shellman, Spencer; Sikorski, K. 
Description:  Algorithm 825: A deepcut bisection envelope algorithm for fixed points We present the BEDFix (Bisection Envelope Deepcut 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 averagecase 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 worstcase 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 worstcase complexity depends on the logarithm of the reciprocal of 1q, 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 deepcut bisection envelope algorithm for fixed points. Zbl 1070.65543 Shellman, Spencer; Sikorski, K. 
2003

all
top 5
Cited by 14 Authors
all
top 5
Cited in 6 Serials
all
top 5