Can we actually find any fixed points with Brouwer's theorem? - MathOverflow

Can we actually find any fixed points with Brouwer's theorem?

2012-08-29T21:39:32Z

Background

At the risk of greatly oversimplifying matters, let me state a heuristic from Granas and Dugundji's beautiful book: fixed point theorems fall into two broad categories. The first class is usually functional analytic and imposes strong conditions on the map $f:X \to X$ whereas the second class is usually algebraic topological and imposes strong conditions on the space $X$ itself.

A typical example of the first class of theorems is the fixed point theorem of Banach. While the spaces it applies to are fairly general (complete metric spaces), the function must have a Lipschitz constant strictly less than $1$. On the other hand, Brouwer's theorem falls into the second class. Any continuous map works, but the domain must be a compact and convex subset of Euclidean space (originally a disk). Of course, both these theorems have been vastly generalized from the versions that I am stating here.

Question

One fundamental advantage of the Banach theorem is that it actually provides a recipe for converging to the fixed point as part of the standard proof: just start at an initial point and iterate. The proofs of the Brouwer theorem that I have seen do no such thing. The best known proof (I think) is the one by contradiction: assuming the domain is a disk, if $f(x)$ and $x$ are always distinct then the ray from $f(x)$ through $x$ to the boundary of said disk provides a deformation-retraction from the disk to its boundary, aha!

Here is my question:

Is there any way to actually find a fixed point when using Brouwer's theorem?

A Possible Idea

One scheme that unfortunately fails is as follows. Consider the sequence of iterates $f^n(x)$ for $n \in \mathbb{N}$ and any initial $x$ in the domain. We have an infinite sequence in a compact set, and hence a convergent subsequence, so the limit point is a candidate. This won't work since a) we haven't used convexity at all, and b) one may just be converging to a periodic orbit of $f$.

Sorry if this is too half-baked or elementary, but I have reduced an annoying problem to finding (any!!) fixed point of a map on the unit disk in $\mathbb{R}^n$. But this infernal map is absolutely hideous and in no way satisfies the hypotheses for the Banach fixed point theorem, so I have to use Brouwer's theorem. There is also no Earthly hope of discretizing the domain and approximating this monstrosity by a simplicial map. If the question sounds desperate, that's because it is... All help is greatly appreciated.

Update

Thanks to all the answerers and commenters for various helpful and constructive suggestions. If either of the articles referenced by Aaron or Willie turn out to contain directly useful information, I will write a brief summary of the relevant content here.

Answer by Johannes Hahn for Can we actually find any fixed points with Brouwer's theorem?

2012-08-29T21:43:30Z

There is a constructive version of Brouwer's theorem via Sperner's theorem. This gives an actual way to compute fixed points. (Not a very efficient one, granted, but an algorithm nonetheless)

Answer by Aaron Meyerowitz for Can we actually find any fixed points with Brouwer's theorem?

2012-08-29T22:54:25Z

There are other constructive proofs Here is an article with a method which , according to the authors, does not require a simplicial decomposition,is similar to Newton's method, and has been applied up to dimension $60$.

Answer by Will Sawin for Can we actually find any fixed points with Brouwer's theorem?

2012-08-29T22:54:33Z

This is perhaps silly, but the obvious algorithm for $\mathbb R^1$ is to compute $f(1/2)$. If it's larger than $1/2$, compute $f(3/4)$. If it's smaller, compute $f(1/4)$. Keep going dyadically and you will compute the binary digits of a fixed point to an arbitrary level of accuracy. But it's very unclear how to generalize this.

If all we can do is sample the function at finitely many points, it should be impossible to guess the location of a fixed point with any degree of accuracy. To see this, take a function with a single fixed point, like $f(x)=.99x$. Take a long but very thin tube containing that point and another point, and change the function on the tube so that the other point is now the fixed point.

Since the measure of the tube can be made arbitrarily small, and the tube can be chosen to avoid any finite set, any strategy for sampling finitely many points will, with high probability, be unable to distinguish the function from $.99x$ and so will be unable to guess the location of the fixed point.

Thus, you need some way to show the function is not malevolent, like some understanding of the $\epsilon$s and $\delta$s in the function's uniform continuity, or maybe a probabilistic model of a random function.

Answer by Willie Wong for Can we actually find any fixed points with Brouwer's theorem?

2012-08-30T07:31:48Z

(This answer is in a similar direction to that of Johannes Hahn's and to Will Sawin's)

I think (I am not 100% sure) that one may get away without doing the triangulation and simplicial approximation (of the "usual" Sperner's Lemma proof) if you take the approach using van Maaren's version of Sperner's Lemma (there is an outline of the proof in Schechter's Handbook of Analysis and its Foundations with some typos).

One first obtains the van Maaren's version of Sperner's Lemma, which is purely combinatorial/order theoretical and is a constructive statement on finite sets (the proof just gives the algorithm).

Using that one gets an approximate fixed point statement (roughly speaking for every $\epsilon$ you find a point that is $\epsilon$ away from being a fixed point). To get the approximate fixed point at size $1/k, k\in\mathbb{N}$ you only need to consider the finite subset formed by the lattice of spacing $1/(3kn)$ where $n$ is the dimension. In this step the convexity comes into play (but not continuity; compactness only enters via Heine-Borel as boundedness).

Note that this does not require being able to approximate the function $f$: it just requires being able to evaluate $f(x)$ for given $x$ to arbitrary accuracy (in particular you need to know whether the $i$-th coordinate of $f(x)$ is less than or equal to the $i$-th coordinate of $x$).

Then you take limit as $k\to \infty$ (and here continuity and compactness are used, by convexity is no longer relevant) (the practicality of this last step, of course, is questionable; and as Noam Elkies and Michael Greinecker alluded to, this method gives no rate of convergence, so cutting off the computation at a finite $k$ doesn't guarantee that you are near a bona fide fixed point at all).

Answer by Quinn Culver for Can we actually find any fixed points with Brouwer's theorem?

2012-08-31T01:36:03Z

Here's a paper worth checking out: http://arxiv.org/abs/1206.4809. It essentially shows that finding a fixed point of a continuous $f:[0,1]^{n} \to [0,1]^{n}$ is as hard as finding a point in a nonempty connected closed subset of $[0,1]^{n}$.

They also mention (after Theorem 1.1) that the Brouwer fixed point theorem is non-constructive.

Answer by Moe Hirsch for Can we actually find any fixed points with Brouwer's theorem?

2012-08-31T14:59:16Z

The paper "Exponential lower bounds for finding Brouwer fixed points"

Addendum by original poster: It was non-trivial to find a copy of this great paper of Hirsch, Papadimitriou and Vavasis. It does answer my general question quite clearly: finding Brouwer fixed points is exponentially hard in the worst case no matter what algorithm you use. Here is a link to this paper for all those who are interested and don't want to run into many, many pay-walls. I will take it down in a few days. -VN