Parabolic regularity in geometric variational analysis

Mohammadi, Ashkan; Mordukhovich, Boris; Sarabi, M.

doi:10.1090/tran/8253

Parabolic regularity in geometric variational analysis
HTML articles powered by AMS MathViewer

by Ashkan Mohammadi, Boris S. Mordukhovich and M. Ebrahim Sarabi PDF

Trans. Amer. Math. Soc. 374 (2021), 1711-1763 Request permission

Abstract:

The paper is mainly devoted to systematic developments and applications of geometric aspects of second-order variational analysis that are revolved around the concept of parabolic regularity of sets. This concept has been known in variational analysis for more than two decades while being largely underinvestigated. We discover here that parabolic regularity is the key to derive new calculus rules and computation formulas for major second-order generalized differential constructions of variational analysis in connection with some properties of sets that go back to classical differential geometry and geometric measure theory. The established results of second-order variational analysis and generalized differentiation, being married to the developed calculus of parabolic regularity, allow us to obtain novel applications to both qualitative and quantitative/numerical aspects of constrained optimization including second-order optimality conditions, augmented Lagrangians, etc. under weak constraint qualifications.

References

Samir Adly and Loïc Bourdin, Sensitivity analysis of variational inequalities via twice epi-differentiability and proto-differentiability of the proximity operator, SIAM J. Optim. 28 (2018), no. 2, 1699–1725. MR 3805858, DOI 10.1137/17M1135013
Heinz H. Bauschke, Jonathan M. Borwein, and Wu Li, Strong conical hull intersection property, bounded linear regularity, Jameson’s property $(G)$, and error bounds in convex optimization, Math. Program. 86 (1999), no. 1, Ser. A, 135–160. MR 1712477, DOI 10.1007/s101070050083
A. Ben-Tal and J. Zowe, A unified theory of first and second order conditions for extremum problems in topological vector spaces, Math. Programming Stud. 19 (1982), 39–76. Optimality and stability in mathematical programming. MR 669725, DOI 10.1007/bfb0120982
A. Ben-Tal and J. Zowe, Directional derivatives in nonsmooth optimization, J. Optim. Theory Appl. 47 (1985), no. 4, 483–490. MR 818873, DOI 10.1007/BF00942193
J. Frédéric Bonnans, Roberto Cominetti, and Alexander Shapiro, Second order optimality conditions based on parabolic second order tangent sets, SIAM J. Optim. 9 (1999), no. 2, 466–492. MR 1686803, DOI 10.1137/S1052623496306760
J. Frédéric Bonnans, Roberto Cominetti, and Alexander Shapiro, Sensitivity analysis of optimization problems under second order regular constraints, Math. Oper. Res. 23 (1998), no. 4, 806–831. MR 1662414, DOI 10.1287/moor.23.4.806
J. Frédéric Bonnans and Alexander Shapiro, Perturbation analysis of optimization problems, Springer Series in Operations Research, Springer-Verlag, New York, 2000. MR 1756264, DOI 10.1007/978-1-4612-1394-9
G. Bouligand, Sur les surfaces dépourvues de points hyperlimits, Ann. Soc. Polon Math. 9 (1930), 32–41.
R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal. 9 (1985), no. 11, 1189–1209. MR 813653, DOI 10.1016/0362-546X(85)90030-6
Robin W. Chaney, Second-order directional derivatives for nonsmooth functions, J. Math. Anal. Appl. 128 (1987), no. 2, 495–511. MR 917384, DOI 10.1016/0022-247X(87)90202-2
Robin W. Chaney, Second-order sufficient conditions in nonsmooth optimization, Math. Oper. Res. 13 (1988), no. 4, 660–673. MR 971917, DOI 10.1287/moor.13.4.660
Nguyen Huy Chieu and Le Van Hien, Computation of graphical derivative for a class of normal cone mappings under a very weak condition, SIAM J. Optim. 27 (2017), no. 1, 190–204. MR 3608751, DOI 10.1137/16M1066816
N. H. Chieu, L. V. Hien, T. T. A. Nghia, and H. A. Tuan, Second-order optimality conditions for strong local minimizers via subgradient graphical derivative, arXiv:1903.05746 2019.
Giovanni Colombo and Lionel Thibault, Prox-regular sets and applications, Handbook of nonconvex analysis and applications, Int. Press, Somerville, MA, 2010, pp. 99–182. MR 2768810
Rafael Correa, Abderrahim Hantoute, and Marco A. López-Cerdá, Moreau-Rockafellar-type formulas for the subdifferential of the supremum function, SIAM J. Optim. 29 (2019), no. 2, 1106–1130. MR 3939337, DOI 10.1137/18M1169370
Asen L. Dontchev and R. Tyrrell Rockafellar, Implicit functions and solution mappings, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2014. A view from variational analysis. MR 3288139, DOI 10.1007/978-1-4939-1037-3
Herbert Federer, Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418–491. MR 110078, DOI 10.1090/S0002-9947-1959-0110078-1
Helmut Gfrerer, First order and second order characterizations of metric subregularity and calmness of constraint set mappings, SIAM J. Optim. 21 (2011), no. 4, 1439–1474. MR 2869504, DOI 10.1137/100813415
Helmut Gfrerer and Boris S. Mordukhovich, Second-order variational analysis of parametric constraint and variational systems, SIAM J. Optim. 29 (2019), no. 1, 423–453. MR 3908827, DOI 10.1137/17M1157751
Helmut Gfrerer and Jiří V. Outrata, On computation of generalized derivatives of the normal-cone mapping and their applications, Math. Oper. Res. 41 (2016), no. 4, 1535–1556. MR 3693740, DOI 10.1287/moor.2016.0789
J.-B. Hiriart-Urruty, Approximating a second-order directional derivative for nonsmooth convex functions, SIAM J. Control Optim. 20 (1982), no. 6, 783–807. MR 675570, DOI 10.1137/0320057
J.-B. Hiriart-Urruty, Limiting behaviour of the approximate first order and second order directional derivatives for a convex function, Nonlinear Anal. 6 (1982), no. 12, 1309–1326. MR 684967, DOI 10.1016/0362-546X(82)90106-7
Nguyen T. V. Hang, Boris S. Mordukhovich, and M. Ebrahim Sarabi, Second-order variational analysis in second-order cone programming, Math. Program. 180 (2020), no. 1-2, Ser. A, 75–116. MR 4062832, DOI 10.1007/s10107-018-1345-6
N. T. V. Hang, B. S. Mordukhovich, and M. E. Sarabi, Augmented Lagrangian method for second-order conic programs under second-order sufficiency, arXiv:2005.04182 2020.
René Henrion, Abderrahim Jourani, and Jiři Outrata, On the calmness of a class of multifunctions, SIAM J. Optim. 13 (2002), no. 2, 603–618. MR 1951037, DOI 10.1137/S1052623401395553
René Henrion and Jiří V. Outrata, Calmness of constraint systems with applications, Math. Program. 104 (2005), no. 2-3, Ser. B, 437–464. MR 2179245, DOI 10.1007/s10107-005-0623-2
Claude Lemarechal and Evgueni Nurminskii, Sur la différentiabilité de la fonction d’appui du sous-différentiel approché, C. R. Acad. Sci. Paris Sér. A-B 290 (1980), no. 18, A855–A858 (French, with English summary). MR 579988
A. B. Levy, R. Poliquin, and L. Thibault, Partial extensions of Attouch’s theorem with applications to proto-derivatives of subgradient mappings, Trans. Amer. Math. Soc. 347 (1995), no. 4, 1269–1294. MR 1290725, DOI 10.1090/S0002-9947-1995-1290725-3
Yong-Jin Liu and Li-Wei Zhang, Convergence analysis of the augmented Lagrangian method for nonlinear second-order cone optimization problems, Nonlinear Anal. 67 (2007), no. 5, 1359–1373. MR 2323284, DOI 10.1016/j.na.2006.07.022
Philip D. Loewen and Harry H. Zheng, Epi-derivatives of integral functionals with applications, Trans. Amer. Math. Soc. 347 (1995), no. 2, 443–459. MR 1282892, DOI 10.1090/S0002-9947-1995-1282892-2
A. Mohammadi and B. S. Mordukhovich, Variational analysis in normed spaces with applications to constrained optimization, arXiv:2006.00462 2020, to appear in SIAM J. Optim.
A. Mohammadi, B. S. Mordukhovich, and M. E. Sarabi, Variational analysis of composite models with applications to continuous optimization to appear in Math. Oper. Res., arXiv:1905.08837v2 2020.
B. Sh. Mordukhovich, Maximum principle in the problem of time optimal response with nonsmooth constraints, Prikl. Mat. Meh. 40 (1976), no. 6, 1014–1023 (Russian); English transl., J. Appl. Math. Mech. 40 (1976), no. 6, 960–969 (1977). MR 0487669, DOI 10.1016/0021-8928(76)90136-2
Boris S. Mordukhovich, Sensitivity analysis in nonsmooth optimization, Theoretical aspects of industrial design (Wright-Patterson Air Force Base, OH, 1990) SIAM, Philadelphia, PA, 1992, pp. 32–46. MR 1157413
Boris Mordukhovich, Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions, Trans. Amer. Math. Soc. 340 (1993), no. 1, 1–35. MR 1156300, DOI 10.1090/S0002-9947-1993-1156300-4
Boris S. Mordukhovich, Variational analysis and generalized differentiation. I, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 330, Springer-Verlag, Berlin, 2006. Basic theory. MR 2191744
Boris S. Mordukhovich, Variational analysis and applications, Springer Monographs in Mathematics, Springer, Cham, 2018. MR 3823783, DOI 10.1007/978-3-319-92775-6
R. A. Poliquin and R. T. Rockafellar, A calculus of epi-derivatives applicable to optimization, Canad. J. Math. 45 (1993), no. 4, 879–896. MR 1227665, DOI 10.4153/CJM-1993-050-7
R. A. Poliquin and R. T. Rockafellar, Prox-regular functions in variational analysis, Trans. Amer. Math. Soc. 348 (1996), no. 5, 1805–1838. MR 1333397, DOI 10.1090/S0002-9947-96-01544-9
Stephen M. Robinson, Generalized equations and their solutions. I. Basic theory, Math. Programming Stud. 10 (1979), 128–141. Point-to-set maps and mathematical programming. MR 527064, DOI 10.1007/bfb0120850
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683, DOI 10.1515/9781400873173
R. T. Rockafellar, First- and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc. 307 (1988), no. 1, 75–108. MR 936806, DOI 10.1090/S0002-9947-1988-0936806-9
R. T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré C Anal. Non Linéaire 6 (1989), no. suppl., 449–482. Analyse non linéaire (Perpignan, 1987). MR 1019126, DOI 10.1016/S0294-1449(17)30034-3
R. Tyrrell Rockafellar, Second-order optimality conditions in nonlinear programming obtained by way of epi-derivatives, Math. Oper. Res. 14 (1989), no. 3, 462–484. MR 1008425, DOI 10.1287/moor.14.3.462
R. Tyrrell Rockafellar, Lagrange multipliers and optimality, SIAM Rev. 35 (1993), no. 2, 183–238. MR 1220880, DOI 10.1137/1035044
R. Tyrrell Rockafellar, Second-order convex analysis, J. Nonlinear Convex Anal. 1 (2000), no. 1, 1–16. MR 1751725
R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
Walter Rudin, Principles of mathematical analysis, 2nd ed., McGraw-Hill Book Co., New York, 1964. MR 0166310
F. Severi, Su alcune questioni di topologia infinitesimale, Ann. Soc. Polon. Math. 9 (1930), 97–108.
Alexander Shapiro and Jie Sun, Some properties of the augmented Lagrangian in cone constrained optimization, Math. Oper. Res. 29 (2004), no. 3, 479–491. MR 2082615, DOI 10.1287/moor.1040.0103
Defeng Sun, Jie Sun, and Liwei Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Math. Program. 114 (2008), no. 2, Ser. A, 349–391. MR 2393047, DOI 10.1007/s10107-007-0105-9