Fixed-point computation: Difference between revisions

Revision as of 10:15, 16 April 2023

Revision as of 11:05, 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|''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 morein [[dynamic system]] analysis.

== 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''. By the [[Brouwer fixed-point theorem]], any contiuous 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. Two of the moreSeveral 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>

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

The most basic step of a fixed-point computation algorithm is a '''value query''': given any ''x'' in ''E^d'', the

Line 18 ⟶ 19:

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 ''δ''-absoluterelative fixed -point is inapproximately <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 ComplexitySikorski and Method Efficiency in Optimization, Wiley, New York, 1983.</ref>Wozniakowski<ref name=":45">{{Cite webjournal |last=Sikorski |first=K |last2=Woźniakowski |first2=H |date=20011987-12-01 |title=Optimal solutionComplexity of nonlinearfixed equationspoints, I |url=https://dlwww.acmsciencedirect.orgcom/doiscience/absarticle/10.5555pii/3704370885064X87900082 |access-datejournal=2023-04-16Journal of Complexity |websitelanguage=Guideen books|volume=3 |languageissue=EN4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 |issn=0885-064X}}</ref> Butshowed 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.

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, and ''L''=1, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).<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> 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.

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