Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal error bounds for nonexpansive fixed-point iterations in normed spaces
60
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps in normed spaces. We look for iterations that achieve the smallest fixed-point residual after $n$ steps, by minimizing a worst-case bound $|x^n-Tx^n|le R_n$ derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing $R_n$ yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate $R_n=O(1/n)$, which we also show to be the best possible. In particular, we prove that the classical Halpern iteration achieves this optimal rate for several alternative stepsizes, and we determine analytically the optimal stepsizes that attain the smallest worst-case residuals at every step $n$, with a tight bound $R_napproxfrac{4}{n+4}$. We also determine the optimal Halpern stepsizes for affine nonexpansive maps, for which we get exactly $R_n=frac{1}{n+1}$. Finally, we show that the best rate for the classical Krasnoselskiu{i}-Mann iteration is $Omega(1/sqrt{n})$, and we present numerical evidence suggesting that even after introducing inertial terms one cannot reach the faster rate $O(1/n)$.
rate research
Read More
We present a self-contained analysis of a particular family of metrics over the set of non-negative integers. We show that these metrics, which are defined through a nested sequence of optimal transport problems, provide tight estimates for general Krasnoselskii-Mann fixed point iterations for non-expansive maps. We also describe some of their very special properties, including their monotonicity and the so-called convex quadrangle inequality that yields a greedy algorithm to compute them efficiently.
We estimate convergence rates for fixed-point iterations of a class of nonlinear operators which are partially motivated from solving convex optimization problems. We introduce the notion of the generalized averaged nonexpansive (GAN) operator with a positive exponent, and provide a convergence rate analysis of the fixed-point iteration of the GAN operator. The proposed generalized averaged nonexpansiveness is weaker than the averaged nonexpansiveness while stronger than nonexpansiveness. We show that the fixed-point iteration of a GAN operator with a positive exponent converges to its fixed-point and estimate the local convergence rate (the convergence rate in terms of the distance between consecutive iterates) according to the range of the exponent. We prove that the fixed-point iteration of a GAN operator with a positive exponent strictly smaller than 1 can achieve an exponential global convergence rate (the convergence rate in terms of the distance between an iterate and the solution). Furthermore, we establish the global convergence rate of the fixed-point iteration of a GAN operator, depending on both the exponent of generalized averaged nonexpansiveness and the exponent of the H$ddot{text{o}}$lder regularity, if the GAN operator is also H$ddot{text{o}}$lder regular. We then apply the established theory to three types of convex optimization problems that appear often in data science to design fixed-point iterative algorithms for solving these optimization problems and to analyze their convergence properties.
In this paper, we first introduce an iterative process in modular function spaces and then extend the idea of a {lambda}-firmly nonexpansive mapping from Banach spaces to modular function spaces. We call such mappings as ({lambda},{rho})-firmly nonexpansive mappings. We incorporate the two ideas to approximate fixed points of ({lambda},{rho})-firmly nonexpansive mappings using the above mentioned iterative process in modular function spaces. We give an example to validate our results.
In this article, we propose a Krasnoselskiv{i}-Mann-type algorithm for finding a common fixed point of a countably infinite family of nonexpansive operators $(T_n)_{n geq 0}$ in Hilbert spaces. We formulate an asymptotic property which the family $(T_n)_{n geq 0}$ has to fulfill such that the sequence generated by the algorithm converges strongly to the element in $bigcap_{n geq 0} operatorname{Fix} T_n$ with minimum norm. Based on this, we derive a forward-backward algorithm that allows variable step sizes and generates a sequence of iterates that converge strongly to the zero with minimum norm of the sum of a maximally monotone operator and a cocoercive one. We demonstrate the superiority of the forward-backward algorithm with variable step sizes over the one with constant step size by means of numerical experiments on variational image reconstruction and split feasibility problems in infinite dimensional Hilbert spaces.
This paper is concerned with the variational inequality problem (VIP) over the fixed point set of a quasi-nonexpansive operator. We propose, in particular, an algorithm which entails, at each step, projecting onto a suitably chosen half-space, and prove that the sequences it generates converge to the unique solution of the VIP. We also present an application of our result to a hierarchical optimization problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
