Set intersection problems: supporting hyperplanes and quadratic programming
From MaRDI portal
Publication:2515044
alternating projectionsbest approximation problemDykstra's algorithmquadratic programmingsuperlinear convergencesupporting hyperplanes
Best approximation, Chebyshev systems (41A50) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product) (46C05) Chains (nests) of projections or of invariant subspaces, integrals along chains, etc. (47A46) Equations and inequalities involving linear operators, with vector unknowns (47A50) Iterative procedures involving nonlinear operators (47J25) Set-valued and variational analysis (49J53) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Approximation methods and heuristics in mathematical programming (90C59)
Abstract: We study how the supporting hyperplanes produced by the projection process can complement the method of alternating projections and its variants for the convex set intersection problem. For the problem of finding the closest point in the intersection of closed convex sets, we propose an algorithm that, like Dykstra's algorithm, converges strongly in a Hilbert space. Moreover, this algorithm converges in finitely many iterations when the closed convex sets are cones in satisfying an alignment condition. Next, we propose modifications of the alternating projection algorithm, and prove its convergence. The algorithm converges superlinearly in under some nice conditions. Under a conical condition, the convergence can be finite. Lastly, we discuss the case where the intersection of the sets is empty.
Recommendations
- Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces.
- The supporting halfspace-quadratic programming strategy for the dual of the best approximation problem
- On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
- A new projection method for finding the closest point in the intersection of convex sets
- Dykstra's alternating projection algorithm for two sets
Cites work
- A successive projection method
- A superlinearly convergent projection algorithm for solving the convex inequality problem
- About regularity of collections of sets
- Accelerating the convergence of the method of alternating projections
- Accelerating the convergence of the method of alternating projections via a line search: A brief survey
- Acceleration schemes for the method of alternating projections
- Alternating projection methods.
- An Algorithm for Restricted Least Squares Regression
- An alternating projection that does not converge in norm
- Best approximation in inner product spaces
- Block-iterative surrogate projection methods for convex feasibility problems
- Convex Analysis
- Decomposition through formalization in a product space
- Extrapolation algorithm for affine-convex feasibility problems
- Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces.
- scientific article; zbMATH DE number 3177945 (Why is no real title available?)
- scientific article; zbMATH DE number 2068037 (Why is no real title available?)
- scientific article; zbMATH DE number 878830 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Local linear convergence for alternating and averaged nonconvex projections
- Metric inequality, subdifferential calculus and applications
- Metric regularity and subdifferential calculus
- On Projection Algorithms for Solving Convex Feasibility Problems
- On the convergence of von Neumann's alternating projection algorithm for two sets
- Opial-type theorems and the common fixed point problem
- Projection algorithms: Results and open problems
- Regularities and their relations to error bounds
- Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
- Superlinear rate of convergence and optimal acceleration schemes in the solution of convex inequality problems.
- Techniques of variational analysis
- The method of projections for finding the common point of convex sets
- Variational Analysis
Cited in
(14)- Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces.
- The support-vector algorithm with compound step
- Finitely convergent deterministic and stochastic iterative methods for solving convex feasibility problems
- Finitely convergent iterative methods with overrelaxations revisited
- A simple algorithm for computing projection onto intersection of finite level sets
- On the application of alternating projection under the constraint of linear matrix inequalities
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- The supporting halfspace-quadratic programming strategy for the dual of the best approximation problem
- An acceleration scheme for Dykstra's algorithm
- Convergence Rate Analysis of a Dykstra-Type Projection Algorithm
- The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets
- Projection methods for finding the greatest element of the intersection of max-closed convex sets
- A generalized projection-based scheme for solving convex constrained optimization problems
- Algorithms for projecting a point onto a level surface of a continuous function on a compact set
This page was built for publication: Set intersection problems: supporting hyperplanes and quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515044)
