47
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ I spent half a back-packing trip meditating on this question while hiking, only to give up. Thanks for asking. $\endgroup$
    – Joseph Victor
    Commented Aug 30, 2012 at 2:10
  • 1
    $\begingroup$ I am not an expert, but I am vaguely aware of work (the name Papadopoulos comes to mind) relating to the complexity of applying Brouwer, which is necessary in the existence of Nash equilibria, to other computationally complex problems. So part of the answer is that you should expect that any approach is not fast. Brouwer-completeness should be understood analogously to (it is different from) NP-completeness. $\endgroup$
    – Theo Johnson-Freyd
    Commented Aug 30, 2012 at 15:42
  • 2
    $\begingroup$ Theo, you were definitely on the right track here, except I suspect that the name coming to mind was "Papadimitriou". On a somewhat tangential note, Googling "Papadopoulos math" brings up at least 6 seemingly distinct Papadopouloses, none of whom seem to have worked on Brouwer fixed points :) $\endgroup$
    – Vidit Nanda
    Commented Aug 31, 2012 at 19:15

6 Answers 6

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ The paper is in J. Complexity 5 (1989), no. 4, 379--416. It shows that any algorithm based on function evaluations has a worst-case complexity that is exponential in both the number of digits of accuracy and the dimension of the ambient Euclidean space. $\endgroup$
    – Moe Hirsch
    Commented Sep 7, 2012 at 18:50
  • $\begingroup$ The article only adresses the case of Lipschitz maps, One may argue that the strength of the Brouwer fixed point theorem is the fact that it applies to all continuous maps. $\endgroup$
    – coudy
    Commented Nov 13, 2023 at 15:33
18
$\begingroup$

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)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Dear Johannes, thank you for the answer. I am aware of the Sperner lemma, but was under the impression that using it would require me to triangulate the domain and simplicially approximate my function, which appears computationally intractable. $\endgroup$
    – Vidit Nanda
    Commented Aug 29, 2012 at 21:46
  • 5
    $\begingroup$ But that gives you an "almost fixed point", it doesn' ensure that that point is close to an actual fixed point. $\endgroup$
    – Michael Greinecker
    Commented Aug 30, 2012 at 6:38
  • 4
    $\begingroup$ FYI, Nikolai Ivanov has a proof that the Sperner Lemma proof is essentially the Brouwer proof done at the co-chain level. arxiv.org/abs/0906.5193 $\endgroup$
    – Ryan Budney
    Commented Aug 30, 2012 at 7:18
12
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ That actually looks like a 1-dimensional version of Sperner. But yes, if all you can do is compute any $f(x)$ to within any given $\delta$ then already in one dimension you can't guarantee an $\epsilon$-approximation of the fixed point because $f$ might be very close to the identity function. You can, however, find an $\epsilon$-approximation to a solution of $d(x,f(x)) < \delta$. $\endgroup$
    – Noam D. Elkies
    Commented Aug 29, 2012 at 23:39
  • $\begingroup$ I thought up an argument that uses explicit $\epsilon$s and $\delta$s to continually subdivide the ball and converge to the fixed points, but it's probably just a higher-dimensional version of Sperner, and if not it certainly involves computing a simplicial approximation to at least part of the function. $\endgroup$
    – Will Sawin
    Commented Aug 30, 2012 at 0:32
  • 1
    $\begingroup$ Will, I also can't see how to avoid some sort of approximation using such a scheme as you suggest. I even thought about intersecting the disk with a cubical grid, evaluating at the vertices, and refining dyadically, but of course as you said: I will still miss fixed points no matter what. $\endgroup$
    – Vidit Nanda
    Commented Aug 30, 2012 at 1:59
  • 3
    $\begingroup$ If I even try to define the function here, they will revoke my mathoverflow license for taking "too localized" to stratospheric heights. $\endgroup$
    – Vidit Nanda
    Commented Aug 30, 2012 at 2:50
  • 2
    $\begingroup$ I'm just saying if you knew some niceness condition stronger than continuity, you might have a chance. Also: If you think Bolzano-Weierstrauss is constructive, you can, as Noam Elkies point out, find an $\epsilon$-approximation to a solution of $d(x,f(x))<\delta$, then let $\epsilon$ and $\delta$ go to $0$ and take the limit of a convergent subsequence. But clearly that's not practical. $\endgroup$
    – Will Sawin
    Commented Aug 30, 2012 at 3:22
9
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Aaron, thank you for the reference. I am not sure if it answers the question yet, but I will read it carefully soon. $\endgroup$
    – Vidit Nanda
    Commented Aug 30, 2012 at 2:00
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Quinn, thank you for the reference. They stress the non-constructiveness in great style: "Brouwer is known as one of the founders of intuitionism, which is one of the well-studied varieties of constructive mathematics and ironically, the theorem that he is best known for does not admit any constructive proof." $\endgroup$
    – Vidit Nanda
    Commented Aug 31, 2012 at 2:14
  • 2
    $\begingroup$ On a more disturbing note, how does one reconcile that non-constructiveness assertion with the paper mentioned in Aaron's answer?? $\endgroup$
    – Vidit Nanda
    Commented Aug 31, 2012 at 2:20
  • 3
    $\begingroup$ @Vel: (a) there are many different notions of constructivism. See, e.g. plato.stanford.edu/entries/mathematics-constructive/#3 The paper linked in the answer seems to equate constructive with some notion of computable (see the comments after the assertion that Brouwer FPT is non-constructive). (b) The paper of Kellog, Li, and Yorke in Aaron's answer makes an assumption that the function is $C^2$; presumably this would also make a difference. (Think Newton's method for root finding versus trying to find the root guaranteed by IVT of a merely continuous function.) $\endgroup$
    – Willie Wong
    Commented Aug 31, 2012 at 11:50
  • $\begingroup$ The argument in my answer works for $C^2$ functions, as long as the only query allowed is computing the value and first and second derivative at a point. So you need to either accept a method that only works after infinite time and gives you no certainty of approximation after finite time, as in Willie Wong's answer and Noam Elkies' comment, or accept a stronger query, such as in the Sperner's Lemma argument. $\endgroup$
    – Will Sawin
    Commented Aug 31, 2012 at 15:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .