Talk from Archives

Rates of convergence for the Krasnoselskii-Mann fixed point iteration

23.04.2018 16:45 - 17:45

We analyze the convergence of an inexact version of the classical Krasnoselskii-Mann iteration for computing fixed points of nonexpansive maps in Banach spaces. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. These recursive bounds are in turn interpreted as expected rewards for an underlying Markov chain, which leads to explicit rates of convergence. In the case of the exact iteration we show that these bounds are tight by building a nonexpansive map that attains them with equality, and we deduce that the optimal constant of asymptotic regularity is exactly $1/\sqrt{\pi}$. The results are extended to continuous time to study the asymptotics of non-autonomous evolution equations governed by nonexpansive operators.

Personal website of Roberto Cominetti

Location:
HS 7 OMP1 (#1.303)