On the convergence rate of the Halpern-iteration
Felix Lieder
Abstract
Abstract In this work, we give a tight estimate of the rate of convergence for the Halpern-iteration for approximating a fixed point of a nonexpansive mapping in a Hilbert space. Specifically, using semidefinite programming and duality we prove that the norm of the residuals is upper bounded by the distance of the initial iterate to the closest fixed point divided by the number of iterations plus one.
Topics & Concepts
MathematicsHilbert spaceRate of convergenceDuality (order theory)Bounded functionFixed pointNorm (philosophy)Convergence (economics)Semidefinite programmingApplied mathematicsComputational intelligenceFixed-point iterationCombinatoricsDiscrete mathematicsMathematical optimizationPure mathematicsMathematical analysisComputer scienceEconomicsChannel (broadcasting)Machine learningPolitical scienceEconomic growthComputer networkLawOptimization and Variational AnalysisAdvanced Optimization Algorithms ResearchSparse and Compressive Sensing Techniques