Abstract
The article continues the study of the ‘regular’ arrangement of a collection of sets near a point in their intersection. Such regular intersection or, in other words, transversality properties are crucial for the validity of qualification conditions in optimization as well as subdifferential, normal cone and coderivative calculus, and convergence analysis of computational algorithms. One of the main motivations for the development of the transversality theory of collections of sets comes from the convergence analysis of alternating projections for solving feasibility problems. This article targets infinite dimensional extensions of the intrinsic transversality property introduced recently by Drusvyatskiy, Ioffe and Lewis as a sufficient condition for local linear convergence of alternating projections. Several characterizations of this property are established involving new limiting objects defined for pairs of sets. Special attention is given to the convex case.
Similar content being viewed by others
References
Bakan, A., Deutsch, F., Li, W.: Strong CHIP, normality, and linear regularity of convex sets. Trans. Am. Math. Soc. 357(10), 3831–3863 (2005)
Bauschke, H.H., Borwein, J.M.: On the convergence of von Neumann’s alternating projection algorithm for two sets. Set-Valued Anal. 1(2), 185–212 (1993)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3), 367–426 (1996). https://doi.org/10.1137/S0036144593251710
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: applications. Set-Valued Var. Anal. 21(3), 475–501 (2013). https://doi.org/10.1007/s11228-013-0238-3
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: theory. Set-Valued Var. Anal. 21(3), 431–473 (2013). https://doi.org/10.1007/s11228-013-0239-2
Borwein, J.M., Zhu, Q.J.: Techniques of Variational Analysis. Springer, New York (2005)
Bregman, L.M.: The method of successive projection for finding a common point of convex sets. Sov. Math. Dokl. 6, 688–692 (1965)
Clarke, F.H., Ledyaev, Y.S., Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Graduate Texts in Mathematics, vol. 178. Springer, New York (1998)
Dolecki, S.: Tangency and differentiation: some applications of convergence theory. Ann. Mat. Pura Appl. 130(4), 223–255 (1982). https://doi.org/10.1007/BF01761497
Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Map**s. A View from Variational Analysis, 2 edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2014)
Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Transversality and alternating projections for nonconvex sets. Found. Comput. Math. 15(6), 1637–1651 (2015). https://doi.org/10.1007/s10208-015-9279-3
Guillemin, V., Pollack, A.: Differential Topology. Prentice-Hall, Inc., Englewood Cliffs (1974)
Gurin, 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(6), 1–24 (1967). https://doi.org/10.1016/0041-5553(67)90113-9
Hesse, R., Luke, D.R.: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Optim. 23(4), 2397–2419 (2013). https://doi.org/10.1137/120902653
Hirsch, M.W.: Differential Topology. Springer, New York (1976). Graduate Texts in Mathematics, No. 33
Ioffe, A.D.: Approximate subdifferentials and applications. III. The metric theory. Mathematika 36(1), 1–38 (1989)
Ioffe, A.D.: Metric regularity and subdifferential calculus. Russ. Math. Surv. 55, 501–558 (2000)
Ioffe, A.D.: Metric regularity—a survey. Part I. Theory. J. Aust. Math. Soc. 101 (2), 188–243 (2016). https://doi.org/10.1017/S1446788715000701
Ioffe, A.D.: Metric regularity—a survey. Part II. Applications. J. Aust. Math. Soc. 101(3), 376–417 (2016). https://doi.org/10.1017/S1446788715000695
Klatte, D., Li, W.: Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Program., Ser. A 84(1), 137–160 (1999)
Kruger, A.Y.: On Fréchet subdifferentials. J. Math. Sci. 116(3), 3325–3358 (2003)
Kruger, A.Y.: Stationarity and regularity of set systems. Pac. J. Optim. 1(1), 101–126 (2005)
Kruger, A.Y.: About regularity of collections of sets. Set-Valued Anal. 14(2), 187–206 (2006)
Kruger, A.Y.: About stationarity and regularity in variational analysis. Taiwan. J. Math. 13(6A), 1737–1785 (2009)
Kruger, A.Y.: Error bounds and metric subregularity. Optimization 64(1), 49–79 (2015). https://doi.org/10.1080/02331934.2014.938074
Kruger, A.Y., López, M.A.: Stationarity and regularity of infinite collections of sets. J. Optim. Theory Appl. 154(2), 339–369 (2012)
Kruger, A.Y., Luke, D.R., Thao, N.H.: About subtransversality of collections of sets. Set-Valued Var. Anal. 1–29. (2017). https://doi.org/10.1007/s11228-017-0436-5
Kruger, A.Y., Luke, D.R., Thao, N.H.: Set regularities and feasibility problems. Math. Program., Ser. B 1–33. (2017). https://doi.org/10.1007/s10107-016-1039-x
Kruger, A.Y., Thao, N.H.: About uniform regularity of collections of sets. Serdica Math. J. 39, 287–312 (2013)
Kruger, A.Y., Thao, N.H.: About [q]-regularity properties of collections of sets. J. Math. Anal. Appl. 416(2), 471–496 (2014)
Kruger, A.Y., Thao, N.H.: Quantitative characterizations of regularity properties of collections of sets. J. Optim. Theory Appl. 164(1), 41–67 (2015). https://doi.org/10.1007/s10957-014-0556-0
Kruger, A.Y., Thao, N.H.: Regularity of collections of sets and convergence of inexact alternating projections. J. Convex Anal. 23(3), 823–847 (2016)
Lewis, A.S., Luke, D.R., Malick, J.: Local linear convergence for alternating and averaged nonconvex projections. Found. Comput. Math. 9(4), 485–513 (2009). https://doi.org/10.1007/s10208-008-9036-y
Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33(1), 216–234 (2008)
Li, C., Ng, K.F.: Strong CHIP for infinite system of closed convex sets in normed linear spaces. SIAM J. Optim. 16(2), 311–340 (2005). https://doi.org/10.1137/040613238
Li, C., Ng, K.F.: The dual normal CHIP and linear regularity for infinite systems of convex sets in Banach spaces. SIAM J. Optim. 24(3), 1075–1101 (2014). https://doi.org/10.1137/130941493
Li, C., Ng, K.F., Pong, T.K.: The SECQ, linear regularity, and the strong CHIP for an infinite system of closed convex sets in normed linear spaces. SIAM J. Optim. 18(2), 643–665 (2007). https://doi.org/10.1137/060652087
Luke, D.R., Thao, N.H., Tam, M.K.: Quantitative convergence analysis of iterated expansive, set-valued map**s. Math. Oper. Res. (2017). To appear
Luke, D.R., Thao, N.H., Teboulle, M.: Necessary conditions for linear convergence of Picard iterations and application to alternating projections, pp. 1–22. ar**v:1704.08926 (2017)
Mordukhovich, B.S.: Approximation Methods in Problems of Optimization and Control. Moscow, Nauka (1988). In Russian
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation. I: Basic Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 330. Springer, Berlin (2006)
Ng, K.F., Yang, W.H.: Regularities and their relations to error bounds. Math. Program., Ser. A 99(3), 521–538 (2004). https://doi.org/10.1007/s10107-003-0464-9
Ng, K.F., Zang, R.: Linear regularity and ϕ-regularity of nonconvex sets. J. Math. Anal. Appl. 328 (1), 257–280 (2007). https://doi.org/10.1016/j.jmaa.2006.05.028
Ngai, H.V., Théra, M.: Metric inequality, subdifferential calculus and applications. Set-Valued Anal. 9(1–2), 187–216 (2001). Wellposedness in Optimization and Related Topics (Gargnano, 1999)
Noll, D., Rondepierre, A.: On local convergence of the method of alternating projections. Found. Comput. Math. 16(2), 425–455 (2016). https://doi.org/10.1007/s10208-015-9253-0
Penot, J.P.: Calculus without Derivatives. Graduate Texts in Mathematics, vol. 266. Springer, New York (2013)
Phelps, R.R.: Convex Functions, Monotone Operators and Differentiability. Lecture Notes in Mathematics, 2nd edn, vol. 1364. Springer, Berlin (1993)
Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (1998)
Zheng, X.Y., Ng, K.F.: Linear regularity for a collection of subsmooth sets in Banach spaces. SIAM J. Optim. 19(1), 62–76 (2008)
Zheng, X.Y., Wei, Z., Yao, J.C.: Uniform subsmoothness and linear regularity for a collection of infinitely many closed sets. Nonlinear Anal. 73(2), 413–430 (2010)
Acknowledgements
The author thanks Nguyen Hieu Thao and the referees for the careful reading of the manuscript and constructive comments and suggestions.
The research was supported by Australian Research Council, project DP160100854.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Professor Jonathan Michael Borwein
Rights and permissions
About this article
Cite this article
Kruger, A.Y. About Intrinsic Transversality of Pairs of Sets. Set-Valued Var. Anal 26, 111–142 (2018). https://doi.org/10.1007/s11228-017-0446-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-017-0446-3
Keywords
- Metric regularity
- Metric subregularity
- Transversality
- Subtransversality
- Intrinsic transversality
- Normal cone
- Alternating projections
- Linear convergence