Fixed-point computation
Fixed-point computation refers to the process of computing an exact or approximate fixed point of a given function.[1] 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 a convex set 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.
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. This template was placed by Erel Segal (talk · contribs). If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Erel Segal (talk | contribs) 2 years ago. (Update timer) |
Algorithms based on function evaluations
The first algorithm to approximate a fixed point was proposed by Herbert Scarf in 1967.[2][3] A subtle aspect of Scarf's algorithm is that it finds a point that is almost fixed by a function f, but in general cannot find a point that is close to an actual fixed point. In mathematical language, if ε is chosen to be very small, Scarf's algorithm can be used to find a point x such that f(x) is very close to x, i.e., . But Scarf's algorithm cannot be used to find a point x such that x is very close to a fixed point: we cannot guarantee where Often this latter condition is what is meant by the informal phrase "approximating a fixed point"[citation needed].
Other algorithms for computing a fixed point were developed by Kuhn (1968), Eaves (1972), Merrill (1972) and others.[4] A book by Michael Todd[1] surveys various algorithms developed until 1976. These algorithms are based on function evaluations: they receive as an input a black-box that, for any x, returns the value of f(x). In the worst case, the number of evaluations required by these algorithms is exponential. Hirsch, Papadimitriou and Vavasis proved that[4] any algorithm based on function evaluations, that finds a fixed point with p decimal digits, requires evaluations in the worst case. Equivalently, finding a point at a distance at most from a fixed point requires evaluations. This holds even when the function is two-dimensional (from the unit-disk to itself).
References
- ^ a b The Computation of Fixed Points and Applications. doi:10.1007/978-3-642-50327-6.
- ^ Scarf, Herbert (1967-09-01). "The Approximation of Fixed Points of a Continuous Mapping". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116. ISSN 0036-1399.
- ^ H. Scarf found the first algorithmic proof: Voitsekhovskii, M.I. (2001) [1994], "Brouwer theorem", Encyclopedia of Mathematics, EMS Press, ISBN 1-4020-0609-8.
- ^ a b Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (1989-12-01). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. ISSN 0885-064X.