Fixed-point computation: Difference between revisions

Revision as of 12:40, 16 April 2023

Revision as of 12:43, 16 April 2023

Line 43:

* The first algorithm to approximate a fixed point of a general function was developed by [[Herbert Scarf]] in 1967.<ref>{{cite journal |last1=Scarf |first1=Herbert |title=The Approximation of Fixed Points of a Continuous Mapping |journal=SIAM Journal on Applied Mathematics |date=September 1967 |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 }}</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 {{mvar|ε}}-residual fixed-point by finding a fully-labelled "primitive set", in a construction similar to [[Sperner's lemma]].

* 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 |jstor=58762 |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=61 |issue=4 |pages=1238–1242 |doi=10.1073/pnas.61.4.1238 |pmid=16591723 |pmc=225246 |doi-access=free }}</ref> used simplices and simplicial partitions instead of primitive sets.

* Developing the simplicial approach further, Orin Harrison Merrill<ref>{{cite thesis |last1=MERRILL |first1=ORIN HARRISON |date=1972 |title=APPLICATIONS AND EXTENSIONS OF AN ALGORITHM THAT COMPUTES FIXED POINTS OFCERTAIN UPPER SEMI-CONTINUOUS POINT TO SET MAPPINGS |url=https://www.proquest.com/openview/9bd010ff744833cb3a23ef521046adcb/1 }}</ref> presented the ''restart algorithm''.

* B. Curtis Eaves<ref>{{cite journal |last1=Eaves |first1=B. Curtis |title=Homotopies for computation of fixed points |journal=Mathematical Programming |date=December 1972 |volume=3-3 |issue=1 |pages=1–22 |doi=10.1007/BF01584975 |s2cid=39504380 }}</ref> presented the ''[[homotopy]] algorithm''. The algorithm works by starting with an affine function that approximates ''f'', and deforming it towards ''f'', while following the fixed point''.'' A book by Michael Todd<ref name=":1" /> surveys various algorithms developed until 1976.

Line 67:

Let ''f'' be a direction-preserving function from the integer cube {1,...,''n''}^''d'' to itself. Chen and Deng<ref name=":2" /> prove that, for any ''d'' ≥ 2 and ''n'' > 48 ''d'', computing such a fixed point requires <math>\Theta(n^{d-1})</math> function evaluations.

Chen and Deng<ref>{{cite journal |last1=Chen |first1=Xi |last2=Deng |first2=Xiaotie |title=On the complexity of 2D discrete fixed point problem |journal=Theoretical Computer Science |date=October 2009 |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 }}</ref> define a different discrete-fixed-point problem, which they call 2D-BROUWER. It considers a discrete function ''f'' on {0,...,''n''}''²'' such that, for every ''x'' on the grid, ''f''(''x'')-''x'' is either (0,1) or (1,0) or (-1,-1). The goal is to find a square in the grid, in which all three labels occur. The function ''f'' must map the square {0,...,''n''}^''2'' to itself, so it must map the lines ''x''=0 and ''y''=0 to either (0,1) or (1,0); the line ''x''=''n'' to either (-1,-1) or (0,1); and the line ''y''=''n'' to either (-1,-1) or (1,0). The problem can be reduced to 2D-SPERNER (computing a fully-labeled triangle in a triangulation satisfying the conditions to [[Sperner's lemma]]), and therefore it is [[PPAD-complete]]. This implies that computing an approximate fixed-point is PPAD-complete even for very simple functions.

== Relation between fixed-point computation and root-finding algorithms ==

Line 79:

== Communication complexity ==

Roughgarden and Weinstein<ref>{{cite journalbook |doi=10.1109/FOCS.2016.32 |chapter=On the Communication Complexity of Approximate Fixed Points |title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |year=2016 |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |pages=229–238 |isbn=978-1-5090-3933-3 |s2cid=87553 }}</ref> studied the [[communication complexity]] of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function ''f'' and the other knows a function ''g''. Both functions are Lipschitz continuous and satisfy Brouwer's conditions. The goal is to compute an approximate fixed point of the [[composite function]] <math>g\circ f</math>. They show that the deterministic communication complexity is in <math>\Omega(2^d)</math>.

== Further reading ==

* Equilibria, fixed points, and complexity classes: a survey.<ref>{{cite journal |last1=Yannakakis |first1=Mihalis |title=Equilibria, fixed points, and complexity classes |journal=Computer Science Review |date=May 2009 |volume=3 |issue=2 |pages=71–85 |doi=10.1016/j.cosrev.2009.03.004 |url=https://drops.dagstuhl.de/opus/volltexte/2008/1311/ }}</ref>

== References ==