Finding best approximation pairs for two intersections of closed convex sets

DOI10.1007/S10589-021-00324-0zbMATH Open1484.90076arXiv2102.13194OpenAlexW3209863242MaRDI QIDQ2070342FDOQ2070342

Authors: Heinz H. Bauschke, Shambhavi Singh, Xianfu Wang 

Publication date: 24 January 2022

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

Abstract: The problem of finding a best approximation pair of two sets, which in turn generalizes the well known convex feasibility problem, has a long history that dates back to work by Cheney and Goldstein in 1959. In 2018, Aharoni, Censor, and Jiang revisited this problem and proposed an algorithm that can be used when the two sets are finite intersections of halfspaces. Motivated by their work, we present alternative algorithms that utilize projection and proximity operators. Numerical experiments indicate that these methods are competitive and sometimes superior to the one proposed by Aharoni et al.

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

Recommendations

• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Finding a best approximation pair of points for two polyhedra
• Some remarks on the convex feasibility problem and best approximation problem
• A new projection method for finding the closest point in the intersection of convex sets
• The supporting halfspace-quadratic programming strategy for the dual of the best approximation problem

zbMATH Keywords

Douglas-Rachford algorithmbest approximation pairAharoni-Censor-Jiang algorithmdual-based proximal methodproximal distance algorithmstochastic subgradient descent

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09)

Cites Work

• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• MM optimization algorithms
• First-order methods in optimization
• A Stochastic Approximation Method
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Fixed points of nonexpanding maps
• Approximation of fixed points of nonexpansive mappings
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• Stochastic Estimation of the Maximum of a Regression Function
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Dykstra's alternating projection algorithm for two sets
• Convex analysis and monotone operator theory in Hilbert spaces
• Computational acceleration of projection algorithms for the linear best approximation problem
• Dualization of signal recovery problems
• Proximity Maps for Convex Sets
• Proximal distance algorithms: theory and practice
• The proximal distance algorithm
• A fast dual proximal gradient algorithm for convex minimization and applications
• Optimization methods for large-scale machine learning
• Finding a best approximation pair of points for two polyhedra
• On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint

Cited In (7)

• Best Approximation from the Intersection of a Closed Convex Set and a Polyhedron in Hilbert Space, Weak Slater Conditions, and the Strong Conical Hull Intersection Property
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)
• The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets
• Criteria of strong nearest-cross points and strong best approximation pairs
• Closed convex sets and their best simultaneous approximation properties with applications
• Finding a best approximation pair of points for two polyhedra

Uses Software

• proxdist

This page was built for publication: Finding best approximation pairs for two intersections of closed convex sets

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