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 a 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. Numerous examples are provided to illustrate the theory.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bauschke, H.H.: Projection algorithms and monotone operators. Ph.D. thesis, Simon Fraser University, Burnaby, B.C., Canada (1996)
Bauschke, H.H., Borwein, J.M.: On the convergence of von Neumann’s alternating projection algorithm for two sets. Set-Valued Anal. 2, 185–212 (1993)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)
Bauschke, H.H., Borwein, J.M., Lewis, A.S.: The method of cyclic projections for closed convex sets in Hilbert space. In: Censor, Y., Reich, S. (eds.) Recent Developments in Optimization Theory and Nonlinear Analysis (Jerusalem 1995). Contemporary Mathematics, vol. 204, pp. 1–38. American Mathematical Society (1997)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer (2011)
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: theory (2013). doi:10.1007/s11228-013-0239-2
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and sparsity optimization with affine constraints. Found. Comput. Math. (2012, in press). arXiv preprint. http://arxiv.org
Borwein, J.M., Zhu, Q.J.: Techniques of Variational Analysis. Springer (2005)
Censor, Y., Zenios, S.A.: Parallel Optimization. Oxford University Press (1997)
Clarke, F.H., Ledyaev, Y.S., Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Springer (1998)
Combettes, P.L., Trussell, H.J.: Method of successive projections for finding a common point of sets in metric spaces. J. Optim. Theory Appl. 67, 487–507 (1990)
Deutsch, F.: The angle between subspaces of a Hilbert space. In: Singh, S.P., Carbone, A., Watson, B. (eds.) Approximation Theory, Wavelets and Applications (Maratea, 1994). NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 454, pp. 107–130. Kluwer (1995)
Deutsch, F.: Best Approximation in Inner Product Spaces. Springer (2001)
Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm I: angles between convex sets. J. Approx. Theory 142, 36–55 (2006)
Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm II: norms of nonlinear operators. J. Approx. Theory 142, 56–82 (2006)
Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm III: regularity of convex sets. J. Approx. Theory 155, 155–184 (2008)
Dixmier, J.: Étude sur les variétés et les opérateurs de Julia, avec quelques applications. B. Soc. Math. Fr. 77, 11–101 (1949)
Friedrichs, K.: On certain inequalities and characteristic value problems for analytic functions and for functions of two variables. Trans. Amer. Math. Soc. 41, 321–364 (1937)
Gubin, L.G., Polyak, B.T., Raik, E.V.: The method of projections for finding the common point of convex sets. USSR Comput. Math. Math. Phys. 7, 1–24 (1967)
Lewis, A.S., Luke, D.R., Malick, J.: Local linear convergence for alternating and averaged nonconvex projections. Found. Comput. Math. 9, 485–513 (2009)
Lewis, A.S., Malick, J.: Alternating projection on manifolds. Math. Oper. Res. 33, 216–234 (2008)
Luke, D.R.: Finding best approximation pairs relative to a convex and a prox-regular set in a Hilbert space. SIAM J. Optim. 19(2), 714–739 (2008)
Luke, D.R.: Local linear convergence and approximate projections onto regularized sets. Nonlinear Anal. 75, 1531–1546 (2012)
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I. Springer (2006)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rockafellar, R.T.,Wets, R.J-B.: Variational Analysis. Springer, corrected 3rd printing (2009)
Stark, H., Yang, Y.: Vector Space Projections. Wiley (1998)
von Neumann, J.: Functional Operators Vol.II. The Geometry of Orthogonal Spaces. Annals of Mathematical Studies #22, Princeton University Press, Princeton (1950)
Wiener, N.: On the factorization of matrices. Comment. Math. Helv. 29, 97–111 (1955)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bauschke, H.H., Luke, D.R., Phan, H.M. et al. Restricted Normal Cones and the Method of Alternating Projections: Applications. Set-Valued Var. Anal 21, 475–501 (2013). https://doi.org/10.1007/s11228-013-0238-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-013-0238-3
Keywords
- Convex set
- Friedrichs angle
- Linear convergence
- Method of alternating projections
- Nonconvex set
- Normal cone
- Projection operator
- Restricted normal cone
- Superregularity