Fixed-point computation

Fixed-point computation refers to the process of computing an exact or approximate fixed point of a given function.^[1] In its most common form, the given function ${\displaystyle f}${\displaystyle f} satisfies the condition to the Brouwer fixed-point theorem: that is, ${\displaystyle f}${\displaystyle f} is continuous and maps the unit d-cube to itself. The Brouwer fixed-point theorem guarantees that ${\displaystyle 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.

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

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

• The residual criterion: given an approximation parameter ${\displaystyle \varepsilon >0}${\displaystyle \varepsilon >0} , An ε-residual fixed-point of ${\displaystyle f}${\displaystyle f} is a point ${\displaystyle x}${\displaystyle x} in ${\displaystyle E^{d}}${\displaystyle E^{d}}' such that ${\displaystyle |f(x)-x|\leq \varepsilon }${\displaystyle |f(x)-x|\leq \varepsilon }, where here ${\displaystyle |\cdot |}${\displaystyle |\cdot |} denotes the maximum norm. That is, all ${\displaystyle d}${\displaystyle d} coordinates of the difference ${\displaystyle f(x)-x}${\displaystyle f(x)-x} should be at most ε.^{[3] : 4}
• The absolute criterion: given an approximation parameter ${\displaystyle \delta >0}${\displaystyle \delta >0}, A δ-absolute fixed-point of ${\displaystyle f}${\displaystyle f} is a point ${\displaystyle x}${\displaystyle x} in ${\displaystyle E^{d}}${\displaystyle E^{d}} such that ${\displaystyle |x-x_{0}|\leq \delta }${\displaystyle |x-x_{0}|\leq \delta }, where ${\displaystyle x_{0}}${\displaystyle x_{0}} is any fixed-point of ${\displaystyle f}${\displaystyle f}.
• The relative criterion: given an approximation parameter ${\displaystyle \delta >0}${\displaystyle \delta >0}, A δ-relative fixed-point of ${\displaystyle f}${\displaystyle f} is a point x in ${\displaystyle E^{d}}${\displaystyle E^{d}} such that ${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }, where ${\displaystyle x_{0}}${\displaystyle x_{0}} is any fixed-point of ${\displaystyle f}${\displaystyle f}.

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If ${\displaystyle f}${\displaystyle f} is Lipschitz-continuous with constant ${\displaystyle L}${\displaystyle L}, then ${\displaystyle |x-x_{0}|\leq \delta }${\displaystyle |x-x_{0}|\leq \delta } implies ${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }. Since ${\displaystyle x_{0}}${\displaystyle x_{0}} is a fixed-point of ${\displaystyle f}${\displaystyle f}, this implies ${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }, so ${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }${\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 }${\displaystyle \varepsilon =(1+L)\cdot \delta }.

The most basic step of a fixed-point computation algorithm is a value query: given any ${\displaystyle x}${\displaystyle x} in ${\displaystyle E^{d}}${\displaystyle E^{d}}, the algorithm is provided with an oracle ${\displaystyle {\tilde {f}}}${\displaystyle {\tilde {f}}} to ${\displaystyle f}${\displaystyle f} that returns the value ${\displaystyle f(x)}${\displaystyle f(x)}. The accuracy of the approximate fixed-point depends upon the error in the oracle ${\displaystyle {\tilde {f}}(x)}${\displaystyle {\tilde {f}}(x)}.

The function ${\displaystyle f}${\displaystyle f} is accessible via evaluation queries: for any ${\displaystyle x}${\displaystyle x}, the algorithm can evaluate ${\displaystyle f(x)}${\displaystyle f(x)}. The run-time complexity of an algorithm is usually given by the number of required evaluations.

A Lipschitz-continuous function with constant ${\displaystyle L}${\displaystyle L} is called contractive if ${\displaystyle L<1}${\displaystyle L<1}; it is called weakly-contractive if ${\displaystyle L\leq 1}${\displaystyle L\leq 1}. Every contractive function satisfying Brouwer's conditions 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 ${\displaystyle t}${\displaystyle t} iterations is in ${\displaystyle O(L^{t})}${\displaystyle O(L^{t})}. Therefore, the number of evaluations required for a ${\displaystyle \delta }${\displaystyle \delta }-relative fixed-point is approximately ${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}${\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)}${\displaystyle d\geq \log(1/\delta )/\log(1/L)}, the number of required evaluations of any algorithm for ${\displaystyle \delta }${\displaystyle \delta }-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ${\displaystyle L}${\displaystyle L} approaches 1, the number of evaluations approaches infinity. No finite algorithm can compute a ${\displaystyle \delta }${\displaystyle \delta }-absolute fixed point for all functions with ${\displaystyle L=1}${\displaystyle L=1}.^[5]

When ${\displaystyle L}${\displaystyle 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)))}${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))} queries, and a δ-absolute fixed point using ${\displaystyle O(\log(1/\delta ))}${\displaystyle O(\log(1/\delta ))} queries. This is faster than the fixed-point iteration algorithm.^[6]

When ${\displaystyle d>1}${\displaystyle d>1} but not too large, and ${\displaystyle L\leq 1}${\displaystyle L\leq 1}, the optimal algorithm is the interior-ellipsoid algorithm (based on the ellipsoid method).^[7] It finds an ε-residual fixed-point using ${\displaystyle O(d\cdot \log(1/\varepsilon ))}${\displaystyle O(d\cdot \log(1/\varepsilon ))} evaluations. When ${\displaystyle L<1}${\displaystyle L<1}, it finds a ${\displaystyle \delta }${\displaystyle \delta }-absolute fixed point using ${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}${\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 '${\displaystyle L\leq 1}${\displaystyle L\leq 1}, using only ${\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}${\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 ${\displaystyle L<1}${\displaystyle L<1}, BEDFix can also compute a ${\displaystyle \delta }${\displaystyle \delta }-absolute fixed-point using ${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}${\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 ))}${\displaystyle O(\log ^{d}(1/\varepsilon ))} queries. When ${\displaystyle L}${\displaystyle L} < 1, PFix can be executed with ${\displaystyle \varepsilon =(1-L)\cdot \delta }${\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 ]))}${\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))} queries. It is more efficient than the iteration algorithm when ${\displaystyle L}${\displaystyle L} is close to 1. The algorithm is recursive: it handles a d-dimensional function by recursive calls on (d-1)-dimensional functions.

When the function ${\displaystyle f}${\displaystyle f} is differentiable, and the algorithm can evaluate its derivative (not only ${\displaystyle f}${\displaystyle f} itself), the Newton method can be used and it is much faster.^{[10] [11]}

For functions with Lipschitz constant ${\displaystyle L}${\displaystyle L} > 1, computing a fixed-point is much harder.

For a 1-dimensional function (d = 1), a ${\displaystyle \delta }${\displaystyle \delta }-absolute fixed-point can be found using ${\displaystyle O(\log(1/\delta ))}${\displaystyle O(\log(1/\delta ))} queries using the bisection method: start with the interval ${\displaystyle E:=[0,1]}${\displaystyle E:=[0,1]}; at each iteration, let ${\displaystyle x}${\displaystyle x} be the center of the current interval, and compute ${\displaystyle f(x)}${\displaystyle f(x)}; if ${\displaystyle f(x)>x}${\displaystyle f(x)>x} then recurse on the sub-interval to the right of ${\displaystyle x}${\displaystyle x}; otherwise, recurse on the interval to the left of ${\displaystyle x}${\displaystyle x}. Note that the current interval always contains a fixed point, so after ${\displaystyle O(\log(1/\delta ))}${\displaystyle O(\log(1/\delta ))} queries, any point in the remaining interval is a ${\displaystyle \delta }${\displaystyle \delta }-absolute fixed-point of ${\displaystyle f}${\displaystyle f} Setting ${\displaystyle \delta :=\varepsilon /(L+1)}${\displaystyle \delta :=\varepsilon /(L+1)}, where ${\displaystyle L}${\displaystyle L} is the Lipschitz constant, gives an ε-residual fixed-point, using ${\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))}${\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))} queries.^[3]

For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski^[2] proved that for any integers d ≥ 2 and ${\displaystyle L}${\displaystyle L} > 1, finding a δ-absolute fixed-point of d-dimensional ${\displaystyle L}${\displaystyle L}-Lipschitz functions might require infinitely many evaluations. The proof idea is as follows. For any integer T > 1 and any sequence of T of evaluation queries (possibly adaptive), one can construct two functions that are Lipschitz-continuous with constant ${\displaystyle L}${\displaystyle L}, and yield the same answer to all these queries, but one of them has a unique fixed-point at (x, 0) and the other has a unique fixed-point at (x, 1). Any algorithm using T evaluations cannot differentiate between these functions, so cannot find a δ-absolute fixed-point. This is true for any finite integer T.

Several algorithms based on function evaluations have been developed for finding an ε-residual fixed-point

• The first algorithm to approximate a fixed point of a general function was developed by Herbert Scarf in 1967.^{[12] [13]} Scarf's algorithm finds an ε-residual fixed-point by finding a fully labeled "primitive set", in a construction similar to Sperner's lemma.
• A later algorithm by Harold Kuhn ^[14] used simplices and simplicial partitions instead of primitive sets.
• Developing the simplicial approach further, Orin Harrison Merrill^[15] presented the restart algorithm.
• B. Curtis Eaves^[16] presented the Homotopy method. The algorithm works by starting with an affine function that approximates ${\displaystyle f}${\displaystyle f}, and deforming it towards ${\displaystyle f}${\displaystyle f} while following the fixed point.
• A book by Michael Todd^[1] surveys various algorithms developed until 1976.
• David Gale ^[17] showed that computing a fixed point of an n-dimensional function (on the unit d-dimensional cube) is equivalent to deciding who is the winner in a d-dimensional game of Hex (a game with d players, each of whom needs to connect two opposite faces of a d-cube). Given the desired accuracy ε
  • Construct a Hex board of size kd, where ${\displaystyle k>1/\varepsilon }${\displaystyle k>1/\varepsilon }. Each vertex z corresponds to a point z/k in the unit n-cube.
  • Compute the difference ${\displaystyle f}${\displaystyle f}(z/k) - z/k; note that the difference is an n-vector.
  • Label the vertex z by a label in 1, ..., d, denoting the largest coordinate in the difference vector.
  • The resulting labeling corresponds to a possible play of the d-dimensional Hex game among d players. This game must have a winner, and Gale presents an algorithm for constructing the winning path.
  • In the winning path, there must be a point in which f_i(z/k) - z/k is positive, and an adjacent point in which f_i(z/k) - z/k is negative. This means that there is a fixed point of ${\displaystyle f}${\displaystyle f} between these two points.

In the worst case, the number of function evaluations required by all these algorithms is exponential in the binary representation of the accuracy, that is, in ${\displaystyle \Omega (1/\varepsilon )}${\displaystyle \Omega (1/\varepsilon )}.

Hirsch, Papadimitriou and Vavasis proved that^[3] any algorithm based on function evaluations, that finds an ε-residual fixed-point of f, requires ${\displaystyle \Omega (L'/\varepsilon )}${\displaystyle \Omega (L'/\varepsilon )} function evaluations, where ${\displaystyle L'}${\displaystyle L'} is the Lipschitz constant of the function ${\displaystyle f(x)-x}${\displaystyle f(x)-x} (note that ${\displaystyle L-1\leq L'\leq L+1}${\displaystyle L-1\leq L'\leq L+1}). More precisely:

• For a 2-dimensional function (d=2), they prove a tight bound ${\displaystyle \Theta (L'/\varepsilon )}${\displaystyle \Theta (L'/\varepsilon )}.
• For any d ≥ 3, finding an ε-residual fixed-point of a d-dimensional function requires ${\displaystyle \Omega ((L'/\varepsilon )^{d-2})}${\displaystyle \Omega ((L'/\varepsilon )^{d-2})} queries and ${\displaystyle O((L'/\varepsilon )^{d})}${\displaystyle O((L'/\varepsilon )^{d})} queries.

The latter result leaves a gap in the exponent. Chen and Deng^[18] closed the gap. They proved that, for any d ≥ 2 and ${\displaystyle 1/\varepsilon >4d}${\displaystyle 1/\varepsilon >4d} and ${\displaystyle L'/\varepsilon >192d^{3}}${\displaystyle L'/\varepsilon >192d^{3}}, the number of queries required for computing an ε-residual fixed-point is in ${\displaystyle \Theta ((L'/\varepsilon )^{d-1})}${\displaystyle \Theta ((L'/\varepsilon )^{d-1})}.

A discrete function is a function defined on a subset of ${\displaystyle \mathbb {Z} ^{d}}${\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 ${\displaystyle f}${\displaystyle f} is a function from a rectangle subset of ${\displaystyle \mathbb {Z} ^{d}}${\displaystyle \mathbb {Z} ^{d}} to itself, and ${\displaystyle f}${\displaystyle f} is hypercubic direction-preserving , then ${\displaystyle f}${\displaystyle f} has a fixed point.

Let ${\displaystyle f}${\displaystyle f} be a direction-preserving function from the integer cube ${\displaystyle \{1,\dots ,n\}^{d}}${\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})}${\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 ${\displaystyle f}${\displaystyle f} on ${\displaystyle \{0,\dots ,n\}^{2}}${\displaystyle \{0,\dots ,n\}^{2}} such that, for every x on the grid, ${\displaystyle f}${\displaystyle 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 ${\displaystyle f}${\displaystyle f} must map the square ${\displaystyle \{0,\dots ,n\}^{2}}${\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 ${\displaystyle g}${\displaystyle g} from ${\displaystyle E^{d}}${\displaystyle E^{d}} to R, a root of ${\displaystyle g}${\displaystyle g} is a point x in ${\displaystyle E^{d}}${\displaystyle E^{d}} such that ${\displaystyle g}${\displaystyle g}(x)=0. An ε-root of g is a point x in ${\displaystyle E^{d}}${\displaystyle E^{d}} such that ${\displaystyle g(x)\leq \varepsilon }${\displaystyle g(x)\leq \varepsilon }.

Fixed-point computation is a special case of root-finding: given a function ${\displaystyle f}${\displaystyle f} on ${\displaystyle E^{d}}${\displaystyle E^{d}}, define ${\displaystyle g(x):=|f(x)-x|}${\displaystyle g(x):=|f(x)-x|}. X is a fixed-point of ${\displaystyle f}${\displaystyle f} if and only if x is a root of ${\displaystyle g}${\displaystyle g}, and x is an ε-residual fixed-point of ${\displaystyle f}${\displaystyle f} if and only if x is an ε-root of ${\displaystyle g}${\displaystyle 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})}${\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 ))}${\displaystyle O(\log(1/\varepsilon ))} queries using the bisection method). Here is a proof sketch.^{[3] : 35} Construct a function ${\displaystyle g}${\displaystyle g} that is slightly larger than ε everywhere in ${\displaystyle E^{d}}${\displaystyle E^{d}} except in some small cube around some point x₀, where x₀ is the unique root of ${\displaystyle g}${\displaystyle g}. If ${\displaystyle g}${\displaystyle g} is Lipschitz continuous with constant ${\displaystyle L}${\displaystyle L}, then the cube around x₀ can have a side-length of ${\displaystyle \varepsilon /L}${\displaystyle \varepsilon /L}. Any algorithm that finds an ε-root of ${\displaystyle g}${\displaystyle g} must check a set of cubes that covers the entire ${\displaystyle E^{d}}${\displaystyle E^{d}}; the number of such cubes is at least ${\displaystyle (L/\varepsilon )^{d}}${\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 ${\displaystyle g}${\displaystyle g} such that ${\displaystyle g(x)+x}${\displaystyle g(x)+x} maps ${\displaystyle E^{d}}${\displaystyle E^{d}} to itself (that is: ${\displaystyle g(x)+x}${\displaystyle g(x)+x} is in ${\displaystyle E^{d}}${\displaystyle E^{d}} for all x in ${\displaystyle E^{d}}${\displaystyle E^{d}}). This is because, for every such function, the function ${\displaystyle f(x):=g(x)+x}${\displaystyle f(x):=g(x)+x} satisfies the conditions of Brouwer's fixed-point theorem. X is a fixed-point of ${\displaystyle f}${\displaystyle f} if and only if x is a root of ${\displaystyle g}${\displaystyle g}, and x is an ε-residual fixed-point of ${\displaystyle f}${\displaystyle f} if and only if x is an ε-root of ${\displaystyle g}${\displaystyle g}. Chen and Deng^[18] show that the discrete variants of these problems are computationally equivalent: both problems require ${\displaystyle \Theta (n^{d-1})}${\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 ${\displaystyle f}${\displaystyle f} and the other knows a function ${\displaystyle g}${\displaystyle 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}${\displaystyle g\circ f}. They show that the deterministic communication complexity is in ${\displaystyle \Omega (2^{d})}${\displaystyle \Omega (2^{d})}.

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

• Fixed-point theorems
• Numerical analysis

• Wikipedia articles needing page number citations from April 2023
• Articles with short description
• Short description matches Wikidata