Fixed-point computation: Difference between revisions

Revision as of 12:37, 16 April 2023

Revision as of 12:40, 16 April 2023

Line 20:

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">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=Complexity of fixed points, I |journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 }}</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 book |last1=Sikorski |first1=Krzysztof A. |title=Optimal Solution of Nonlinear Equations |date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{pn}}</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>{{cite journalbook |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=Robustness in Identification and Control |year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</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>{{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 }}</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.

Line 76:

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 |last1=Sikorski |first1=K. |title=Optimal solution of nonlinear equations satisfying a Lipschitz condition |journal=Numerische Mathematik |date=June 1984 |volume=43 |issue=2 |pages=225–240 |doi=10.1007/BF01390124 |s2cid=120937024 }}</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 journalbook |doi=10.1145/1060590.1060638 |chapter=On algorithms for discrete and approximate brouwer fixed points |title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |year=2005 |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |pages=323–330 |isbn=1581139608 |s2cid=16942881 }}</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 ==