|
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>{{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>
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.
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 δ-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 Lipschitz constant ''L ≤''= 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can alsobe computeexecuted 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. (thatIt is more efficient than the iteration algorithm when ''L'' is close to 1. The algorithm is recursive: it handles a similar''d''-dimensional complexityfunction butby withrecursive <math>\varepsiloncalls =on (''d''-1)-L)\cdotdimensional \delta</math>)functions.
=== Algorithms for differentiable functions ===
=== Two or more dimensions: algorithms ===
For functions in two or more dimensions, the problem is much more challenging. Shellman and Sikorski<ref name=":3" /> proved that, for d≥2any andintegers any''d''≥2 and ''L''>1, finding a δ-absolute fixed-point of ''d''-dimensional ''L''-Lipschitz functions might require infinitely-many evaluations. The proof idea is as follows. For any integer ''T''>1, and for any sequence of ''T'' of evaluation queries (possibly adaptive), one can construct two functions that are Lipschitz-continuous with constant ''L'', and yield the same answer to all these queries, but one of them has a unique fixed-point at (''x'',0) and the other has a unique fixed-point at (''x'',1). Any algorithm using ''T'' evaluations cannot differentiate between these functions, so cannot find a δ-absolute fixed-point. This is true for any finite integer ''T''.
Several algorithms based on function evaluations have been developed for finding an {{mvar|ε}}-residual fixed-point
| 