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

DOI10.1137/16M1087333zbMATH Open1369.47072arXiv1703.09426OpenAlexW2598996488MaRDI QIDQ4976159FDOQ4976159

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

Publication date: 27 July 2017

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

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.

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

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

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)

Cites Work

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

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)