Fixed-point computation: Difference between revisions

Revision as of 12:14, 16 April 2023

Revision as of 12:18, 16 April 2023

Line 1:

'''Fixed-point computation''' refers to the process of computing an exact or approximate [[Fixed point (mathematics)|fixed point]] of a given function.<ref name=":1">{{cite journalbook |doi=10.1007/978-3-642-50327-6 |title=The Computation of Fixed Points and Applications |series=Lecture Notes in Economics and Mathematical Systems |year=1976 |volume=124 |isbn=978-3-540-07685-8 }}{{pn}}</ref> In its most common form, we are given a function ''f'' that satisfies the condition to the [[Brouwer fixed-point theorem]], that is: ''f'' is continuous and maps the unit [[N-cube|''d''-cube]] to itself. The [[Brouwer fixed-point theorem]] guarantees that ''f'' has a fixed point, but the proof is not constructive. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in economics for computing a [[market equilibrium]], in game theory for computing a [[Nash equilibrium]], and in [[dynamic system]] analysis.

== Definitions ==

Line 24:

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.

Shellman and Sikorski<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 }}</ref> presented an algorithm called BEFix (Bisection Envelope Fixed-point) for computing an {{mvar|ε}}-residual fixed-point of a two-dimensional function with ''L ≤'' 1, using only <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> queries. They later<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</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 ''L ≤'' 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can be executed 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. It is more efficient than the iteration algorithm when ''L'' is close to 1. The algorithm is recursive: it handles a ''d''-dimensional function by recursive calls on (''d''-1)-dimensional functions.

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 |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.

* [[David Gale]]<ref>{{cite journal |first1=David |last1=Gale |year=1979 |title=The Game of Hex and Brouwer Fixed-Point Theorem |journal=The American Mathematical Monthly |volume=86 |issue=10 |pages=818–827 |doi=10.2307/2320146 |jstor=2320146 }}</ref> showed that computing a fixed point of an ''n''-dimensional function (on the unit ''d''-dimensional cube) is equivalent to deciding who is the winner in an ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of an ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

** Construct a Hex board of size ''kd'', where ''k''>1/''{{mvar|ε}}''. Each vertex ''z'' corresponds to a point ''z''/''k'' in the unit ''n''-cube.

Line 55:

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

Hirsch, [[Christos Papadimitriou|Papadimitriou]] and Vavasis proved that<ref name=":0">{{cite journal |last1=Hirsch |first1=Michael D |last2=Papadimitriou |first2=Christos H |last3=Vavasis |first3=Stephen A |title=Exponential lower bounds for finding Brouwer fix points |journal=Journal of Complexity |date=December 1989 |volume=5 |issue=4 |pages=379–416 |doi=10.1016/0885-064X(89)90017-4 |s2cid=1727254 }}</ref> ''any'' algorithm based on function evaluations, that finds an {{mvar|ε}}-residual fixed-point of ''f,'' requires <math>\Omega(L'/\varepsilon)</math> function evaluations, where <math>L'</math> is the Lipschitz constant of the function <math>f(x)-x</math> (note that <math>L-1 \leq L' \leq L+1</math>). More precisely:

* For a 2-dimensional function (''d''=2), they prove a tight bound <math>\Theta(L'/\varepsilon)</math>.

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 |lastlast1=Chen |firstfirst1=Xi |last2=Deng |first2=Xiaotie |date=2009-10-17 |title=On the complexity of 2D discrete fixed point problem |url=https://www.sciencedirect.com/science/article/pii/S030439750900499X |journal=Theoretical Computer Science |series=Automata, Languages and Programming (ICALP 2006) |language=en |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |s2cid=2831759 |issn=0304-3975}}</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 74:

Fixed-point computation is a special case of root-finding: given a function ''f'' on ''E^d'', define <math>g(x) := |f(x)-x|</math>. 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''. Therefore, any [[root-finding algorithm]] (an algorithm that computes an approximate root of a function) can be used to find an approximate fixed-point.

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 journal |lastlast1=Chen |firstfirst1=Xi |last2=Deng |first2=Xiaotie |date=2005-05-22 |title=On algorithms for discrete and approximate brouwer fixed points |url=https://doi.org/10.1145/1060590.1060638 |journal=Proceedings of the thirtyThirty-seventh annualAnnual ACM symposiumSymposium on Theory of computingComputing |series=STOC '05 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=323–330 |doi=10.1145/1060590.1060638 |isbn=978-1-58113-960-0|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 ==

Roughgarden and Weinstein<ref>{{Cite journal |lastlast1=Roughgarden |firstfirst1=Tim |last2=Weinstein |first2=Omri |date=2016-10-01 |title=On the Communication Complexity of Approximate Fixed Points |url=https://ieeexplore.ieee.org/document/7782935 |journal=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |pages=229–238 |doi=10.1109/FOCS.2016.32|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>.

== References ==