Fixed-point computation

The graph of an example function with three fixed points

The unit interval is denoted by ${\displaystyle E:=[0,1]}$, and the unit d-dimensional cube is denoted by E^d. A continuous function f is defined on E^d (from E^d to itself). Often, it is assumed that f is not only continuous but also Lipschitz continuous, that is, for some constant L, ${\displaystyle |f(x)-f(y)|\leq L\cdot |x-y|}$ for all x,y in E^d.

A fixed point of f is a point x in E^d such that f(x) = x. By the Brouwer fixed-point theorem, any continuous function from 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:[2]

• The residual criterion: given an approximation parameter ${\displaystyle \varepsilon >0}$ , An ε-residual fixed-point of f is a point x in E^d such that ${\displaystyle |f(x)-x|\leq \varepsilon }$, where here |.| denotes the maximum norm. That is, all d coordinates of the difference ${\displaystyle f(x)-x}$ should be at most ε.[3]^: 4
• The absolute criterion: given an approximation parameter ${\displaystyle \delta >0}$, A δ-absolute fixed-point of f is a point x in E^d such that ${\displaystyle |x-x_{0}|\leq \delta }$, where ${\displaystyle x_{0}}$ is any fixed-point of f.
• The relative criterion: given an approximation parameter ${\displaystyle \delta >0}$, A δ-relative fixed-point of f is a point x in E^d such that ${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }$, where ${\displaystyle x_{0}}$ 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 ${\displaystyle |x-x_{0}|\leq \delta }$ implies ${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }$. Since ${\displaystyle x_{0}}$ is a fixed-point of f, this implies ${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }$, so ${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }$. Therefore, a δ-absolute fixed-point is also an ε-residual fixed-point with ${\displaystyle \varepsilon =(1+L)\cdot \delta }$.

The most basic step of a fixed-point computation algorithm is a value query: given any x in E^d, 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.

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.

Computing a fixed point using function iteration

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 ${\displaystyle O(L^{t})}$. Therefore, the number of evaluations required for a δ-relative fixed-point is approximately ${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$. Sikorski and Wozniakowski[4] showed that Banach's algorithm is optimal when the dimension is large. Specifically, when ${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$, 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.[5]

When L < 1 and d = 1, the optimal algorithm is the Fixed Point Envelope (FPE) algorithm of Sikorski and Wozniakowski.[4] It finds a δ-relative fixed point using ${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}$ queries, and a δ-absolute fixed point using ${\displaystyle O(\log(1/\delta ))}$ queries. This is much faster than the fixed-point iteration algorithm.[6]

When d>1 but not too large, and L ≤ 1, the optimal algorithm is the interior-ellipsoid algorithm (based on the ellipsoid method).[7] It finds an ε-residual fixed-point is using ${\displaystyle O(d\cdot \log(1/\varepsilon ))}$ evaluations. When L<1, it finds a δ-absolute fixed point using ${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}$ evaluations.

Shellman and Sikorski[8] 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 ${\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}$ queries. They later[9] 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 ${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}$ queries.

Shellman and Sikorski[2] presented an algorithm called PFix for computing an ε-residual fixed-point of a d-dimensional function with L ≤ 1, using ${\displaystyle O(\log ^{d}(1/\varepsilon ))}$ queries. When L < 1, PFix can be executed with ${\displaystyle \varepsilon =(1-L)\cdot \delta }$, and in that case, it computes a δ-absolute fixed-point, using ${\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))}$ queries. It is more efficient than the iteration algorithm when L is close to 1. The algorithm is recursive: it handles a d-dimensional function by recursive calls on (d-1)-dimensional functions.

For functions with Lipschitz constant L > 1, computing a fixed-point is much harder.

A discrete function is a function defined on a subset of ${\displaystyle \mathbb {Z} ^{d}}$ (the d-dimensional integer grid). There are several discrete fixed-point theorems, stating conditions under which a discrete function has a fixed point. For example, the Iimura-Murota-Tamura theorem states that (in particular) if f is a function from a rectangle subset of ${\displaystyle \mathbb {Z} ^{d}}$ to itself, and f is hypercubic direction-preserving, then f has a fixed point.

Let f be a direction-preserving function from the integer cube ${\displaystyle \{1,\dots ,n\}^{d}}$ to itself. Chen and Deng[18] prove that, for any d ≥ 2 and n > 48d, computing such a fixed point requires ${\displaystyle \Theta (n^{d-1})}$ function evaluations.

Chen and Deng[19] define a different discrete-fixed-point problem, which they call 2D-BROUWER. It considers a discrete function f on ${\displaystyle \{0,\dots ,n\}^{2}}$ such that, for every x on the grid, f(x) - x is either (0, 1) or (1, 0) or (-1, -1). The goal is to find a square in the grid, in which all three labels occur. The function f must map the square ${\displaystyle \{0,\dots ,n\}^{2}}$to itself, so it must map the lines x = 0 and y = 0 to either (0, 1) or (1, 0); the line x = n to either (-1, -1) or (0, 1); and the line y = n to either (-1, -1) or (1,0). The problem can be reduced to 2D-SPERNER (computing a fully-labeled triangle in a triangulation satisfying the conditions to Sperner's lemma), and therefore it is PPAD-complete. This implies that computing an approximate fixed-point is PPAD-complete even for very simple functions.

Given a function g from E^d to R, a root of g is a point x in E^d such that g(x)=0. An ε-root of g is a point x in E^d such that ${\displaystyle g(x)\leq \varepsilon }$.

Fixed-point computation is a special case of root-finding: given a function f on E^d, define ${\displaystyle g(x):=|f(x)-x|}$. Clearly, x is a fixed-point of f if and only if x is a root of g, and x is an ε-residual fixed-point of f if and only if x is an ε-root of g. Therefore, any root-finding algorithm (an algorithm that computes an approximate root of a function) can be used to find an approximate fixed-point.

The opposite is not true: finding an approximate root of a general function may be harder than finding an approximate fixed point. In particular, Sikorski[20] proved that finding an ε-root requires ${\displaystyle \Omega (1/\varepsilon ^{d})}$ function evaluations. This gives an exponential lower bound even for a one-dimensional function (in contrast, an ε-residual fixed-point of a one-dimensional function can be found using ${\displaystyle O(\log(1/\varepsilon ))}$ queries using the bisection method). Here is a proof sketch.[3]^: 35 Construct a function g that is slightly larger than ε everywhere in E^d except in some small cube around some point x₀, where x₀ is the unique root of g. If g is Lipschitz continuous with constant L, then the cube around x₀ can have a side-length of ${\displaystyle \varepsilon /L}$. Any algorithm that finds an ε-root of g must check a set of cubes that covers the entire E^d; the number of such cubes is at least ${\displaystyle (L/\varepsilon )^{d}}$.

However, there are classes of functions for which finding an approximate root is equivalent to finding an approximate fixed point. One example[18] is the class of functions g such that ${\displaystyle g(x)+x}$ maps E^d to itself (that is: ${\displaystyle g(x)+x}$ is in E^d for all x in E^d). This is because, for every such function, the function ${\displaystyle f(x):=g(x)+x}$ satisfies the conditions to Brouwer's fixed-point theorem. Clearly, x is a fixed-point of f if and only if x is a root of g, and x is an ε-residual fixed-point of f if and only if x is an ε-root of g. Chen and Deng[18] show that the discrete variants of these problems are computationally equivalent: both problems require ${\displaystyle \Theta (n^{d-1})}$ function evaluations.

Roughgarden and Weinstein[21] studied the communication complexity of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function f and the other knows a function g. Both functions are Lipschitz continuous and satisfy Brouwer's conditions. The goal is to compute an approximate fixed point of the composite function ${\displaystyle g\circ f}$. They show that the deterministic communication complexity is in ${\displaystyle \Omega (2^{d})}$.

• Yannakakis, Mihalis (May 2009). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. doi:10.1016/j.cosrev.2009.03.004.