Restricted normal cones and the method of alternating projections: theory

DOI10.1007/S11228-013-0239-2zbMATH Open1272.49027arXiv1205.0318OpenAlexW2132628835MaRDI QIDQ368469FDOQ368469

Authors: Heinz H. Bauschke, D. Russell Luke, Hung M. Phan, Xianfu Wang 

Publication date: 23 September 2013

Published in: Set-Valued and Variational Analysis (Search for Journal in Brave)

Abstract: The method of alternating projections (MAP) is a common method for solving feasibility problems. While employed traditionally to subspaces or to convex sets, little was known about the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick derived local linear convergence results provided that a condition involving normal cones holds and at least one of the sets is superregular (a property less restrictive than convexity). However, their results failed to capture very simple classical convex instances such as two lines in three-dimensional space. In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only any two linear subspaces but also any two closed convex sets whose relative interiors meet are covered. We also allow for sets that are more structured such as unions of convex sets. The key tool required is the restricted normal cone, which is a generalization of the classical Mordukhovich normal cone. We thoroughly study restricted normal cones from the viewpoint of constraint qualifications and regularity. Numerous examples are provided to illustrate the theory.

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

Recommendations

• Restricted normal cones and the method of alternating projections: applications
• The method of alternating relaxed projections for two nonconvex sets
• Transversality and alternating projections for nonconvex sets
• On the convergence of von Neumann's alternating projection algorithm for two sets

zbMATH Keywords

normal coneconvex setFriedrichs angleprojection operatorconstraint qualificationnonconvex setrestricted normal conesuperregularity

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Nonsmooth analysis (49J52) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09)

Cites Work

• Convex analysis and monotone operator theory in Hilbert spaces
• Convex Analysis
• Title not available (Why is that?)
• Techniques of variational analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted normal cones and sparsity optimization with affine constraints
• Title not available (Why is that?)
• Functional Operators (AM-22), Volume 2
• Best approximation in inner product spaces
• Title not available (Why is that?)
• Restricted normal cones and the method of alternating projections: applications
• Alternating Projections on Manifolds
• Local linear convergence for alternating and averaged nonconvex projections
• Title not available (Why is that?)
• On the factorization of matrices
• Étude sur les variétés et les opérateurs de Julia, avec quelques applications

Cited In (32)

• An algorithm for generalized constrained multi-source Weber problem with demand substations
• About subtransversality of collections of sets
• Restricted normal cones and sparsity optimization with affine constraints
• Regularity of sets under a reformulation in a product space with reduced dimension
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• Characterization of metric regularity for \({\sigma}\)-subsmooth multifunctions
• Linear convergence of projection algorithms
• Cardinality minimization, constraints, and regularization: a survey
• Restricted normal cones and the method of alternating projections: applications
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• About intrinsic transversality of pairs of sets
• Nonnegative low rank tensor approximations with multidimensional image applications
• The block-wise circumcentered-reflection method
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Extremality, stationarity and generalized separation of collections of sets
• Convergence rates with inexact non-expansive operators
• Set regularities and feasibility problems
• Necessary conditions for linear convergence of iterated expansive, set-valued mappings
• Linear convergence of the Douglas-Rachford method for two closed sets
• Some new characterizations of intrinsic transversality in Hilbert spaces
• Metric inequality conditions on sets and consequences in optimization
• A cyclic Douglas-Rachford iteration scheme
• Regularity properties of non-negative sparsity sets
• The method of alternating relaxed projections for two nonconvex sets
• On the local convergence of the Douglas-Rachford algorithm
• Alternating projections with applications to Gerchberg-Saxton error reduction
• Projection methods for quantum channel construction
• Transversality and alternating projections for nonconvex sets
• Norm convergence of realistic projection and reflection methods
• Transversality in variational analysis
• Duality and Convex Programming
• On a numerical construction of doubly stochastic matrices with prescribed eigenvalues

This page was built for publication: Restricted normal cones and the method of alternating projections: theory

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