Weak, strong, and linear convergence of a double-layer fixed point algorithm

DOI10.1137/16M1087333MaRDI QIDQ4976159zbMATH OpenOpenAlexFDO

Authors Rafał Zalas, V. I. Kolobov, Simeon Reich

Publication date 27 July 2017

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.09426

zbMATH Keywords

projection methodcommon fixed point problemconvex feasibility problemquasi-nonexpansive operatorcuttersubgradient projectionblock iterative algorithmsimultaneous projectioncyclic projectionboundedly regular operatordemi-closed operatorboundedly regular familyfejér monotone sequenceremotest-set projection

Mathematics Subject Classification ID

Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Iterative procedures involving nonlinear operators (47J25) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Numerical analysis in abstract spaces (65J99)

Abstract: In this article we consider a consistent convex feasibility problem in a real Hilbert space defined by a finite family of sets $C_i$. We are interested, in particular, in the case where for each $i$, $C_i=Fix(U_i)=zinmathcalHmid{p}_i(z)=0$, $U_{i}colonmathcalHightarrowmathcalH$ is a cutter and $p_{i}colonmathcalHightarrow[0,infty)$ is a proximity function. Moreover, we make the following assumption: the computation of $p_i$ is at most as difficult as the evaluation of $U_i$ and this is at most as difficult as projecting onto $C_i$. We study a double-layer fixed point algorithm which applies two types of controls in every iteration step. The first one -- the outer control -- is assumed to be almost cyclic. The second one -- the inner control -- determines the most important sets from those offered by the first one. The selection is made in terms of proximity functions. The convergence results presented in this manuscript depend on the conditions which first, bind together the sets, the operators and the proximity functions and second, connect the inner and outer controls. In particular, weak regularity (demi-closedness principle), bounded regularity and bounded linear regularity imply weak, strong and linear convergence of our algorithm, respectively. The framework presented in this paper covers many known (subgradient) projection algorithms already existing in the literature; for example, those applied with (almost) cyclic, remotest-set, maximum displacement, most-violated constraint and simultaneous controls. In addition, we provide several new examples, where the double-layer approach indeed accelerates the convergence speed as we demonstrate numerically.

Recommendations

• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• Norm convergence of realistic projection and reflection methods
• scientific article; zbMATH DE number 7213713
• The rate of convergence for the cyclic projections algorithm. II: Norms of nonlinear operators
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets

Cites work

• scientific article; zbMATH DE number 3511879 (Why is no real title available?)
• scientific article; zbMATH DE number 1382772 (Why is no real title available?)
• scientific article; zbMATH DE number 3229228 (Why is no real title available?)
• scientific article; zbMATH DE number 3230744 (Why is no real title available?)
• scientific article; zbMATH DE number 3301853 (Why is no real title available?)
• scientific article; zbMATH DE number 3027894 (Why is no real title available?)
• A Weak-to-Strong Convergence Principle for Fejér-Monotone Methods in Hilbert Spaces
• A finitely convergent ``row-action method for the convex feasibility problem
• A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in Hilbert space
• A parallel subgradient projections method for the convex feasibility problem
• A projection method for approximating fixed points of quasi nonexpansive mappings without the usual demiclosedness condition
• Alternating projection methods.
• An alternating projection that does not converge in norm
• Application of quasi-nonexpansive operators to an iterative method for variational inequality
• Applied iterative methods.
• Block-iterative algorithms for solving convex feasibility problems in Hilbert and in Banach spaces
• Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
• Characterizing arbitrarily slow convergence in the method of alternating projections
• Convergence analysis for column-action methods in image reconstruction
• Convergence analysis of a block iterative version of the loping Landweber-Kaczmarz iteration
• Convergence of non-periodic infinite products of orthogonal projections and nonexpansive operators in Hilbert space
• Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Convex analysis and monotone operator theory in Hilbert spaces
• Cyclic subgradient projections
• Decomposition through formalization in a product space
• Functional Operators (AM-22), Volume 2
• General method for solving the split common fixed point problem
• Hilbertian convex feasibility problem: Convergence of projection methods
• Inner inclination of subspaces and infinite products of orthogonal projections
• Iterative methods for fixed point problems in Hilbert spaces
• Landweber-type operator and its properties
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• Mean value iteration of nonexpansive mappings in a Banach space
• Methods for variational inequality problem over the intersection of fixed point sets of quasi-nonexpansive operators
• Minimization of unsmooth functionals
• On Projection Algorithms for Solving Convex Feasibility Problems
• On subgradient projectors
• On the convergence of a class of outer approximation algorithms for convex programs
• Opial-type theorems and the common fixed point problem
• Projection and proximal point methods: Convergence results and counterexamples.
• Projection methods: an annotated bibliography of books and reviews
• Properties of a class of approximately shrinking operators and their applications
• Relaxed outer projections, weighted averages and convex feasibility
• Strong and weak convergence of the sequence of successive approximations for quasi-nonexpansive mappings
• Strong convergence of a hybrid steepest descent method for the split common fixed point problem
• The Relaxation Method for Linear Inequalities
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• The rate of convergence for the cyclic projections algorithm. II: Norms of nonlinear operators
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• The rate of convergence in the method of alternating projections
• The solution by iteration of nonlinear functional equations in Banach spaces
• Theory of Reproducing Kernels
• Weak convergence of the sequence of successive approximations for nonexpansive mappings

Cited in

(8)

• Regular Sequences of Quasi-Nonexpansive Operators and Their Applications
• Linear convergence rates for extrapolated fixed point algorithms
• Finitely convergent iterative methods with overrelaxations revisited
• Conical averagedness and convergence analysis of fixed point algorithms
• Common solutions to a system of variational inequalities over the set of common fixed points of demi-contractive operators
• Asymptotic behaviour of a nonautonomous evolution equation governed by a quasi-nonexpansive operator
• A generalized block-iterative projection method for the common fixed point problem induced by cutters
• Convergence properties of dynamic string-averaging projection methods in the presence of perturbations

This page was built for publication: Weak, strong, and linear convergence of a double-layer fixed point algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4976159)