Fixed-point computation: Difference between revisions

Revision as of 05:58, 29 July 2024

Latest revision as of 11:38, 15 August 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Computing the fixed point of a function}}

{{CS1 config|mode=cs1}}

'''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 book |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 }}</ref> In its most common form, the given function <math>f</math> satisfies the condition to the [[Brouwer fixed-point theorem]]: that is:, <math>f</math> is continuous and maps the unit [[N-cube|''d''-cube]] to itself. The [[Brouwer fixed-point theorem]] guarantees that <math>f</math> has a fixed point, but the proof is not [[Constructive proof|constructive]]. Various algorithms have been devised for computing an approximate fixed point. Such algorithms are used in economicsvarious fortasks, computingsuch aas

* [[marketNash equilibrium computation]], in
* [[gameMarket theory]]equilibrium for computing a [[Nash equilibriumcomputation]], and in
* [[dynamicDynamic system]] analysis.

== Definitions ==

Line 15 ⟶ 19:

For Lipschitz-continuous functions, the absolute criterion is stronger than the residual criterion: If <math>f</math> is Lipschitz-continuous with constant <math>L</math>, 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 <math>f</math>, this implies <math>|f(x)-x_0|\leq L\cdot \delta</math>, so <math>|f(x)-x|\leq (1+L)\cdot \delta</math>. Therefore, a δ-absolute fixed-point is also an {{mvar|ε}}-residual fixed-point with <math>\varepsilon = (1+L)\cdot \delta</math>.

The most basic step of a fixed-point computation algorithm is a '''value query''': given any <math>x</math> in <math>E^d</math>, the{{Sentence fragment|date=Aprilalgorithm 2023is provided with an oracle <math>\tilde{f}</math> to <math>f</math> that returns the value <math>f(x)</math>. The accuracy of the approximate fixed-point depends upon the error in the oracle <math>\tilde{f}(x)</math>.

The function <math>f</math> is accessible via '''evaluation''' queries: for any <math>x</math>, the algorithm can evaluate <math>f(x)</math>. The run-time complexity of an algorithm is usually given by the number of required evaluations.

Line 49 ⟶ 53:

* 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 of Certain Upper Semi-continuous Point to Set Mappings |id={{NAID|10006142329}} |oclc=570461463 |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 ''[[homotopyHomotopy method]] algorithm''. The algorithm works by starting with an affine function that approximates <math>f</math>, and deforming it towards <math>f</math> 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 a ''d''-dimensional game of [[Hex (board game)|Hex]] (a game with ''d'' players, each of whom needs to connect two opposite faces of a ''d''-cube). Given the desired accuracy ''{{mvar|ε}}''

** Construct a Hex board of size ''kd'', where <math>k > 1/\varepsilon</math>. Each vertex ''z'' corresponds to a point ''z''/''k'' in the unit ''n''-cube.