Fixed-point computation: Difference between revisions

Revision as of 11:44, 16 April 2023

Latest revision as of 11:38, 15 August 2025

(41 intermediate revisions by 24 users not shown)

Line 1:

{{Short description|Computing the fixed point of a function}}

'''Fixed-point computation''' refers to the process of computing an exact or approximate [[Fixed point (mathematics)|fixed point]] of a given function.<ref name=":1">{{Cite book |url=https://link.springer.com/book/10.1007/978-3-642-50327-6 |title=The Computation of Fixed Points and Applications |language=en |doi=10.1007/978-3-642-50327-6}}</ref> 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|''d''-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 in [[dynamic system]] analysis.

{{CS1 config|mode=cs1}}

'''Fixed-point computation''' refers to the process of computing an exact or approximate [[Fixed point (mathematics)|fixed point]] of a given function.<ref name=":1">{{Citecite book |urldoi=https://link.springer.com/book/10.1007/978-3-642-50327-6 |title=The Computation of Fixed Points and Applications |languageseries=enLecture Notes in Economics and Mathematical Systems |doiyear=1976 |volume=124 |isbn=10.1007/978-3-642540-5032707685-68 }}</ref> In its most common form, we arethe given a function ''<math>f'' that</math> satisfies the condition to the [[Brouwer fixed-point theorem]],: that is:, ''<math>f''</math> is continuous and maps the unit [[N-cube|''d''-cube]] to itself. The [[Brouwer fixed-point theorem]] guarantees that ''<math>f''</math> has a fixed point, but the proof is not [[Constructive proof|constructive]]. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in economicsvarious for computing a [[market equilibrium]]tasks, insuch game theory for computing a [[Nash equilibrium]], and in [[dynamic system]] analysis.as

* [[Nash equilibrium computation]],

* [[Market equilibrium computation]],

* [[Dynamic system]] analysis.

== Definitions ==

[[File:Fixed point example.svg|alt=an example function with three fixed points|thumb|The graph of an example function with three fixed points]]

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

A '''fixed point''' of ''<math>f''</math> is a point ''<math>x''</math> in ''E<supmath>E^d</supmath>'' such that ''<math>f''(''x'') ='' x''</math>. By the [[Brouwer fixed-point theorem]], any contiuouscontinuous function from ''E<supmath>E^d</supmath>'' 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:<ref name=":3">{{Citecite journal |lastlast1=Shellman |firstfirst1=Spencer |last2=Sikorski |first2=K. |date=2003-12-01 |title=A recursive algorithm for the infinity-norm fixed point problem |url=https://www.sciencedirect.com/science/article/pii/S0885064X03000682 |journal=Journal of Complexity |languagedate=enDecember 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |issn=0885doi-064Xaccess=free }}</ref>

* The '''residual criterion''': given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-residual fixed-point of''' '''''<math>f''</math>''' is a point ''<math>x''</math> in ''E<supmath>E^d</supmath>'' such that <math>|f(x)-x|\leq \varepsilon</math>, where here ''<math>|.\cdot|''</math> denotes the [[maximum norm]]. That is, all ''<math>d''</math> coordinates of the difference <math>f(x)-x</math> should be at most {{mvar|ε}}.<ref name=":0" />{{Rp|page=4}}

* The '''absolute criterion''': given an approximation parameter <math>\delta>0</math>, A '''δ-absolute fixed-point of''' '''''<math>f''</math>''' is a point ''<math>x''</math> in ''E<supmath>E^d</supmath>'' such that <math>|x-x_0| \leq \delta</math>, where <math>x_0</math> is any fixed-point of ''<math>f</math>.''

* The '''relative criterion''': given an approximation parameter <math>\delta>0</math>, A '''δ-relative fixed-point of''' '''''<math>f''</math>''' is a point ''x'' in ''E<supmath>E^d</supmath>'' such that <math>|x-x_0|/|x_0|\leq \delta</math>, where <math>x_0</math> is any fixed-point of ''<math>f</math>.''

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If ''<math>f''</math> is Lipschitz-continuous with constant ''<math>L''</math>, then <math>|x-x_0|\leq \delta</math> implies <math>|f(x)-f(x_0)|\leq L\cdot \delta</math>. Since <math>x_0</math> is a fixed-point of ''<math>f''</math>, this implies <math>|f(x)-x_0|\leq L\cdot \delta</math>, so <math>|f(x)-x|\leq (1+L)\cdot \delta</math>. Therefore, a δ-absolute fixed-point is also an {{mvar|ε}}-residual fixed-point with <math>\varepsilon = (1+L)\cdot \delta</math>.

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

The function ''<math>f''</math> is accessible via '''evaluation''' queries: for any ''<math>x''</math>, the algorithm can evaluate ''<math>f''(''x'')</math>. The run-time complexity of an algorithm is usually given by the number of required evaluations. {{Under construction|placedby=Erel Segal}}

== Contractive functions ==

A Lipschitz-continuous function with constant ''<math>L''</math> is called [[Contractive|'''[[contractive]]''']] if ''<math>L''<1</math>; it is called [[Weakly-contractive|'''[[weakly-contractive]]''']] if ''L≤''<math>L\le 1</math>. Every contractive function satisfying Brouwer's condisionsconditions has a ''unique'' fixed point. Moreover, fixed-point computation for contractive functions is easier than for general functions.

[[File:Fixed point anime.gif|alt=computing a fixed point using function iteration|thumb|Computing a fixed point using function iteration]]

The first algorithm for fixed-point computation was the '''[[fixed-point iteration]]''' algorithm of Banach. [[Banach fixed point theorem|Banach's fixed-point theorem]] implies that, when fixed-point iteration is applied to a contraction mapping, the error after ''<math>t''</math> iterations is in <math>O(L^t)</math>. Therefore, the number of evaluations required for a ''δ''<math>\delta</math>-relative fixed-point is approximately <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. Sikorski and Wozniakowski<ref name=":5">{{Citecite journal |lastlast1=Sikorski |firstfirst1=K |last2=Woźniakowski |first2=H |date=1987-12-01 |title=Complexity of fixed points, I |url=https://www.sciencedirect.com/science/article/pii/0885064X87900082 |journal=Journal of Complexity |languagedate=enDecember 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 |issn=0885doi-064Xaccess=free }}</ref> showed that Banach's algorithm is optimal when the dimension is large. Specifically, when <math>d\geq \log(1/\delta)/\log(1/L) </math>, the number of required evaluations of ''any'' algorithm for ''δ''<math>\delta</math>-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when ''<math>L''</math> approaches 1, the number of evaluations approaches infinity. In fact, noNo finite algorithm can compute a ''δ''<math>\delta</math>-absolute fixed point for all functions with <math>L=1</math>.<ref name=":4">{{Citecite webbook |lastlast1=Sikorski |firstfirst1=KKrzysztof |date=2001A. |title=Optimal solutionSolution of nonlinearNonlinear equationsEquations |urldate=https://dl.acm.org/doi/abs/10.5555/3704372001 |access-datepublisher=2023-04-16Oxford University Press |websiteisbn=Guide978-0-19-510690-9 books}}{{page needed|languagedate=ENApril |doi=2023}}</ref>

When <math>L</math> < 1 and ''d'' = 1, the optimal algorithm is the '''Fixed Point Envelope''' (FPE) algorithm of Sikorski and Wozniakowski.<ref name=":5" /> It finds a ''δ''-relative fixed point using <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> queries, and a ''δ''-absolute fixed point using <math>O(\log(1/\delta)) </math> queries. This is much faster than the fixed-point iteration algorithm.<ref>{{Citationcite |last=Sikorskibook |firstdoi=K10.1007/978-1-4615-9552-6_4 |titlechapter=Fast Algorithms for the Computation of Fixed Points |date=1989 |url=https://doi.org/10.1007/978-1-4615-9552-6_4 |worktitle=Robustness in Identification and Control |pagesyear=49–581989 |editor-lastlast1=MilaneseSikorski |editor-firstfirst1=MK. |access-datepages=2023-04-14 |place=Boston, MA |publisher=Springer US |language=en |doi=10.1007/978-1-4615-9552-6_449–58 |isbn=978-1-4615-95529554-60 |editor2-last=Tempo |editor2-first=R. |editor3-last=Vicino |editor3-first=A.}}</ref>

The first algorithm for fixed-point computation was the [[fixed-point iteration]] algorithm of Banach. [[Banach fixed point theorem|Banach's fixed-point theorem]] implies that, when fixed-point iteration is applied to a contraction mapping, the error after ''t'' iterations is in <math>O(L^t)</math>. Therefore, the number of evaluations required for a ''δ''-relative fixed-point is approximately <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. Sikorski and Wozniakowski<ref name=":5">{{Cite journal |last=Sikorski |first=K |last2=Woźniakowski |first2=H |date=1987-12-01 |title=Complexity of fixed points, I |url=https://www.sciencedirect.com/science/article/pii/0885064X87900082 |journal=Journal of Complexity |language=en |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 |issn=0885-064X}}</ref> showed that Banach's algorithm is optimal when the dimension is large. Specifically, when <math>d\geq \log(1/\delta)/\log(1/L) </math>, 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.<ref name=":4">{{Cite web |last=Sikorski |first=K |date=2001 |title=Optimal solution of nonlinear equations |url=https://dl.acm.org/doi/abs/10.5555/370437 |access-date=2023-04-16 |website=Guide books |language=EN |doi=}}</ref>

When <math>d>1</math> but not too large, and <math>L\le 1</math>, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).<ref>{{cite journal |last1=Huang |first1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |title=Approximating Fixed Points of Weakly Contracting Mappings |journal=Journal of Complexity |date=June 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 |doi-access=free }}</ref> It finds an {{mvar|ε}}-residual fixed-point using <math>O(d\cdot \log(1/\varepsilon)) </math> evaluations. When <math>L<1</math>, it finds a <math>\delta</math>-absolute fixed point using <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> evaluations.

When L<1 and ''d''=1, the optimal algorithm is the Fixed Point Envelope (FPE) algorithm of Sikorski and Wozniakowski.<ref name=":5" /> It finds a ''δ''-relative fixed point using <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> queries, and a ''δ''-absolute fixed point using <math>O(\log(1/\delta)) </math> queries. This is much faster than the fixed-point iteration algorithm.<ref>{{Citation |last=Sikorski |first=K. |title=Fast Algorithms for the Computation of Fixed Points |date=1989 |url=https://doi.org/10.1007/978-1-4615-9552-6_4 |work=Robustness in Identification and Control |pages=49–58 |editor-last=Milanese |editor-first=M. |access-date=2023-04-14 |place=Boston, MA |publisher=Springer US |language=en |doi=10.1007/978-1-4615-9552-6_4 |isbn=978-1-4615-9552-6 |editor2-last=Tempo |editor2-first=R. |editor3-last=Vicino |editor3-first=A.}}</ref>

When ''d''>1 but not too large,Shellman and ''L ≤'' 1, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).Sikorski<ref>{{Citecite journal |lastlast1=HuangShellman |firstfirst1=ZSpencer |last2=KhachiyanSikorski |first2=L |last3=Sikorski |first3=K |date=1999-06-01. |title=ApproximatingA FixedTwo-Dimensional PointsBisection ofEnvelope WeaklyAlgorithm Contractingfor MappingsFixed |url=https://www.sciencedirect.com/science/article/pii/S0885064X99905046Points |journal=Journal of Complexity |languagedate=enJune 2002 |volume=1518 |issue=2 |pages=200–213641–659 |doi=10.1006/jcom.19992001.05040625 |issn=0885doi-064Xaccess=free }}</ref> Itpresented an algorithm called '''BEFix''' (Bisection Envelope Fixed-point) for findscomputing an {{mvar|ε}}-residual fixed-point isof usinga two-dimensional function with '<math>O(dL\cdotle 1</math>, using only <math>2 \loglceil\log_2(1/\varepsilon)) \rceil+1</math> evaluationsqueries. WhenThey later<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</ref> presented an improvement called ''L'BEDFix'<1'' (Bisection Envelope Deep-cut Fixed-point), itwith findsthe asame worst-case guarantee but better empirical performance. When <math>L<1</math>, ''δ'BEDFix''' can also compute a <math>\delta</math>-absolute fixed -point using <math>O(d\cdot [\log(1/\deltavarepsilon) + \log(1/(1-L))]) </math> evaluationsqueries.

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

Shellman and Sikorski<ref>{{Cite journal |last=Shellman |first=Spencer |last2=Sikorski |first2=K. |date=2002-06-01 |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |url=https://www.sciencedirect.com/science/article/pii/S0885064X01906259 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 |issn=0885-064X}}</ref> presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an {{mvar|ε}}-residual fixed-point of a two-dimensional function with ''L ≤'' 1, using only <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> queries. They later<ref>{{Cite journal |last=Shellman |first=Spencer |last2=Sikorski |first2=K. |date=2003-09-01 |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |url=https://doi.org/10.1145/838250.838255 |journal=ACM Transactions on Mathematical Software |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |issn=0098-3500}}</ref> 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 <math>O(\log(1/\varepsilon)+\log(1/(1-L)))</math> queries.

Shellman and Sikorski<ref name=":3" /> presented an algorithm called PFix for computing an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function with ''L ≤'' 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can be executed with <math>\varepsilon = (1-L)\cdot \delta</math>, and in that case, it computes a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> 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.

=== Algorithms for differentiable functions ===

When the function ''<math>f''</math> is differentiable, and the algorithm can evaluate its derivative (not only ''<math>f''</math> itself), the [[Newton's method in optimization|Newton method]] can be used and it is much faster.<ref>{{Citecite journal |lastlast1=Kellogg |firstfirst1=R. B. |last2=Li |first2=T. Y. |last3=Yorke |first3=J. |date=September 1976 |title=A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results |url=http://epubs.siam.org/doi/10.1137/0713041 |journal=SIAM Journal on Numerical Analysis |languagedate=enSeptember 1976 |volume=13 |issue=4 |pages=473–483 |doi=10.1137/0713041 |issn=0036-1429}}</ref><ref>{{Citecite journal |lastlast1=Smale |firstfirst1=Steve |date=1976-07-01 |title=A convergent process of price adjustment and global newton methods |url=https://www.sciencedirect.com/science/article/pii/0304406876900197 |journal=Journal of Mathematical Economics |languagedate=enJuly 1976 |volume=3 |issue=2 |pages=107–120 |doi=10.1016/0304-4068(76)90019-7 |issn=0304-4068}}</ref>

== General functions ==

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

=== One dimension ===

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

=== Two or more dimensions: algorithms ===

For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski<ref name=":3" /> proved that, for any integers ''d''≥2 ≥ 2 and ''<math>L''</math> > 1, finding a δ-absolute fixed-point of ''d''-dimensional ''<math>L''</math>-Lipschitz functions might require infinitely- many evaluations. The proof idea is as follows. For any integer ''T'' > 1, and for any sequence of ''T'' of evaluation queries (possibly adaptive), one can construct two functions that are Lipschitz-continuous with constant ''<math>L''</math>, 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 {{mvar|ε}}-residual fixed-point

* The first algorithm to approximate a fixed point of a general function was developed by [[Herbert Scarf]] in 1967.<ref>{{Citecite journal |lastlast1=Scarf |firstfirst1=Herbert |date=1967-09-01 |title=The Approximation of Fixed Points of a Continuous Mapping |url=http://epubs.siam.org/doi/10.1137/0115116 |journal=SIAM Journal on Applied Mathematics |languagedate=enSeptember 1967 |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 |issn=0036-1399}}</ref><ref>H. Scarf found the first algorithmic proof: {{SpringerEOM|title=Brouwer theorem|first=M.I.|last=Voitsekhovskii|isbn=1-4020-0609-8}}.</ref> Scarf's algorithm finds an {{mvar|ε}}-residual fixed-point by finding a fully-labelled labeled "primitive set", in a construction similar to [[Sperner's lemma]].

* A later algorithm by [[Harold W. Kuhn|Harold Kuhn]]<ref>{{Cite journal |last=Kuhn |first=Harold W. |date=1968 |title=Simplicial Approximation of Fixed Points |url=https://www.jstor.org/stable/=58762 |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=61 |issue=4 |pages=1238–1242 |issndoi=002710.1073/pnas.61.4.1238 |pmid=16591723 |pmc=225246 |doi-8424access=free }}</ref> used simplices and simplicial partitions instead of primitive sets.

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{Citecite webthesis |last1=Merrill |first1=Orin Harrison |date=1972 |title=APPLICATIONSApplications ANDand EXTENSIONSExtensions OFof ANan ALGORITHMAlgorithm THATthat COMPUTESComputes FIXEDFixed POINTSPoints OFCERTAINof UPPERCertain SEMIUpper Semi-CONTINUOUScontinuous POINTPoint TOto SETSet MAPPINGSMappings -|id={{NAID|10006142329}} ProQuest|oclc=570461463 |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1?pq-origsite=gscholar&cbl=18750&diss=y |access-date=2023-04-13 |website=www.proquest.com |language=en}}</ref> presented the ''restart algorithm''.

* B. Curtis Eaves<ref>{{Citecite journal |lastlast1=Eaves |firstfirst1=B. Curtis |date=1972-12-01 |title=Homotopies for computation of fixed points |url=https://doi.org/10.1007/BF01584975 |journal=Mathematical Programming |languagedate=enDecember 1972 |volume=3-3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |issns2cid=1436-464639504380 }}</ref> presented the ''[[homotopyHomotopy method]] algorithm''. The algorithm works by starting with an affine function that approximates ''<math>f''</math>, and deforming it towards ''<math>f'',</math> while following the fixed point''.''
* A book by Michael Todd<ref name=":1" /> surveys various algorithms developed until 1976.

* [[David Gale]]<ref>{{cite journal |authorfirst1=David |last1=Gale |year=1979 |title=The Game of Hex and Brouwer Fixed-Point Theorem |journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> 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 ana ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of ana ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

** Construct a Hex board of size ''kd'', where ''<math>k'' > 1/''{{mvar|ε}}''\varepsilon</math>. Each vertex ''z'' corresponds to a point ''z''/''k'' in the unit ''n''-cube.

** Compute the difference ''<math>f''</math>(''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 <math>f</math> 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 <math>\Omega(1/\varepsilon)</math>.

==== Two or more dimensions: queryQuery complexity ====

Hirsch, [[Christos Papadimitriou|Papadimitriou]] and Vavasis proved that<ref name=":0">{{Citecite journal |lastlast1=Hirsch |firstfirst1=Michael D |last2=Papadimitriou |first2=Christos H |last3=Vavasis |first3=Stephen A |date=1989-12-01 |title=Exponential lower bounds for finding Brouwer fix points |url=https://www.sciencedirect.com/science/article/pii/0885064X89900174 |journal=Journal of Complexity |languagedate=enDecember 1989 |volume=5 |issue=4 |pages=379–416 |doi=10.1016/0885-064X(89)90017-4 |issns2cid=0885-064X1727254 }}</ref> ''any'' algorithm based on function evaluations, that finds an {{mvar|ε}}-residual fixed-point of ''f,'' requires <math>\Omega(L'/\varepsilon)</math> function evaluations, where <math>L'</math> is the Lipschitz constant of the function <math>f(x)-x</math> (note that <math>L-1 \leq L' \leq L+1</math>). More precisely:

* For a 2-dimensional function (''d''=2), they prove a tight bound <math>\Theta(L'/\varepsilon)</math>.

* For any d ≥ 3, finding an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function requires <math>\Omega((L'/\varepsilon)^{d-2})</math> queries and <math>O((L'/\varepsilon)^{d})</math> queries.

The latter result leaves a gap in the exponent. Chen and Deng<ref name=":2" /> closed the gap. They proved that, for any ''d'' ≥ 2 and <math>1/\varepsilon > 4 d</math> and <math>L'/\varepsilon > 192 d^3</math>, the number of queries required for computing an {{mvar|ε}}-residual fixed-point is in <math>\Theta((L'/\varepsilon)^{d-1})</math>.

== Discrete fixed-point computation ==

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

Let ''<math>f''</math> be a direction-preserving function from the integer cube <math>\{1,... \dots,'' n''\}<sup>''^d''</supmath> to itself. Chen and Deng<ref name=":2" /> prove that, for any ''d'' ≥ 2 and ''n'' > 48 ''d'', computing such a fixed point requires <math>\Theta(n^{d-1})</math> function evaluations.

Chen and Deng<ref>{{cite journal |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |title=On the complexity of 2D discrete fixed point problem |journal=Theoretical Computer Science |date=October 2009 |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 }}</ref> define a different discrete-fixed-point problem, which they call '''2D-BROUWER'''. It considers a discrete function <math>f</math> on <math>\{0,\dots, n\}^2</math> such that, for every ''x'' on the grid, <math>f</math>(''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 <math>f</math> must map the square <math>\{0,\dots, n\}^2</math>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 ''<math>g''</math> from ''E<supmath>E^d</supmath>'' to ''R'', a '''root''' of ''<math>g''</math> is a point ''x'' in ''E<supmath>E^d</supmath>'' such that ''<math>g''</math>(''x'')=0. An '''{{mvar|ε}}-root''' of g is a point ''x'' in ''E<supmath>E^d</supmath>'' such that <math>g(x)\leq \varepsilon</math>.

Fixed-point computation is a special case of root-finding: given a function ''<math>f''</math> on ''E<supmath>E^d</supmath>'', define <math>g(x) := |f(x)-x|</math>. Clearly, ''xX'' is a fixed-point of ''<math>f''</math> if and only if ''x'' is a root of ''<math>g''</math>, and ''x'' is an {{mvar|ε}}-residual fixed-point of ''<math>f''</math> if and only if ''x'' is an {{mvar|ε}}-root of ''<math>g''</math>. 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<ref>{{Citecite journal |lastlast1=Sikorski |firstfirst1=K. |date=1984-06-01 |title=Optimal solution of nonlinear equations satisfying a Lipschitz condition |url=https://doi.org/10.1007/BF01390124 |journal=Numerische Mathematik |languagedate=enJune 1984 |volume=43 |issue=2 |pages=225–240 |doi=10.1007/BF01390124 |issns2cid=0945-3245120937024 }}</ref> proved that finding an {{mvar|ε}}-root requires <math>\Omega(1/\varepsilon^d)</math> function evaluations. This gives an exponential lower bound even for a one-dimensional function (in contrast, an {{mvar|ε}}-residual fixed-point of a one-dimensional function can be found using <math>O(\log(1/\varepsilon))</math> queries using the [[bisection method]]). Here is a proof sketch.<ref name=":0" />{{Rp|page=35}} Construct a function ''<math>g''</math> that is slightly larger than {{mvar|ε}} everywhere in ''E<supmath>E^d</supmath>'' except in some small cube around some point ''x''₀, where ''x''₀ is the unique root of ''<math>g''</math>. If ''<math>g''</math> is [[Lipschitz continuous]] with constant ''<math>L''</math>, then the cube around ''x''₀ can have a side-length of {{mvar|ε}}<math>\varepsilon/''L''</math>. Any algorithm that finds an {{mvar|ε}}-root of ''<math>g''</math> must check a set of cubes that covers the entire ''E<supmath>E^d</supmath>''; the number of such cubes is at least <math>(L/\varepsilon)^d</math>.

However, there are classes of functions for which finding an approximate root is equivalent to finding an approximate fixed point. One example<ref name=":2">{{Citecite journalbook |lastdoi=Chen10.1145/1060590.1060638 |first=Xi |last2=Deng |first2=Xiaotie |date=2005-05-22 |titlechapter=On algorithms for discrete and approximate brouwer fixed points |url=https://doi.org/10.1145/1060590.1060638 |journaltitle=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |seriesyear=STOC2005 '05|last1=Chen |___locationfirst1=NewXi York, NY, USA|last2=Deng |publisherfirst2=Association for Computing MachineryXiaotie |pages=323–330 |doiisbn=10.1145/1060590.10606381581139608 |isbns2cid=978-1-58113-960-016942881 }}</ref> is the class of functions ''<math>g''</math> such that <math>g(x)+x</math> maps ''E<supmath>E^d</supmath>'' to itself (that is: ''<math>g''(x)+x</math> is in ''E<supmath>E^d</supmath>'' for all x in ''E<supmath>E^d</supmath>''). This is because, for every such function, the function <math>f(x) := g(x)+x</math> satisfies the conditions toof Brouwer's fixed-point theorem. Clearly, ''xX'' is a fixed-point of ''<math>f''</math> if and only if ''x'' is a root of ''<math>g''</math>, and ''x'' is an {{mvar|ε}}-residual fixed-point of ''<math>f''</math> if and only if ''x'' is an {{mvar|ε}}-root of ''<math>g''</math>. Chen and Deng<ref name=":2" /> show that the discrete variants of these problems are computationally equivalent: both problems require <math>\Theta(n^{d-1})</math> function evaluations.

== Communication complexity ==

Roughgarden and Weinstein<ref>{{Citecite journalbook |last=Roughgarden |first=Tim |last2=Weinstein |first2=Omri |datedoi=10.1109/FOCS.2016-10.32 |titlechapter=On the Communication Complexity of Approximate Fixed Points |url=https://ieeexplore.ieee.org/document/7782935 |journaltitle=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |year=2016 |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |pages=229–238 |doiisbn=10.1109/FOCS.2016.32978-1-5090-3933-3 |s2cid=87553 }}</ref> studied the [[communication complexity]] of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function ''<math>f''</math> and the other knows a function ''<math>g''</math>. Both functions are Lipschitz continuous and satisfy Brouwer's conditions. The goal is to compute an approximate fixed point of the [[composite function]] <math>g\circ f</math>. They show that the deterministic communication complexity is in <math>\Omega(2^d)</math>.

== References ==

{{reflist}}

== Further reading ==

* {{cite journal |last1=Yannakakis |first1=Mihalis |title=Equilibria, fixed points, and complexity classes |journal=Computer Science Review |date=May 2009 |volume=3 |issue=2 |pages=71–85 |doi=10.1016/j.cosrev.2009.03.004 |url=https://drops.dagstuhl.de/opus/volltexte/2008/1311/|arxiv=0802.2831 }}

[[Category:Fixed-point theorems]]