Fixed-point computation: Difference between revisions

Revision as of 10:15, 16 April 2023

Latest revision as of 11:38, 15 August 2025

(46 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 more.

{{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 more.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. Two of the moreSeveral 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 <math>E^d</math> 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 (L+1+L)\cdot \delta</math>. Therefore, a δ-absolute fixed-point is also an {{mvar|ε}}-residual fixed-point with <math>\varepsilon = (1+L+1)\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">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=Complexity of fixed points, I |journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 |doi-access=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. No finite algorithm can compute a <math>\delta</math>-absolute fixed point for all functions with <math>L=1</math>.<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=Optimal Solution of Nonlinear Equations |date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{page needed|date=April 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 faster than the fixed-point iteration algorithm.<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=Robustness in Identification and Control |year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</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 for a ''δ''-absolute fixed point is in <math>O(\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L)) </math>. Banach's algorithm is optimal when the dimension ''d'' is large.<ref>A. Nemirovsky, D.B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley, New York, 1983.</ref><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> But 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" />

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 ''d''=1, the [[bisection method]] can be used, and it is optimal for various error criteria.<ref name=":4" />

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 Lipschitz constant ''L ≤''= 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When <math>L</math> < 1, ''L'PFix''' can be executed with <math>\varepsilon = (1-L)\cdot \delta</math>, PFixand canin alsothat case, it computecomputes a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> queries. (thatIt is: amore similarefficient complexitythan butthe withiteration algorithm when <math>\varepsilon = (1-L)\cdot \delta</math>) is close to 1. TheyThe alsoalgorithm proveis that,recursive: whenit handles a ''Ld''>1,-dimensional findingfunction aby δ-absoluterecursive fixed-pointcalls mighton require infinitely(''d''-many1)-dimensional evaluation queriesfunctions.

* The [[Newton's method in optimization|Newton method]] - which requires to know not only the function ''f'' but also its derivative.<ref>{{Cite web |title=Iterative solution of nonlinear equations in several variables |url=https://dl.acm.org/doi/abs/10.5555/335947 |access-date=2023-04-13 |website=Guide books |language=EN}}</ref><ref>{{Cite journal |last=Kellogg |first=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 |language=en |volume=13 |issue=4 |pages=473–483 |doi=10.1137/0713041 |issn=0036-1429}}</ref><ref>{{Cite journal |last=Smale |first=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 |language=en |volume=3 |issue=2 |pages=107–120 |doi=10.1016/0304-4068(76)90019-7 |issn=0304-4068}}</ref>

* The interior [[Ellipsoid method|ellipsoid algorithm]].

* The Fixed Point Envelope algorithm of Sikorski.<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>

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:

=== Algorithms for differentiable 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 Lipschitz constant ''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.

*When Thethe [[Newton'sfunction method<math>f</math> inis optimization|Newtondifferentiable, method]]and -the whichalgorithm requirescan toevaluate knowits derivative (not only the function ''<math>f''</math> butitself), alsothe its[[Newton's derivative.<ref>{{Citemethod webin optimization|title=IterativeNewton solutionmethod]] ofcan nonlinearbe equationsused inand severalit variablesis |url=https://dlmuch faster.acm.org/doi/abs/10.5555/335947 |access-date=2023-04-13 |website=Guide books |language=EN}}</ref><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>

* Shellman and Sikorski<ref name=":3" /> presented an algorithm called PFix for computing an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function with Lipschitz constant ''L''=1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can also compute a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> queries (that is: a similar complexity but with <math>\varepsilon = (1-L)\cdot \delta</math>). They also prove that, when ''L''>1, finding a δ-absolute fixed-point might require infinitely-many evaluation queries.

== General functions ==

== Algorithms based on function evaluations ==

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

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 δ<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 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 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''.

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

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

* The first algorithm to approximate a fixed point was developed by [[Herbert Scarf]] in 1967.<ref>{{Cite journal |last=Scarf |first=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 |language=en |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 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 {{mvar|ε}}-residual fixed-point of ''f'', that is, a point that is {{em|almost fixed}} by a function ''f'', but in general cannot find a δ-absolute fixed-point of ''f,'' that is, ''a'' point that is close to an actual fixed point.

* 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 |issn=0027-8424}}</ref> used simplices and simplicial partitions instead of primitive sets.

* 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 approximate{{mvar|ε}}-residual fixed -point by finding a fully-labelled labeled "primitive set", in a construction similar to [[Sperner's lemma]]. A subtle aspect of Scarf's algorithm is that it finds an {{mvar|ε}}-residual fixed-point of ''f'', that is, a point that is {{em|almost fixed}} by a function ''f'', but in general cannot find a δ-absolute fixed-point of ''f,'' that is, ''a'' point that is close to an actual fixed point.

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{Cite web |title=APPLICATIONS AND EXTENSIONS OF AN ALGORITHM THAT COMPUTES FIXED POINTS OFCERTAIN UPPER SEMI-CONTINUOUS POINT TO SET MAPPINGS - ProQuest |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''.

* 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.

* B. Curtis Eaves<ref>{{Cite journal |last=Eaves |first=B. Curtis |date=1972-12-01 |title=Homotopies for computation of fixed points |url=https://doi.org/10.1007/BF01584975 |journal=Mathematical Programming |language=en |volume=3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |issn=1436-4646}}</ref> 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<ref name=":1" /> surveys various algorithms developed until 1976.

* 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''.

* [[David Gale]]<ref>{{cite journal |author=David 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 an ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of an ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

* 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.

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

* A book by Michael Todd<ref name=":1" /> surveys various algorithms developed until 1976.

** Compute the difference ''f''(''z''/''k'')-''z''/''k''; note that the difference is an ''n''-vector.

* [[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|ε}}''

** Label the vertex ''z'' by a label in 1,...,''d'', denoting the largest coordinate in the difference vector.

** 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]]