Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees

Abstract

We study the computational difficulty of the problem of finding fixed points of nonexpansive mappings in uniformly convex Banach spaces. We show that the fixed point sets of computable nonexpansive self-maps of a nonempty, computably weakly closed, convex and bounded subset of a computable real Hilbert space are precisely the nonempty, co-r.e. weakly closed, convex subsets of the domain. A uniform version of this result allows us to determine the Weihrauch degree of the Browder-Goehde-Kirk theorem in computable real Hilbert space: it is equivalent to a closed choice principle, which receives as input a closed, convex and bounded set via negative information in the weak topology and outputs a point in the set, represented in the strong topology. While in finite dimensional uniformly convex Banach spaces, computable nonexpansive mappings always have computable fixed points, on the unit ball in infinite-dimensional separable Hilbert space the Browder-Goehde-Kirk theorem becomes Weihrauch-equivalent to the limit operator, and on the Hilbert cube it is equivalent to Weak Koenig's Lemma. In particular, computable nonexpansive mappings may not have any computable fixed points in infinite dimension. We also study the computational difficulty of the problem of finding rates of convergence for a large class of fixed point iterations, which generalise both Halpern- and Mann-iterations, and prove that the problem of finding rates of convergence already on the unit interval is equivalent to the limit operator.

arXiv comment44 pages

References in corpus (8)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Local stability of ergodic averages
• Complexity Theory for Operators in Analysis
• Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
• Norm convergence of multiple ergodic averages for commuting transformations
• Connected Choice and the Brouwer Fixed Point Theorem
• Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability

Cited by in corpus (15)

• Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
• Finite choice, convex choice and finding roots
• Connected Choice and the Brouwer Fixed Point Theorem
• Rates of convergence for iterative solutions of equations involving set-valued accretive operators
• Abstract strongly convergent variants of the proximal point algorithm
• The descriptive theory of represented spaces
• Generalized Fejér monotone sequences and their finitary content
• How constructive is constructing measures?
• Decision problems for linear recurrences involving arbitrary real numbers
• Projection operators in the Weihrauch lattice
• Quantitative analysis of a subgradient-type method for equilibrium problems
• Convex choice, finite choice and sorting
• Quantitative Strong Convergence for the Hybrid Steepest Descent Method
• Nonstandard Convergence Gives Bounds on Jumps
• Computability in Basic Quantum Mechanics