Fixed-point computation: Difference between revisions

Revision as of 15:13, 14 April 2023

Revision as of 08:58, 16 April 2023

Line 1:

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

== Definitions ==

The unit interval is denoted by ''E'' := [0,1], 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''. 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 more common criteria are:<ref name=":3">{{Cite journal |last=Shellman |first=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 |language=en |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |issn=0885-064X}}</ref>

A '''fixed point''' of ''f'' is a point ''x'' in ''E^d'' such that ''f''(''x'')=''x''. Given an approximation parameter <math>\varepsilon>0</math> , An '''{{mvar|ε}}-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}}

A* '''fixedThe point'''residual of criterion''f'' is a point ''x'' in ''E^d'' such that ''f''(''x'')=''x''.: Givengiven 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}}

An alternative possible definition of an approximate fixed point uses an approximation parameter <math>\delta>0</math>. A '''δ-near 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'' (this criterion is also called the '''absolute criterion''').<ref name=":3">{{Cite journal |last=Shellman |first=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 |language=en |volume=19 |issue=6 |pages=799–834 |doi=10.1016/j.jco.2003.06.001 |issn=0885-064X}}</ref> Note that, 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 (L+1)\cdot \delta</math>. Therefore, a δ-near fixed-point is also an {{mvar|ε}}-fixed-point with <math>\varepsilon = (L+1)\cdot \delta</math>. {{Under construction|placedby=Erel Segal}}

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

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 (L+1)\cdot \delta</math>. Therefore, a δ-absolute fixed-point is also an {{mvar|ε}}-residual fixed-point with <math>\varepsilon = (L+1)\cdot \delta</math>. {{Under construction|placedby=Erel Segal}}

== Algorithms based on function evaluations ==

Line 12 ⟶ 15:

=== One dimension ===

For a 1-dimensional function (''d''=1), a δ-nearabsolute fixed-point can be found using <math>O(\log(1/\delta))</math> queries using the [[bisection method]]: start with the interval E := [0,1]; at each iteration, let ''x'' be the center of the current interval, and compute ''f''(''x''); if ''f''(''x'')>''x'' then recurse on the sub-interval to the right of ''x''; otherwise, recurse on the interval to the left of ''x''. 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 δ-nearabsolute fixed-point of ''f.'' Setting <math>\delta := \varepsilon/(L+1)</math>, where ''L'' 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. Several algorithms based on function evaluations have been developed.

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

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

Line 30 ⟶ 33:

=== Two or more dimensions: query complexity ===

Hirsch, [[Christos Papadimitriou|Papadimitriou]] and Vavasis proved that<ref name=":0">{{Cite journal |last=Hirsch |first=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 |language=en |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>.

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

== Algorithms for contraction mappings ==

A ''[[contraction mapping]]'' (also called a ''contractive Lipschitz function'') is a Lipschitz-continuous function with constant ''L''<1. When the Lipschitz constant is smaller than 1, a fixed point of a contraction mapping can be found much faster than in the general case. Some algorithms for this case are:

* The [[fixed-point iteration]] algorithm of Banach. The [[Banach fixed point theorem|Banach 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 accuracy ''{{mvar|ε}}'' is in <math>O(\log_L(\varepsilon) = \log(\varepsilon)/\log(L) = \log(1/\varepsilon)/\log(1/L)) </math>.

* 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]].<ref>{{Cite journal |last=Huang |first=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 |language=en |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 |issn=0885-064X}}</ref>

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

* 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 δ-nearabsolute 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 Lipschitz constant ''L''=1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can also compute a δ-nearabsolute 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 δ-nearabsolute fixed-point might require infinitely-many evaluation queries.

== Discrete fixed-point computation ==

Line 56 ⟶ 60:

Given a function ''g'' from ''E^d'' to ''R'', a '''root''' of ''g'' is a point ''x'' in ''E^d'' such that ''g''(''x'')=0. An '''{{mvar|ε}}-root''' of g is a point ''x'' in ''E^d'' such that <math>g(x)\leq \varepsilon</math>.

Fixed-point computation is a special case of root-finding: given a function ''f'' on ''E^d'', 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>{{Cite journal |last=Sikorski |first=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 |language=en |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^d'' except in some small cube around some point ''x''₀, where ''x''₀ is the unique root of ''g''. If ''g'' is [[Lipschitz continuous]] with constant ''L'', then the cube around ''x''₀ 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^d''; 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^d'' to itself (that is: ''g''(x)+x is in ''E^d'' for all x in ''E^d''). 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.

== Communication complexity ==