Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 10:
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}}
== 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 [[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 δ-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 also compute a δ-absolute 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 δ-absolute fixed-point might require infinitely-many evaluation queries.▼
== Algorithms based on function evaluations ==
Line 39 ⟶ 55:
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>.
▲A ''[[contraction mapping]]'' 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 δ-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 also compute a δ-absolute 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 δ-absolute fixed-point might require infinitely-many evaluation queries.
== Discrete fixed-point computation ==
| |||