Fixed-point computation: Difference between revisions

Revision as of 20:05, 20 June 2024

Revision as of 20:33, 22 June 2024

Line 5:

== 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^d''. A [[continuous function]] ''f'' is defined on ''E^d'' (from ''E^d'' to itself)''.'' Often, it is assumed that ''f'' is not only continuous but also [[Lipschitz continuous]], that is, for some constant ''L'', <math>|f(x)-f(y)| \leq L\cdot |x-y|</math> for all ''x,y'' in ''E^d''.

A '''fixed point''' of ''f'' is a point ''x'' in ''E^d'' such that ''f''(''x'') = ''x''. By the [[Brouwer fixed-point theorem]], any continuous function from ''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:<ref name=":3">{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A recursive algorithm for the infinity-norm fixed point problem |journal=Journal of Complexity |date=December 2003 |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |doi-access=free }}</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^d'' 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}}

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

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

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If ''f'' is Lipschitz-continuous with constant ''L'', 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 ''f'', 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>.

Line 28:

When ''d''>1 but not too large, and ''L ≤'' 1, 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 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>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 |doi-access=free }}</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 |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 '''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 ===

Line 46:

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>{{cite journal |last1=Scarf |first1=Herbert |title=The Approximation of Fixed Points of a Continuous Mapping |journal=SIAM Journal on Applied Mathematics |date=September 1967 |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 }}</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 |jstor=58762 |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=61 |issue=4 |pages=1238–1242 |doi=10.1073/pnas.61.4.1238 |pmid=16591723 |pmc=225246 |doi-access=free }}</ref> used simplices and simplicial partitions instead of primitive sets.

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{cite thesis |last1=Merrill |first1=Orin Harrison |date=1972 |title=Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-continuous Point to Set Mappings |id={{NAID|10006142329}} |oclc=570461463 |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1 }}</ref> presented the ''restart algorithm''.