Abstract
The paper studies ‘good arrangements’ (transversality properties) of collections of sets in a normed vector space near a given point in their intersection. We target primal (metric and slope) characterizations of transversality properties in the nonlinear setting. The Hölder case is given a special attention. Our main objective is not formally extending our earlier results from the Hölder to a more general nonlinear setting, but rather to develop a general framework for quantitative analysis of transversality properties. The nonlinearity is just a simple setting, which allows us to unify the existing results on the topic. Unlike the well-studied subtransversality property, not many characterizations of the other two important properties: semitransversality and transversality have been known even in the linear case. Quantitative relations between nonlinear transversality properties and the corresponding regularity properties of set-valued map**s as well as nonlinear extensions of the new transversality properties of a set-valued map** to a set in the range space due to Ioffe are also discussed.
Similar content being viewed by others
References
Azé, D., Corvellec, J.N.: Nonlinear local error bounds via a change of metric. J. Fixed Point Theory Appl. 16(1-2), 351–372 (2014). https://doi.org/10.1007/s11784-015-0220-9
Azé, D., Corvellec, J.N.: Nonlinear error bounds via a change of function. J. Optim. Theory Appl. 172(1), 9–32 (2017). https://doi.org/10.1007/s10957-016-1001-3
Bakan, A., Deutsch, F., Li, W.: Strong CHIP, normality, and linear regularity of convex sets. Trans. Amer. Math. Soc. 357(10), 3831–3863 (2005). https://doi.org/10.1090/S0002-9947-05-03945-0
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., Borwein, J.M., Li, W.: Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization. Math. Program., Ser. A 86(1), 135–160 (1999). https://doi.org/10.1007/s101070050083
Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions. Math. Program., Ser. A 165(2), 471–507 (2017). https://doi.org/10.1007/s10107-016-1091-6
Borwein, J.M., Li, G., Tam, M.K.: Convergence rate analysis for averaged fixed point iterations in common fixed point problems. SIAM J. Optim. 27(1), 1–33 (2017). https://doi.org/10.1137/15M1045223
Borwein, J.M., Li, G., Yao, L.: Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets. SIAM J. Optim. 24(1), 498–527 (2014). https://doi.org/10.1137/130919052
Borwein, J.M., Zhuang, D.M.: Verifiable necessary and sufficient conditions for openness and regularity of set-valued and single-valued maps. J. Math. Anal. Appl. 134(2), 441–459 (1988). https://doi.org/10.1016/0022-247X(88)90034-0
Bui, H.T., Cuong, N.D., Kruger, A.Y.: Transversality of collections of sets: Geometric and metric characterizations. Vietnam J Math. https://doi.org/10.1007/s10013-020-00388-1 (2020)
Bui, H.T., Kruger, A.Y.: Extremality, stationarity and generalized separation of collections of sets. J. Optim. Theory Appl. 182(1), 211–264 (2019). https://doi.org/10.1007/s10957-018-01458-8
Cibulka, R., Fabian, M., Kruger, A.Y.: On semiregularity of map**s. J. Math. Anal. Appl. 473(2), 811–836 (2019). https://doi.org/10.1016/j.jmaa.2018.12.071
Corvellec, J.N., Motreanu, V.V.: Nonlinear error bounds for lower semicontinuous functions on metric spaces. Math. Program., Ser. A 114(2), 291–319 (2008)
Cuong, N.D., Kruger, A.Y.: Dual sufficient characterizations of transversality properties. Positivity. https://doi.org/10.1007/s11117-019-00734-9 (2020)
Cuong, N.D., Kruger, A.Y.: Nonlinear transversality of collections of sets: Dual space necessary characterizations. J. Convex Anal. 27(1), 287–308 (2020)
Cuong, N.D., Kruger, A.Y.: Primal space necessary characterizations of transversality properties. Preprint Optimization Online 2020-01-7579 (2020)
De Giorgi, E., Marino, A., Tosques, M.: Evolution problerns in in metric spaces and steepest descent curves. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8) 68(3), 180–187 (1980). In Italian. English translation: Ennio De Giorgi, Selected Papers, Springer, Berlin 2006, pp 527–533
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). https://doi.org/10.1007/978-1-4939-1037-3
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
Drusvyatskiy, D., Li, G., Wolkowicz, H.: A note on alternating projections for ill-posed semidefinite feasibility problems. Math. Program., Ser. A 162(1-2), 537–548 (2017). https://doi.org/10.1007/s10107-016-1048-9
Frankowska, H.: An open map** principle for set-valued maps. J. Math. Anal. Appl. 127(1), 172–180 (1987). https://doi.org/10.1016/0022-247X(87)90149-1
Frankowska, H., Quincampoix, M.: Hölder metric regularity of set-valued maps. Math. Program., Ser. A 132(1-2), 333–354 (2012). https://doi.org/10.1007/s10107-010-0401-7
Gaydu, M., Geoffroy, M.H., Jean-Alexis, C.: Metric subregularity of order q and the solving of inclusions. Cent. Eur. J. Math. 9(1), 147–161 (2011). https://doi.org/10.2478/s11533-010-0087-3
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
Ioffe, A.D.: Metric regularity and subdifferential calculus. Russian Math. Surveys 55, 501–558 (2000). https://doi.org/10.1070/rm2000v055n03ABEH000292
Ioffe, A.D.: Nonlinear regularity models. Math. Program. 139(1-2), 223–242 (2013). https://doi.org/10.1007/s10107-013-0670-z
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.: Variational analysis of regular map**s. Theory and Applications. Springer Monographs in Mathematics Springer. https://doi.org/10.1007/978-3-319-64277-2 (2017)
Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications Nonconvex Optimization and its Applications, vol. 60. Kluwer Academic Publishers, Dordrecht (2002)
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). https://doi.org/10.1007/s11228-006-0014-8
Kruger, A.Y.: About stationarity and regularity in variational analysis. Taiwanese J. Math. 13(6A), 1737–1785 (2009). https://doi.org/10.11650/twjm/1500405612
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.: Error bounds and Hölder metric subregularity. Set-Valued Var. Anal. 23(4), 705–736 (2016). https://doi.org/10.1007/s11228-015-0330-y
Kruger, A.Y.: Nonlinear metric subregularity. J. Optim. Theory Appl. 171(3), 820–855 (2016). https://doi.org/10.1007/s10957-015-0807-8
Kruger, A.Y.: About intrinsic transversality of pairs of sets. Set-Valued Var. Anal. 26(1), 111–142 (2018). https://doi.org/10.1007/s11228-017-0446-3
Kruger, A.Y., López, M.A.: Stationarity and regularity of infinite collections of sets. J. Optim. Theory Appl. 154(2), 339–369 (2012). https://doi.org/10.1007/s10957-012-0043-4
Kruger, A.Y., López, M.A.: Stationarity and regularity of infinite collections of sets. Applications to infinitely constrained optimization. J. Optim. Theory Appl. 155 (2), 390–416 (2012). https://doi.org/10.1007/s10957-012-0086-6
Kruger, A.Y., Luke, D.R., Thao, N.H.: About subtransversality of collections of sets. Set-Valued Var. Anal. 25 (4), 701–729 (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 168(1-2), 279–311 (2018). 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(3-4), 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). https://doi.org/10.1016/j.jmaa.2014.02.028
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)
Kummer, B.: Inclusions in general spaces: Hoelder stability, solution schemes and Ekeland’s principle. J. Math. Anal. Appl. 358(2), 327–344 (2009). https://doi.org/10.1016/j.jmaa.2009.04.060
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
Li, G.: Global error bounds for piecewise convex polynomials. Math. Program. 137(1-2, Ser. A), 37–64 (2013). https://doi.org/10.1007/s10107-011-0481-z
Li, G., Mordukhovich, B.S.: Hölder metric subregularity with applications to proximal point method. SIAM J. Optim. 22(4), 1655–1684 (2012). https://doi.org/10.1137/120864660
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., 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). https://doi.org/10.1023/A:1011291608129
Ngai, H.V., Théra, M.: Error bounds in metric spaces and application to the perturbation stability of metric regularity. SIAM J. Optim. 19(1), 1–20 (2008). https://doi.org/10.1137/060675721
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
Ouyang, W., Zhang, B., Zhu, J.: Hölder metric subregularity for constraint systems in Asplund spaces. Positivity 23(1), 161–175 (2019). https://doi.org/10.1007/s11117-018-0600-7
Penot, J.P.: Calculus without derivatives graduate texts in mathematics, vol. 266. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-4538-8
Rockafellar, R.T., Wets, R.J.B.: Variational analysis. Springer, Berlin (1998)
Thao, N.H., Bui, T.H., Cuong, N.D., Verhaegen, M.: Some new characterizations of intrinsic transversality in Hilbert spaces. Set-Valued Var. Anal. 28 (1), 5–39 (2020). https://doi.org/10.1007/s11228-020-00531-7
Yao, J.C., Zheng, X.Y.: Error bound and well-posedness with respect to an admissible function. Appl. Anal. 95(5), 1070–1087 (2016)
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). https://doi.org/10.1137/060659132
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). https://doi.org/10.1016/j.na.2010.03.032
Zheng, X. Y., Zhu, J.: Generalized metric subregularity and regularity with respect to an admissible function. SIAM J. Optim. 26(1), 535–563 (2016). https://doi.org/10.1137/15M1016345
Acknowledgments
The authors wish to thank the referee and the handling editor for their careful reading of the manuscript and valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Prof. Rafail Gabasov, a great person and teacher
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research was supported by the Australian Research Council, project DP160100854. The second author benefited from the support of the FMJH Program PGMO and from the support of EDF.
Rights and permissions
About this article
Cite this article
Cuong, N.D., Kruger, A.Y. Transversality Properties: Primal Sufficient Conditions. Set-Valued Var. Anal 29, 221–256 (2021). https://doi.org/10.1007/s11228-020-00545-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-020-00545-1
Keywords
- Transversality
- Subtransversality
- Semitransversality
- Regularity
- Subregularity
- Semiregularity
- Slope
- Chain rule