Fixed-point computation refers to the process of computing an exact or approximate fixed point of a given function. In its most common form, the given function f {\displaystyle f} satisfies the condition to the Brouwer fixed-point theorem: that is, f {\displaystyle f} is continuous and maps the unit d-cube to itself. The Brouwer fixed-point theorem guarantees that f {\displaystyle 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 various tasks, such as
Nash equilibrium computation, Market equilibrium computation, Dynamic system analysis.
Definitions
The unit interval is denoted by E := [ 0 , 1 ] {\displaystyle E:=[0,1]} , and the unit d-dimensional cube is denoted by E d {\displaystyle E^{d}} . A continuous function f {\displaystyle f} is defined on E d {\displaystyle E^{d}} (from E d {\displaystyle E^{d}} to itself). Often, it is assumed that f {\displaystyle f} is not only continuous but also Lipschitz continuous, that is, for some constant L {\displaystyle L} , | f ( x ) − f ( y ) | ≤ L ⋅ | x − y | {\displaystyle |f(x)-f(y)|\leq L\cdot |x-y|} for all x , y {\displaystyle x,y} in E d {\displaystyle E^{d}} . A fixed point of f {\displaystyle f} is a point x {\displaystyle x} in E d {\displaystyle E^{d}} such that f ( x ) = x {\displaystyle f(x)=x} . By the Brouwer fixed-point theorem, any continuous function from E d {\displaystyle E^{d}} 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:
… excerpt ends here. Continue reading the full article.
