Fixed-point computation

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 n-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 more.

Definitions

The unit interval is denoted by 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, $|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. Given an approximation parameter $\varepsilon >0$ , An ε-fixed-point of f is a point x in E^d such that $|f(x)-x|\leq \varepsilon$, where here |.| denotes the maximum norm. That is, all d coordinates of the difference $f(x)-x$ should be at most ε.

An alternative possible definition of an approximate fixed point uses an approximation parameter $\delta >0$. A δ-near fixed-point of f is a point x in E^d such that $|x-x_{0}|\leq \delta$, where $x_{0}$ is any fixed-point of f (this criterion is also called the absolute criterion). Note that, if f is Lipschitz-continuous with constant L, then $|x-x_{0}|\leq \delta$ implies $|f(x)-f(x_{0})|\leq L\cdot \delta$. Since $x_{0}$ is a fixed-point of f, this implies $|f(x)-x_{0}|\leq L\cdot \delta$, so $|f(x)-x|\leq (L+1)\cdot \delta$. Therefore, a δ-near fixed-point is also an ε-fixed-point with $\varepsilon =(L+1)\cdot \delta$.

Algorithms based on function evaluations

The most general algorithms use only function evaluations: they receive as an input a black-box that, for any x, returns the value of f(x). They do not use any other information on the function f (e.g. its derivative).

One dimension

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

Two or more dimensions: algorithms

For functions in two or more dimensions, the problem is much more challenging. Several algorithms based on function evaluations have been developed.

• The first algorithm to approximate a fixed point was developed by Herbert Scarf in 1967. Scarf's algorithm finds an approximate fixed point by finding a fully-labelled "primitive set", in a construction similar to Sperner's lemma. A subtle aspect of Scarf's algorithm is that it finds an ε-fixed-point of f, that is, a point that is almost fixed by a function f, but in general cannot find a δ-near fixed-point of f, that is, a point that is close to an actual fixed point.
• 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.
• B. Curtis Eaves presented the homotopy algorithm. The algorithm works by starting with an affine function that approximates f, and deforming it towards f, while following the fixed point. A book by Michael Todd surveys various algorithms developed until 1976.
• 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 an d-dimensional game of Hex (a game with d players, each of whom needs to connect two opposite faces of an d-cube). Given the desired accuracy ε
  • Construct a Hex board of size kd, where k>1/ε. Each vertex z corresponds to a point z/k in the unit n-cube.
  • Compute the difference 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 f between these two points.

In the worst case, the number of function evaluations required by all these algorithms is exponential, that is, $\Omega (1/\varepsilon )$.

Two or more dimensions: query complexity

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

• For a 2-dimensional function (d=2), they prove a tight bound $\Theta (L'/\varepsilon )$.
• For any d ≥ 3, finding an ε-fixed-point of a d-dimensional function requires $\Omega ((L'/\varepsilon )^{d-2})$ queries and $O((L'/\varepsilon )^{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 $1/\varepsilon >4d$ and $L'/\varepsilon >192d^{3}$, the number of queries required for computing an ε-fixed-point is in $\Theta ((L'/\varepsilon )^{d-1})$.

Algorithms for contraction mappings

A contraction mapping (also called a contractive Lipschitz function) is a Lipschitz-continuous function with constant L<1. When the Lipschitz constant is smaller than 1, a fixed point of a contraction mapping can be found much faster than in the general case. Some algorithms for this case are:

• The fixed-point iteration algorithm of Banach. The Banach fixed-point theorem implies that, when fixed-point iteration is applied to a contraction mapping, the error after t iterations is in $O(L^{t})$. Therefore, the number of evaluations required for accuracy ε is in $O(\log _{L}(\varepsilon )=\log(\varepsilon )/\log(L)=\log(1/\varepsilon )/\log(1/L))$.
• The Newton method - which requires to know not only the function f but also its derivative.
• The interior ellipsoid algorithm.

The special case in which the Lipschitz constant is exactly 1 is not covered by the above results, but there are specialized algorithms for this case:

• Shellman and Sikorski presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an ε-fixed-point of a two-dimensional function with Lipschitz constant L=1, using only $2\lceil \log _{2}(1/\varepsilon )\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 L<1, BEDFix can also compute a δ-near fixed-point, using $O(\log(1/\varepsilon )+\log(1/(1-L)))$ queries.
• Shellman and Sikorski presented an algorithm called PFix for computing an ε-fixed-point of a d-dimensional function with Lipschitz constant L=1, using $O(\log ^{d}(1/\varepsilon ))$ queries. When L<1, PFix can also compute a δ-near fixed-point, using $O(\log ^{d}(1/[(1-L)\delta ]))$ queries (that is: a similar complexity but with $\varepsilon =(1-L)\cdot \delta$). They also prove that, when L>1, finding a δ-near fixed-point might require infinitely-many evaluation queries.

Discrete fixed-point computation

A discrete function is a function defined on a subset of $\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 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 {1,...,n}^d to itself. Chen and Deng prove that, for any d ≥ 2 and n > 48 d, computing such a fixed point requires $\Theta (n^{d-1})$ function evaluations.

Relation between fixed-point computation and root-finding algorithms

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 $g(x)\leq \varepsilon$.

Fixed-point computation is a special case of root-finding: given a function f on E^d, define $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 ε-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 proved that finding an ε-root requires $\Omega (1/\varepsilon ^{d})$ function evaluations. This gives an exponential lower bound even for a one-dimensional function (in contrast, an ε-fixed-point of a one-dimensional function can be found using $O(\log(1/\varepsilon ))$ queries using the bisection method). Here is a proof sketch. 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 ε/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 $(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 is the class of functions g such that $g(x)+x$ maps E^d to itself (that is: g(x)+x is in E^d for all x in E^d). This is because, for every such function, the function $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 ε-fixed-point of f if and only if x is an ε-root of g. Chen and Deng show that the discrete variants of these problems are computationally equivalent: both problems require $\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 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 $g\circ f$. They show that the deterministic communication complexity is in $\Omega (2^{d})$.