Fixed-point computation

Contractive functions

A Lipschitz-continuous function with constant ${\displaystyle L}$ is called contractive if ${\displaystyle L<1}$; it is called weakly-contractive if ${\displaystyle L\le 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}$ iterations is in ${\displaystyle O(L^t)}$. Therefore, the number of evaluations required for a ${\displaystyle \delta }$-relative fixed-point is approximately ${\displaystyle {\log }_L(\delta )=\log (\delta )/\log (L)=\log (1/\delta )/\log (1/L)}$. Sikorski and Wozniakowski showed that Banach's algorithm is optimal when the dimension is large. Specifically, when ${\displaystyle d\ge \log (1/\delta )/\log (1/L)}$, the number of required evaluations of any algorithm for ${\displaystyle \delta }$-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ${\displaystyle L}$ approaches 1, the number of evaluations approaches infinity. No finite algorithm can compute a ${\displaystyle \delta }$-absolute fixed point for all functions with ${\displaystyle L=1}$.

When ${\displaystyle 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 ${\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 faster than the fixed-point iteration algorithm.

When ${\displaystyle d>1}$ but not too large, and ${\displaystyle L\le 1}$, the optimal algorithm is the interior-ellipsoid algorithm (based on the ellipsoid method). It finds an ε-residual fixed-point using ${\displaystyle O(d\cdot \log (1/\epsilon ))}$ evaluations. When ${\displaystyle L<1}$, it finds a ${\displaystyle \delta }$-absolute fixed point using ${\displaystyle O(d\cdot [\log (1/\delta )+\log (1/(1-L))])}$ 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 '${\displaystyle L\le 1}$, using only ${\displaystyle 2\lceil {\log }_2(1/\epsilon )\rceil +1}$ 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 ${\displaystyle L<1}$, BEDFix can also compute a ${\displaystyle \delta }$-absolute fixed-point using ${\displaystyle O(\log (1/\epsilon )+\log (1/(1-L)))}$ queries.

Shellman and Sikorski 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/\epsilon ))}$ queries. When ${\displaystyle L}$ < 1, PFix can be executed with ${\displaystyle \epsilon =(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 ${\displaystyle L}$ is close to 1. The algorithm is recursive: it handles a d-dimensional function by recursive calls on (d-1)-dimensional functions.

Algorithms for differentiable functions

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

General functions: one dimension

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

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

General functions: two or more dimensions

For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski proved that for any integers d ≥ 2 and ${\displaystyle L}$ > 1, finding a δ-absolute fixed-point of d-dimensional ${\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}$, 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.

Simplicial method

The first algorithm to approximate a fixed point of a general function was developed by Herbert Scarf in 1967. 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 used simplices and simplicial partitions instead of primitive sets.

Developing the simplicial approach further, Orin Harrison Merrill presented the restart algorithm.

Homotopy method

B. Curtis Eaves presented the homotopy method, based on the concept of homotopy.

Given a function f, for which we want to find a fixed point, the algorithm works by starting with an affine function that approximates f, and deforming it towards f while following the fixed point.

The homotopy method has been used for market equilibrium computation.

The method is further explained in a book by Michael Todd, which surveys various algorithms developed until 1976.

Other algorithms

• David Gale 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/\epsilon }$. Each vertex z corresponds to a point z/k in the unit n-cube.
  • Compute the difference ${\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}$ 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 \mathrm{\Omega }(1/\epsilon )}$.

Query complexity

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

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

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

Discrete fixed-point computation

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

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

Chen and Deng define a different discrete-fixed-point problem, which they call 2D-BROUWER. It considers a discrete function ${\displaystyle f}$ on ${\displaystyle \{0,\dots ,n{\}}^2}$ such that, for every x on the grid, ${\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}$ 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.

Relation between fixed-point computation and root-finding algorithms

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

Fixed-point computation is a special case of root-finding: given a function ${\displaystyle f}$ on ${\displaystyle E^d}$, define ${\displaystyle g(x):=|f(x)-x|}$. X is a fixed-point of ${\displaystyle f}$ if and only if x is a root of ${\displaystyle g}$, and x is an ε-residual fixed-point of ${\displaystyle f}$ if and only if x is an ε-root of ${\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 proved that finding an ε-root requires ${\displaystyle \mathrm{\Omega }(1/{\epsilon }^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/\epsilon ))}$ queries using the bisection method). Here is a proof sketch. Construct a function ${\displaystyle g}$ that is slightly larger than ε everywhere in ${\displaystyle E^d}$ except in some small cube around some point x₀, where x₀ is the unique root of ${\displaystyle g}$. If ${\displaystyle g}$ is Lipschitz continuous with constant ${\displaystyle L}$, then the cube around x₀ can have a side-length of ${\displaystyle \epsilon /L}$. Any algorithm that finds an ε-root of ${\displaystyle g}$ must check a set of cubes that covers the entire ${\displaystyle E^d}$; the number of such cubes is at least ${\displaystyle (L/\epsilon {)}^d}$.

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

Communication complexity

Roughgarden and Weinstein 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}$ and the other knows a function ${\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}$. They show that the deterministic communication complexity is in ${\displaystyle \mathrm{\Omega }(2^d)}$.