Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Fixed-point computation
Computing the fixed point of a function

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 economics for computing a market equilibrium, in game theory for computing a Nash equilibrium, and in dynamic system analysis.

We don't have any images related to Fixed-point computation yet.
We don't have any YouTube videos related to Fixed-point computation yet.
We don't have any PDF documents related to Fixed-point computation yet.
We don't have any Books related to Fixed-point computation yet.
We don't have any archived web articles related to Fixed-point computation yet.

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:2

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

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If f {\displaystyle f} is Lipschitz-continuous with constant L {\displaystyle L} , then | x − x 0 | ≤ δ {\displaystyle |x-x_{0}|\leq \delta } implies | f ( x ) − f ( x 0 ) | ≤ L ⋅ δ {\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta } . Since x 0 {\displaystyle x_{0}} is a fixed-point of f {\displaystyle f} , this implies | f ( x ) − x 0 | ≤ L ⋅ δ {\displaystyle |f(x)-x_{0}|\leq L\cdot \delta } , so | f ( x ) − x | ≤ ( 1 + L ) ⋅ δ {\displaystyle |f(x)-x|\leq (1+L)\cdot \delta } . Therefore, a δ-absolute fixed-point is also an ε-residual fixed-point with ε = ( 1 + L ) ⋅ δ {\displaystyle \varepsilon =(1+L)\cdot \delta } .

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

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

Contractive functions

A Lipschitz-continuous function with constant L {\displaystyle L} is called contractive if L < 1 {\displaystyle L<1} ; it is called weakly-contractive if L ≤ 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 t {\displaystyle t} iterations is in O ( L t ) {\displaystyle O(L^{t})} . Therefore, the number of evaluations required for a δ {\displaystyle \delta } -relative fixed-point is approximately log L ⁡ ( δ ) = log ⁡ ( δ ) / log ⁡ ( L ) = log ⁡ ( 1 / δ ) / log ⁡ ( 1 / L ) {\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)} . Sikorski and Wozniakowski4 showed that Banach's algorithm is optimal when the dimension is large. Specifically, when d ≥ log ⁡ ( 1 / δ ) / log ⁡ ( 1 / L ) {\displaystyle d\geq \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 L {\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 L = 1 {\displaystyle L=1} .5

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

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

Shellman and Sikorski9 presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an ε-residual fixed-point of a two-dimensional function with ' L ≤ 1 {\displaystyle L\leq 1} , using only 2 ⌈ log 2 ⁡ ( 1 / ε ) ⌉ + 1 {\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1} queries. They later10 presented an improvement called BEDFix (Bisection Envelope Deep-cut Fixed-point), with the same worst-case guarantee but better empirical performance. When L < 1 {\displaystyle L<1} , BEDFix can also compute a δ {\displaystyle \delta } -absolute fixed-point using O ( log ⁡ ( 1 / ε ) + log ⁡ ( 1 / ( 1 − L ) ) ) {\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))} queries.

Shellman and Sikorski11 presented an algorithm called PFix for computing an ε-residual fixed-point of a d-dimensional function with L ≤ 1, using O ( log d ⁡ ( 1 / ε ) ) {\displaystyle O(\log ^{d}(1/\varepsilon ))} queries. When L {\displaystyle L} < 1, PFix can be executed with ε = ( 1 − L ) ⋅ δ {\displaystyle \varepsilon =(1-L)\cdot \delta } , and in that case, it computes a δ-absolute fixed-point, using O ( log d ⁡ ( 1 / [ ( 1 − L ) δ ] ) ) {\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))} queries. It is more efficient than the iteration algorithm when 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.

Algorithms for differentiable functions

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

General functions

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

One dimension

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

Two or more dimensions

For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski15 proved that for any integers d ≥ 2 and L {\displaystyle L} > 1, finding a δ-absolute fixed-point of d-dimensional 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 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.1617 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 Kuhn18 used simplices and simplicial partitions instead of primitive sets.
  • Developing the simplicial approach further, Orin Harrison Merrill19 presented the restart algorithm.
  • B. Curtis Eaves20 presented the homotopy algorithm. The algorithm works by starting with an affine function that approximates f {\displaystyle f} , and deforming it towards f {\displaystyle f} while following the fixed point. A book by Michael Todd21 surveys various algorithms developed until 1976.
  • David Gale22 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 k > 1 / ε {\displaystyle k>1/\varepsilon } . Each vertex z corresponds to a point z/k in the unit n-cube.
    • Compute the difference 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 fi(z/k) - z/k is positive, and an adjacent point in which fi(z/k) - z/k is negative. This means that there is a fixed point of 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 Ω ( 1 / ε ) {\displaystyle \Omega (1/\varepsilon )} .

Query complexity

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

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

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

Discrete fixed-point computation

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

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

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

Relation between fixed-point computation and root-finding algorithms

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

Fixed-point computation is a special case of root-finding: given a function f {\displaystyle f} on E d {\displaystyle E^{d}} , define g ( x ) := | f ( x ) − x | {\displaystyle g(x):=|f(x)-x|} . X is a fixed-point of f {\displaystyle f} if and only if x is a root of g {\displaystyle g} , and x is an ε-residual fixed-point of f {\displaystyle f} if and only if x is an ε-root of 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, Sikorski27 proved that finding an ε-root requires Ω ( 1 / ε 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 O ( log ⁡ ( 1 / ε ) ) {\displaystyle O(\log(1/\varepsilon ))} queries using the bisection method). Here is a proof sketch.28: 35  Construct a function g {\displaystyle g} that is slightly larger than ε everywhere in E d {\displaystyle E^{d}} except in some small cube around some point x0, where x0 is the unique root of g {\displaystyle g} . If g {\displaystyle g} is Lipschitz continuous with constant L {\displaystyle L} , then the cube around x0 can have a side-length of ε / L {\displaystyle \varepsilon /L} . Any algorithm that finds an ε-root of g {\displaystyle g} must check a set of cubes that covers the entire E d {\displaystyle E^{d}} ; the number of such cubes is at least ( L / ε ) 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 example29 is the class of functions g {\displaystyle g} such that g ( x ) + x {\displaystyle g(x)+x} maps E d {\displaystyle E^{d}} to itself (that is: g ( x ) + x {\displaystyle g(x)+x} is in E d {\displaystyle E^{d}} for all x in E d {\displaystyle E^{d}} ). This is because, for every such function, the function 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 f {\displaystyle f} if and only if x is a root of g {\displaystyle g} , and x is an ε-residual fixed-point of f {\displaystyle f} if and only if x is an ε-root of g {\displaystyle g} . Chen and Deng30 show that the discrete variants of these problems are computationally equivalent: both problems require Θ ( n d − 1 ) {\displaystyle \Theta (n^{d-1})} function evaluations.

Communication complexity

Roughgarden and Weinstein31 studied the communication complexity of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function f {\displaystyle f} and the other knows a function 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 g ∘ f {\displaystyle g\circ f} . They show that the deterministic communication complexity is in Ω ( 2 d ) {\displaystyle \Omega (2^{d})} .

Further reading

References

  1. The Computation of Fixed Points and Applications. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8. 978-3-540-07685-8 ↩

  2. Shellman, Spencer; Sikorski, K. (December 2003). "A recursive algorithm for the infinity-norm fixed point problem". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001. https://doi.org/10.1016%2Fj.jco.2003.06.001 ↩

  3. Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254. /wiki/Doi_(identifier) ↩

  4. Sikorski, K; Woźniakowski, H (December 1987). "Complexity of fixed points, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2. https://doi.org/10.1016%2F0885-064X%2887%2990008-2 ↩

  5. Sikorski, Krzysztof A. (2001). Optimal Solution of Nonlinear Equations. Oxford University Press. ISBN 978-0-19-510690-9.[page needed] 978-0-19-510690-9 ↩

  6. Sikorski, K; Woźniakowski, H (December 1987). "Complexity of fixed points, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2. https://doi.org/10.1016%2F0885-064X%2887%2990008-2 ↩

  7. Sikorski, K. (1989). "Fast Algorithms for the Computation of Fixed Points". Robustness in Identification and Control. pp. 49–58. doi:10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0. 978-1-4615-9554-0 ↩

  8. Huang, Z; Khachiyan, L; Sikorski, K (June 1999). "Approximating Fixed Points of Weakly Contracting Mappings". Journal of Complexity. 15 (2): 200–213. doi:10.1006/jcom.1999.0504. https://doi.org/10.1006%2Fjcom.1999.0504 ↩

  9. Shellman, Spencer; Sikorski, K. (June 2002). "A Two-Dimensional Bisection Envelope Algorithm for Fixed Points". Journal of Complexity. 18 (2): 641–659. doi:10.1006/jcom.2001.0625. https://doi.org/10.1006%2Fjcom.2001.0625 ↩

  10. Shellman, Spencer; Sikorski, K. (September 2003). "Algorithm 825: A deep-cut bisection envelope algorithm for fixed points". ACM Transactions on Mathematical Software. 29 (3): 309–325. doi:10.1145/838250.838255. S2CID 7786886. /wiki/Doi_(identifier) ↩

  11. Shellman, Spencer; Sikorski, K. (December 2003). "A recursive algorithm for the infinity-norm fixed point problem". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001. https://doi.org/10.1016%2Fj.jco.2003.06.001 ↩

  12. Kellogg, R. B.; Li, T. Y.; Yorke, J. (September 1976). "A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results". SIAM Journal on Numerical Analysis. 13 (4): 473–483. doi:10.1137/0713041. /wiki/Doi_(identifier) ↩

  13. Smale, Steve (July 1976). "A convergent process of price adjustment and global newton methods". Journal of Mathematical Economics. 3 (2): 107–120. doi:10.1016/0304-4068(76)90019-7. /wiki/Doi_(identifier) ↩

  14. Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254. /wiki/Doi_(identifier) ↩

  15. Shellman, Spencer; Sikorski, K. (December 2003). "A recursive algorithm for the infinity-norm fixed point problem". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001. https://doi.org/10.1016%2Fj.jco.2003.06.001 ↩

  16. Scarf, Herbert (September 1967). "The Approximation of Fixed Points of a Continuous Mapping". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116. /wiki/Doi_(identifier) ↩

  17. H. Scarf found the first algorithmic proof: Voitsekhovskii, M.I. (2001) [1994]. "Brouwer theorem". Encyclopedia of Mathematics. EMS Press. ISBN 1-4020-0609-8.. 1-4020-0609-8 ↩

  18. Kuhn, Harold W. (1968). "Simplicial Approximation of Fixed Points". Proceedings of the National Academy of Sciences of the United States of America. 61 (4): 1238–1242. doi:10.1073/pnas.61.4.1238. JSTOR 58762. PMC 225246. PMID 16591723. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC225246 ↩

  19. Merrill, Orin Harrison (1972). Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-continuous Point to Set Mappings (Thesis). OCLC 570461463. NAID 10006142329. https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1 ↩

  20. Eaves, B. Curtis (December 1972). "Homotopies for computation of fixed points". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID 39504380. /wiki/Doi_(identifier) ↩

  21. The Computation of Fixed Points and Applications. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8. 978-3-540-07685-8 ↩

  22. Gale, David (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146. /wiki/Doi_(identifier) ↩

  23. Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254. /wiki/Doi_(identifier) ↩

  24. Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881. 1581139608 ↩

  25. Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881. 1581139608 ↩

  26. Chen, Xi; Deng, Xiaotie (October 2009). "On the complexity of 2D discrete fixed point problem". Theoretical Computer Science. 410 (44): 4448–4456. doi:10.1016/j.tcs.2009.07.052. S2CID 2831759. /wiki/Doi_(identifier) ↩

  27. Sikorski, K. (June 1984). "Optimal solution of nonlinear equations satisfying a Lipschitz condition". Numerische Mathematik. 43 (2): 225–240. doi:10.1007/BF01390124. S2CID 120937024. /wiki/Doi_(identifier) ↩

  28. Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254. /wiki/Doi_(identifier) ↩

  29. Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881. 1581139608 ↩

  30. Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881. 1581139608 ↩

  31. Roughgarden, Tim; Weinstein, Omri (2016). "On the Communication Complexity of Approximate Fixed Points". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 229–238. doi:10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID 87553. 978-1-5090-3933-3 ↩