Fixed-point computation: Difference between revisions

Revision as of 11:22, 16 April 2023

Revision as of 11:25, 16 April 2023

Line 34:

== General functions ==

For functions with Lipschitz constant ''L''>1, computing a fixed-point is much harder.

Shellman and Sikorski<ref name=":3" /> proved that, for d≥2 and any ''L''>1, finding a δ-absolute fixed-point 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''.

=== One dimension ===

Line 41 ⟶ 39:

=== 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≥2 and any ''L''>1, finding a δ-absolute fixed-point 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''.

For functions in two or more dimensions, the problem is much more challenging. Several algorithms based on function evaluations have been developed.

Several algorithms based on function evaluations have been developed for finding an {{mvar|ε}}-residual fixed-point

* The first algorithm to approximate a fixed point of a general function was developed by [[Herbert Scarf]] in 1967.<ref>{{Cite journal |last=Scarf |first=Herbert |date=1967-09-01 |title=The Approximation of Fixed Points of a Continuous Mapping |url=http://epubs.siam.org/doi/10.1137/0115116 |journal=SIAM Journal on Applied Mathematics |language=en |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 |issn=0036-1399}}</ref><ref>H. Scarf found the first algorithmic proof: {{SpringerEOM|title=Brouwer theorem|first=M.I.|last=Voitsekhovskii|isbn=1-4020-0609-8}}.</ref> Scarf's algorithm finds an approximate{{mvar|ε}}-residual fixed -point by finding a fully-labelled "primitive set", in a construction similar to [[Sperner's lemma]]. A subtle aspect of Scarf's algorithm is that it finds an {{mvar|ε}}-residual fixed-point of ''f'', that is, a point that is {{em|almost fixed}} by a function ''f'', but in general cannot find a δ-absolute fixed-point of ''f,'' that is, ''a'' point that is close to an actual fixed point.

* A later algorithm by [[Harold W. Kuhn|Harold Kuhn]]<ref>{{Cite journal |last=Kuhn |first=Harold W. |date=1968 |title=Simplicial Approximation of Fixed Points |url=https://www.jstor.org/stable/58762 |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=61 |issue=4 |pages=1238–1242 |issn=0027-8424}}</ref> used simplices and simplicial partitions instead of primitive sets.

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{Cite web |title=APPLICATIONS AND EXTENSIONS OF AN ALGORITHM THAT COMPUTES FIXED POINTS OFCERTAIN UPPER SEMI-CONTINUOUS POINT TO SET MAPPINGS - ProQuest |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1?pq-origsite=gscholar&cbl=18750&diss=y |access-date=2023-04-13 |website=www.proquest.com |language=en}}</ref> presented the ''restart algorithm''.

Line 53:

** The resulting labeling corresponds to a possible play of the ''d''-dimensional Hex game among ''d'' players. This game must have a winner, and Gale presents an algorithm for constructing the winning path.

** In the winning path, there must be a point in which ''f_i''(''z''/''k'')-''z''/''k'' is positive, and an adjacent point in which ''f_i''(''z''/''k'')-''z''/''k'' is negative. This means that there is a fixed point of f between these two points.

In the worst case, the number of function evaluations required by all these algorithms is exponential in the binary representation of the accuracy, that is, in <math>\Omega(1/\varepsilon)</math>.

=== Two or more dimensions: query complexity ===