A new projection method for finding the closest point in the intersection of convex sets

DOI10.1007/S10589-017-9942-5zbMATH Open1464.47035arXiv1605.07421OpenAlexW3102480021MaRDI QIDQ683336FDOQ683336

Authors: Francisco J. Aragón Artacho, Rubén Campoy 

Publication date: 6 February 2018

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas--Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces.

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

Recommendations

• Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces
• A strongly convergent reflection method for finding the projection onto the intersection of two closed convex sets in a Hilbert space
• scientific article; zbMATH DE number 1174427
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Finding projections onto the intersection of convex sets in hilbert spaces

zbMATH Keywords

projectionreflectionstrong convergenceconvex setDouglas-Rachford algorithmbest approximation problem

Mathematics Subject Classification ID

Convex programming (90C25) 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)

Cites Work

• The rate of convergence for the method of alternating projections. II
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Title not available (Why is that?)
• Theory of Reproducing Kernels
• Convex analysis and monotone operator theory in Hilbert spaces
• Convex Analysis
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Fixed points of nonexpanding maps
• An alternating projection that does not converge in norm
• Asymptotic behavior of contractions in Hilbert space
• Iterative methods for fixed point problems in Hilbert spaces
• A Weak-to-Strong Convergence Principle for Fejér-Monotone Methods in Hilbert Spaces
• Functional Operators (AM-22), Volume 2
• Iterative construction of the resolvent of a sum of maximal monotone operators
• Best approximation in inner product spaces
• Projection and proximal point methods: Convergence results and counterexamples.
• Alternating projection methods.
• An Algorithm for Restricted Least Squares Regression
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Global convergence of a non-convex Douglas-Rachford iteration
• On the local convergence of the Douglas-Rachford algorithm
• Linear convergence of the Douglas-Rachford method for two closed sets
• The Douglas-Rachford algorithm in the absence of convexity
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets
• Alternating Projections on Manifolds
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Local linear convergence for alternating and averaged nonconvex projections
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• Douglas-Rachford feasibility methods for matrix completion problems
• Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
• The Douglas-Rachford algorithm for the case of the sphere and the line
• Decomposition through formalization in a product space
• Dykstra's alternating projection algorithm for two sets
• A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in Hilbert space
• On weak convergence of the Douglas-Rachford method
• Projection methods: an annotated bibliography of books and reviews
• A simple closure condition for the normal cone intersection formula
• A strongly convergent reflection method for finding the projection onto the intersection of two closed convex sets in a Hilbert space
• Title not available (Why is that?)
• A dual approach to constrained interpolation from a convex subset of Hilbert space
• Bounded linear regularity, strong CHIP, and CHIP are distinct properties
• On the Douglas-Rachford algorithm
• Constrained best approximation in Hilbert space. II
• Constrained best approximation in Hilbert space
• Set regularities and feasibility problems

Cited In (29)

• Closed-Form Expressions for Projectors onto Polyhedral Sets in Hilbert Spaces
• The superiorization method with restarted perturbations for split minimization problems with an application to radiotherapy treatment planning
• String-averaging methods for best approximation to common fixed point sets of operators: the finite and infinite cases
• The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators
• Douglas–Rachford algorithm for control-constrained minimum-energy control problems
• Iterative methods for computing the resolvent of the sum of a maximal monotone operator and composite operator with applications
• Random projections for linear programming: an improved retrieval phase
• A strongly convergent reflection method for finding the projection onto the intersection of two closed convex sets in a Hilbert space
• Title not available (Why is that?)
• Deep neural network structures solving variational inequalities
• On the asymptotic behaviour of the Aragón Artacho-Campoy algorithm
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Strengthened splitting methods for computing resolvents
• An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)
• Comparing averaged relaxed cutters and projection methods: theory and examples
• A product space reformulation with reduced dimension for splitting algorithms
• Computing the resolvent of the sum of maximally monotone operators with the averaged alternating modified reflections algorithm
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• A Newton Based Radius Reduction Algorithm for Nearest Point Problems in Pos Cones
• Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces
• A parameterized Douglas-Rachford algorithm
• Finding best approximation pairs for two intersections of closed convex sets
• Set intersection problems: supporting hyperplanes and quadratic programming
• Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach
• A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
• A splitting method for finding the resolvent of the sum of two maximal monotone operators
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Title not available (Why is that?)

This page was built for publication: A new projection method for finding the closest point in the intersection of convex sets

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