Fixed-point computation: Difference between revisions

Revision as of 09:52, 16 April 2023

Revision as of 10:15, 16 April 2023

Line 9:

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

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

The function ''f'' is accessible via '''evaluation''' queries: for any ''x'', the algorithm can evaluate ''f''(''x''). 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 ''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 requiredfor to compute ana ''{{mvar|ε}}δ''-absolute fixed point is in <math>O(\log_L(\varepsilondelta) = \log(\varepsilondelta)/\log(L) = \log(1/\varepsilondelta)/\log(1/L)) </math>. ThisBanach'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 ''d''=1, the [[bisection method]] can be used, and it is optimal for various error criteria.<ref name=":4" />

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 to compute an ''{{mvar|ε}}''-absolute fixed point is in <math>O(\log_L(\varepsilon) = \log(\varepsilon)/\log(L) = \log(1/\varepsilon)/\log(1/L)) </math>. This 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>{{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 The''d''>1 but not too large, and ''L''=1, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[Ellipsoid method|ellipsoid algorithmmethod]]).<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.

a fixed point of a contraction mapping can be found much faster than in the general case. Some algorithms for this case are:

*

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