Fixed-point computation refers to the process of computing an exact or approximate fixed point of a given function. In its most common form, we are given a function f that satisfies the condition to the Brouwer fixed-point theorem, that is: f is continuous and maps the unit d-cube to itself. The Brouwer fixed-point theorem guarantees that f has a fixed point, but the proof is not constructive. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in economics for computing a market equilibrium, in game theory for computing a Nash equilibrium, and in dynamic system analysis.
Definitions
The unit interval is denoted by , and the unit d-dimensional cube is denoted by Ed. A continuous function f is defined on Ed (from Ed to itself). Often, it is assumed that f is not only continuous but also Lipschitz continuous, that is, for some constant L, for all x,y in Ed.
A fixed point of f is a point x in Ed such that f(x) = x. By the Brouwer fixed-point theorem, any continuous function from Ed to itself has a fixed point. But for general functions, it is impossible to compute a fixed point precisely, since it can be an arbitrary real number. Fixed-point computation algorithms look for approximate fixed points. There are several criteria for an approximate fixed point. Several common criteria are:
The residual criterion: given an approximation parameter , An -residual fixed-point of f is a point x in Ed such that , where here |.| denotes the maximum norm. That is, all d coordinates of the difference should be at most . The absolute criterion: given an approximation parameter , A δ-absolute fixed-point of f is a point x in Ed such that , where is any fixed-point of f. The relative criterion: given an approximation parameter , A δ-relative fixed-point of f is a point x in Ed such that , where is any fixed-point of f.
For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If f is Lipschitz-continuous with constant L, then implies . Since is a fixed-point of f, this implies , so . Therefore, a δ-absolute fixed-point is also an -residual fixed-point with .
The most basic step of a fixed-point computation algorithm is a value query: given any x in Ed, the
The function f is accessible via evaluation queries: for any x, the algorithm can evaluate f(x). The run-time complexity of an algorithm is usually given by the number of required evaluations.
Contractive functions
A Lipschitz-continuous function with constant L is called contractive if L < 1; it is called weakly-contractive if L ≤ 1.Every contractive function satisfying Brouwer's condisions has a unique fixed point. Moreover, fixed-point computation for contractive functions is easier than for general functions.
The first algorithm for fixed-point computation was the fixed-point iteration algorithm of Banach. Banach's fixed-point theorem implies that, when fixed-point iteration is applied to a contraction mapping, the error after t iterations is in . Therefore, the number of evaluations required for a δ-relative fixed-point is approximately . Sikorski and Wozniakowski showed that Banach's algorithm is optimal when the dimension is large. Specifically, when , the number of required evaluations of any algorithm for δ-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when L approaches 1, the number of evaluations approaches infinity. In fact, no finite algorithm can compute a δ-absolute fixed point for all functions with L=1.
When L < 1 and d = 1, the optimal algorithm is the Fixed Point Envelope (FPE) algorithm of Sikorski and Wozniakowski. It finds a δ-relative fixed point using queries, and a δ-absolute fixed point using queries. This is much faster than the fixed-point iteration algorithm.
When d>1 but not too large, and L ≤ 1, the optimal algorithm is the interior-ellipsoid algorithm (based on the ellipsoid method). It finds an -residual fixed-point is using evaluations. When L<1, it finds a δ-absolute fixed point using evaluations.
Shellman and Sikorski presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an -residual fixed-point of a two-dimensional function with L ≤ 1, using only queries. They later presented an improvement called BEDFix (Bisection Envelope Deep-cut Fixed-point), with the same worst-case guarantee but better empirical performance. When L<1, BEDFix can also compute a δ-absolute fixed-point using queries.