|
The unit interval is denoted by ''E'' := [0,1], and the unit [[N-cube|''d''-dimensional cube]] is denoted by ''E<sup>d</sup>''. A [[continuous function]] ''f'' is defined on ''E<sup>d</sup>'' (from ''E<sup>d</sup>'' to itself)''.'' Often, it is assumed that ''f'' is not only continuous but also [[Lipschitz continuous]], that is, for some constant ''L'', <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> for all ''x,y'' in ''E<sup>d</sup>''.
A '''fixed point''' of ''f'' is a point ''x'' in ''E<sup>d</sup>'' such that ''f''(''x'')=''x''. By the [[Brouwer fixed-point theorem]], any contiuous function from ''E<sup>d</sup>'' 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=0885-064X}}</ref>
* The '''residual criterion''': given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-residual fixed-point of''' '''''f''''' is a point ''x'' in ''E<sup>d</sup>'' such that <math>|f(x)-x|\leq \varepsilon</math>, where here ''|.|'' denotes the [[maximum norm]]. That is, all ''d'' coordinates of the difference <math>f(x)-x</math> should be at most {{mvar|ε}}.<ref name=":0" />{{Rp|page=4}}
A Lipschitz-continuous function with constant ''L'' is called [[Contractive|'''contractive''']] if ''L''<1; it is called [[Weakly-contractive|'''weakly-contractive''']] if ''L≤''1.Every contractive function satisfying Brouwer's condisions 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 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">{{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=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 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, and ''L ≤'' 1, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).<ref>{{Citecite journal |lastlast1=Huang |firstfirst1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |date=1999-06-01 |title=Approximating Fixed Points of Weakly Contracting Mappings |url=https://www.sciencedirect.com/science/article/pii/S0885064X99905046 |journal=Journal of Complexity |languagedate=enJune 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 |issn=0885-064X}}</ref> It finds an {{mvar|ε}}-residual fixed-point is using <math>O(d\cdot \log(1/\varepsilon)) </math> evaluations. When ''L''<1, it finds a ''δ''-absolute fixed point using <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> evaluations.
Shellman and Sikorski<ref>{{Citecite journal |lastlast1=Shellman |firstfirst1=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 |languagedate=enJune 2002 |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>{{Citecite journal |lastlast1=Shellman |firstfirst1=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 |date=September 2003 |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 ''f'' is differentiable, and the algorithm can evaluate its derivative (not only ''f'' 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 ==
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 "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 |issn=0027-8424}}</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=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''.
* 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 |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.
* [[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 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|ε}}''
** 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.
** Compute the difference ''f''(''z''/''k'')-''z''/''k''; note that the difference is an ''n''-vector.
=== Two or more dimensions: query 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 |issn=0885-064X}}</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>.
Fixed-point computation is a special case of root-finding: given a function ''f'' on ''E<sup>d</sup>'', define <math>g(x) := |f(x)-x|</math>. Clearly, ''x'' is a fixed-point of ''f'' if and only if ''x'' is a root of ''g'', and ''x'' is an {{mvar|ε}}-residual fixed-point of ''f'' if and only if ''x'' is an {{mvar|ε}}-root of ''g''. Therefore, any [[root-finding algorithm]] (an algorithm that computes an approximate root of a function) can be used to find an approximate fixed-point.
The opposite is not true: finding an approximate root of a general function may be harder than finding an approximate fixed point. In particular, Sikorski<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 |issn=0945-3245}}</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 ''g'' that is slightly larger than {{mvar|ε}} everywhere in ''E<sup>d</sup>'' except in some small cube around some point ''x''<sub>0</sub>, where ''x''<sub>0</sub> is the unique root of ''g''. If ''g'' is [[Lipschitz continuous]] with constant ''L'', then the cube around ''x''<sub>0</sub> can have a side-length of {{mvar|ε}}/''L''. Any algorithm that finds an {{mvar|ε}}-root of ''g'' must check a set of cubes that covers the entire ''E<sup>d</sup>''; 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">{{Cite journal |last=Chen |first=Xi |last2=Deng |first2=Xiaotie |date=2005-05-22 |title=On algorithms for discrete and approximate brouwer fixed points |url=https://doi.org/10.1145/1060590.1060638 |journal=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |series=STOC '05 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=323–330 |doi=10.1145/1060590.1060638 |isbn=978-1-58113-960-0}}</ref> is the class of functions ''g'' such that <math>g(x)+x</math> maps ''E<sup>d</sup>'' to itself (that is: ''g''(x)+x is in ''E<sup>d</sup>'' for all x in ''E<sup>d</sup>''). This is because, for every such function, the function <math>f(x) := g(x)+x</math> satisfies the conditions to Brouwer's fixed-point theorem. Clearly, ''x'' is a fixed-point of ''f'' if and only if ''x'' is a root of ''g'', and ''x'' is an {{mvar|ε}}-residual fixed-point of ''f'' if and only if ''x'' is an {{mvar|ε}}-root of ''g''. 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.
| 