Transversality and alternating projections for nonconvex sets

DOI10.1007/S10208-015-9279-3MaRDI QIDQ895706zbMATH OpenOpenAlexFDO

Authors A. S. Lewis, D. Drusvyatskiy, Alexander D. Ioffe

Publication date 4 December 2015

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

alternating projectionstransversalityvariational analysislinear convergenceslopenonconvex sets

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Numerical methods of relaxation type (49M20)

Abstract: We consider the method of alternating projections for finding a point in the intersection of two closed sets, possibly nonconvex. Assuming only the standard transversality condition (or a weaker version thereof), we prove local linear convergence. When the two sets are semi-algebraic and bounded, but not necessarily transversal, we nonetheless prove subsequence convergence.

Recommendations

• Local linear convergence for inexact alternating projections on nonconvex sets
• Local linear convergence for alternating and averaged nonconvex projections
• The method of alternating relaxed projections for two nonconvex sets
• Alternating Projections on Manifolds

Cites work

• scientific article; zbMATH DE number 3969124 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 1113627 (Why is no real title available?)
• scientific article; zbMATH DE number 3229228 (Why is no real title available?)
• A Sard theorem for tame set-valued mappings
• Alternating Projections on Manifolds
• Alternating projections on nontangential manifolds
• An Invitation to Tame Optimization
• Clarke Subgradients of Stratifiable Functions
• Critical values of set-valued maps with stratifiable graphs. Extensions of Sard and Smale-Sard theorems
• Curves of descent
• Functional Operators (AM-22), Volume 2
• Local linear convergence for alternating and averaged nonconvex projections
• Metric regularity and subdifferential calculus
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Nonsmooth optimization: conditioning, convergence and semi-algebraic models
• On gradients of functions definable in o-minimal structures
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Quantitative characterizations of regularity properties of collections of sets
• Regularity of collections of sets and convergence of inexact alternating projections
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and the method of alternating projections: theory
• Techniques of variational analysis
• The method of projections for finding the common point of convex sets
• Transversality and alternating projections for nonconvex sets
• Variational Analysis

Cited in

(62)

• A note on the finite convergence of alternating projections
• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections
• Projection methods for quantum channel construction
• Diagonally Dominant Principal Component Analysis
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Dual sufficient characterizations of transversality properties
• Primal necessary characterizations of transversality properties
• Circumcentering approximate reflections for solving the convex feasibility problem
• Alternating Projections on Manifolds
• Some new characterizations of intrinsic transversality in Hilbert spaces
• Local linear convergence for alternating and averaged nonconvex projections
• Characterizations of some transversality-type properties
• Transversality properties: primal sufficient conditions
• A penalized method of alternating projections for weighted low-rank Hankel matrix optimization
• Provable Phase Retrieval with Mirror Descent
• Frame completion with prescribed norms via alternating projection method
• On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications
• Regularity properties in variational analysis and applications in optimisation. (Abstract of thesis)
• About intrinsic transversality of pairs of sets
• Nonlinear transversality of collections of sets: dual space necessary characterizations
• Some convergence strategies for the alternating generalized projection method
• About subtransversality of collections of sets
• Implicit functions: a metric theory
• On cluster points of alternating projections
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
• Geometric and metric characterizations of transversality properties
• Necessary conditions for non-intersection of collections of sets
• Local linear convergence of alternating projections in metric spaces with bounded curvature
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• Alternating projections on nontangential manifolds
• On tangential transversality
• Transversality in variational analysis
• Extremality, stationarity and generalized separation of collections of sets
• A convergent relaxation of the Douglas-Rachford algorithm
• Local linear convergence for inexact alternating projections on nonconvex sets
• Necessary conditions for linear convergence of iterated expansive, set-valued mappings
• A factorization method for completely positive matrices
• Finding a low-rank basis in a matrix subspace
• Metric regularity -- a survey. II: Applications
• Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
• Well-posedness and generalized metric subregularity with respect to an admissible function
• Alternating projections with applications to Gerchberg-Saxton error reduction
• Set regularities and feasibility problems
• Linear convergence of projection algorithms
• The method of alternating relaxed projections for two nonconvex sets
• Transversality and alternating projections for nonconvex sets
• A cyclic Douglas-Rachford iteration scheme
• Implicit error bounds for Picard iterations on Hilbert spaces
• Restricted normal cones and the method of alternating projections: theory
• On a numerical construction of doubly stochastic matrices with prescribed eigenvalues
• Nonsmooth optimization: conditioning, convergence and semi-algebraic models
• Metric inequality conditions on sets and consequences in optimization
• Transversal families of nonlinear projections and generalizations of Favard length
• Sufficient condition for tangential transversality
• Eigenvalue programming beyond matrices
• Extremality of families of sets
• Exact convergence rates of alternating projections for nontransversal intersections
• Two-Stage Robust Quadratic Optimization with Equalities and Its Application to Optimal Power Flow
• Single-projection procedure for infinite dimensional convex optimization problems
• On the centralization of the circumcentered-reflection method
• Generalized alternating projections on manifolds and convex sets

This page was built for publication: Transversality and alternating projections for nonconvex sets

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