A Generalized Newton Method for Subgradient Systems

References

• [1] Aragón Artacho FJ, Geoffroy MH (2008) Characterizations of metric regularity of subdifferentials. J. Convex Anal. 15(2):365–380.Google Scholar
• [2] Beck A (2017) First-Order Methods in Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [3] Berk A, Brugiapaglia S, Hoheisel T (2022) LASSO reloaded: A variational analysis perspective with applications to compressed sensing. Preprint, submitted May 13, https://arxiv.org/abs/2205.06872.Google Scholar
• [4] Bonnans JF (1994) Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29:161–186.Crossref, Google Scholar
• [5] Burke JV, Qi L (1991) Weak directional closedness and generalized subdifferentials. J. Math. Anal. Appl. 159(2):485–499.Crossref, Google Scholar
• [6] Chieu NH, Hien LV, Nghia TTA (2018) Characterization of tilt stability via subgradient graphical derivative with applications to nonlinear programming. SIAM J. Optim. 28(3):2246–2273.Crossref, Google Scholar
• [7] Chieu NH, Lee GM, Yen ND (2017) Second-order subdifferentials and optimality conditions for C1-smooth optimization problems. Appl. Anal. Optim. 1:461–476.Google Scholar
• [8] Clarke FH (1983) Optimization and Nonsmooth Analysis (Wiley, New York).Google Scholar
• [9] Colombo G, Henrion R, Hoang ND, Mordukhovich BS (2016) Optimal control of the sweeping process over polyhedral controlled sets. J. Differential Equations 260(4):3397–3447.Crossref, Google Scholar
• [10] Dias S, Smirnov G (2012) On the Newton method for set-valued maps. Nonlinear Anal. Theory Methods Appl. 75(3):1219–1230.Crossref, Google Scholar
• [11] Ding C, Sun D, Ye JJ (2014) First-order optimality conditions for mathematical programs with semidefinite cone complementarity constraints. Math. Programming 147:539–579.Crossref, Google Scholar
• [12] Dontchev AL, Rockafellar RT (1996) Characterizations of strong regularity for variational inequalities over polyhedral convex sets. SIAM J. Optim. 6(4):1087–1105.Crossref, Google Scholar
• [13] Dontchev AL, Rockafellar RT (2014) Implicit Functions and Solution Mappings: A View from Variational Analysis, 2nd ed. (Springer, New York).Crossref, Google Scholar
• [14] Drusvyatskiy D, Lewis AS (2013) Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential. SIAM J. Optim. 23(1):256–267.Crossref, Google Scholar
• [15] Drusvyatskiy D, Mordukhovich BS, Nghia TTA (2014) Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21(4):1165–1192.Google Scholar
• [16] Facchinei F, Pang J-C (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II (Springer, New York).Google Scholar
• [17] Gfrerer H (2013) On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs. Set-Valued Variational Anal. 21:151–176.Crossref, Google Scholar
• [18] Ginchev I, Mordukhovich BS (2011) On directionally dependent subdifferentials. Comptes Rendus de l'Academie Bulgare des Sciences 64:497–508.Google Scholar
• [19] Gfrerer H, Mordukhovich BS (2015) Complete characterization of tilt stability in nonlinear programming under weakest qualification conditions. SIAM J. Optim. 25(4):2081–2119.Crossref, Google Scholar
• [20] Gfrerer H, Outrata JV (2021) On a semismooth* Newton method for solving generalized equations. SIAM J. Optim. 31(1):489–517.Crossref, Google Scholar
• [21] Hare LW, Sagastizábal C (2009) Computing proximal points of nonconvex functions. Math. Programming 116:221–258.Crossref, Google Scholar
• [22] Henrion R, Outrata JV (2001) A subdifferential condition for calmness of multifunctions. J. Math. Anal. Appl. 258(1):110–130.Crossref, Google Scholar
• [23] Henrion R, Mordukhovich BS, Nam NM (2010) Second-order analysis of polyhedral systems in finite and infinite dimensions with applications to robust stability of variational inequalities. SIAM J. Optim. 20(5):2199–2227.Crossref, Google Scholar
• [24] Henrion R, Outrata JV, Surowiec T (2012) Analysis of M-stationary points to an EPEC modeling ligopolistic competition in an electricity spot market. ESAIM Control Optim. Calculus Variations 18(2):295–317.Crossref, Google Scholar
• [25] Hoheisel T, Kanzow C, Mordukhovich BS, Phan H (2012) Generalized Newton’s method for nonsmooth equations based on graphical derivatives. Nonlinear Anal. 75:1324–1340.Crossref, Google Scholar
• [26] Izmailov AF, Solodov MV (2014) Newton-Type Methods for Optimization and Variational Problems (Springer, New York).Crossref, Google Scholar
• [27] Jiang H, Qi L, Chen X, Sun D (1996) Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations. De Pillo G, Giannessi F, eds. Nonlinear Optimization and Applications (Springer, New York), 197–212.Google Scholar
• [28] Josephy NH (1979) Newton’s method for generalized equations. Technical Summary Report No. 1965, Mathematics Research Center, University of Wisconsin, Madison, WI.Google Scholar
• [29] Kanzow C, Lechner T (2021) Globalized inexact proximal Newton-type methods for nonconvex composite functions. Comput. Optim. Appl. 78(2):377–410.Crossref, Google Scholar
• [30] Kenderov P (1975) Semi-continuity of set-valued monotone mappings. Fundamenta Mathematicae 88(1):61–69.Crossref, Google Scholar
• [31] Khanh PD, Mordukhovich BS, Phat VT, Tran DB (2021) Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization. Preprint, submitted September 5, https://arxiv.org/abs/2109.02093.Google Scholar
• [32] Klatte D, Kummer B (2002) Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• [33] Kummer B (1988) Newton’s method for non-differentiable functions. Guddat J, Bank B, Hollatz H, Kall P, Karte D, Kummer B, Lommatzsch IC, Tammer L, Vlach M, Zimmermann K, eds. Advances in Mathematical Optimization (Akademi-Verlag, Berlin), 114–125.Google Scholar
• [34] Lee JD, Sun Y, Saunders MA (2014) Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24(3):1420–1443.Crossref, Google Scholar
• [35] Meng F, Sun D, Zhao Z (2005) Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization. Math. Programming 104:561–581.Crossref, Google Scholar
• [36] Mifflin R (1977) Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15(6):957–972.Crossref, Google Scholar
• [37] Milzarek A (2016) Numerical methods and second order theory for nonsmooth problems. Unpublished doctoral thesis, Technical University of Munich.Google Scholar
• [38] Mohammadi A, Sarabi ME (2020) Twice epi-differentiability of extended-real-valued functions with applications in composite optimization. SIAM J. Optim. 30(3):2379–2409.Crossref, Google Scholar
• [39] Mohammadi A, Mordukhovich BS, Sarabi ME (2021) Parabolic regularity in geometric variational analysis. Trans. Amer. Math. Soc. 374:1711–1763.Crossref, Google Scholar
• [40] Mohammadi A, Mordukhovich BS, Sarabi ME (2022) Variational analysis of composite models with applications to continuous optimization. Math. Oper. Res. 47(1):397–426.Link, Google Scholar
• [41] Mordukhovich BS (1992) Sensitivity analysis in nonsmooth optimization. Field DA, Komkov V, eds. Theoretical Aspects of Industrial Design, SIAM Proceedings (Philadelphia), 32–46.Google Scholar
• [42] Mordukhovich BS (1993) Complete characterizations of openness, metric regularity, and Lipschitzian properties of multifunctions. Trans. Amer. Math. Soc. 340(1):1–35.Crossref, Google Scholar
• [43] Mordukhovich BS (2006) Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications (Springer, Berlin).Crossref, Google Scholar
• [44] Mordukhovich BS (2018) Variational Analysis and Applications (Springer, Cham, Switzerland).Crossref, Google Scholar
• [45] Mordukhovich BS, Nghia TTA (2015) Second-order characterizations of tilt stability with applications to nonlinear programming. Math. Programming 149:83–104.Crossref, Google Scholar
• [46] Mordukhovich BS, Outrata JV (2001) On second-order subdifferentials and their applications. SIAM J. Optim. 12(1):139–169.Crossref, Google Scholar
• [47] Mordukhovich BS, Rockafellar RT (2012) Second-order subdifferential calculus with applications to tilt stability in optimization. SIAM J. Optim. 22(3):953–986.Crossref, Google Scholar
• [48] Mordukhovich BS, Sarabi ME (2021) Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization. SIAM J. Optim. 31(2):1184–1214.Crossref, Google Scholar
• [49] Mordukhovich BS, Yuan X, Zheng S, Zhang J (2022) A globally convergent proximal Newton-type method in nonsmooth convex optimization. Math. Programming Forthcoming.Crossref, Google Scholar
• [50] Outrata JV, Sun D (2008) On the coderivative of the projection operator onto the second-order cone. Set-Valued Anal. 16:999–1014.Crossref, Google Scholar
• [51] Pang J-S (1990) Newton’s method for B-differentiable equations. Math. Oper. Res. 15(2):311–341.Link, Google Scholar
• [52] Patrinos P, Bemporad A (2013) Proximal Newton methods for convex composite optimization. Proc. IEEE Conf. Dec. Cont., 2358–2363.Google Scholar
• [53] Poliquin RA, Rockafellar RT (1996) Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348(5):1805–1838.Crossref, Google Scholar
• [54] Poliquin RA, Rockafellar RT (1998) Tilt stability of a local minimum. SIAM J. Optim. 8(2):287–299.Crossref, Google Scholar
• [55] Qi L, Sun J (1993) A nonsmooth version of Newton’s method. Math. Programming 58:353–367.Crossref, Google Scholar
• [56] Robinson SM (1979) Generalized equations and their solutions, I: Basic theory. Huard P ed. Point-to-Set Maps and Mathematical Programming, Mathematical Programming Studies, vol. 10 (Springer, Berlin/Heidelberg), 128–141.Crossref, Google Scholar
• [57] Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• [58] Rockafellar RT, Zagrodny D (1997) A derivative-coderivative inclusion in second-order nonsmooth analysis. Set-Valued Anal. 5:1–17.Crossref, Google Scholar
• [59] Sun D (2001) A further result on an implicit function theorem for locally Lipschitz functions. Oper. Res. Lett. 28(4):193–198.Crossref, Google Scholar
• [60] Themelis A, Stella L, Patrinos P (2018) Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone linesearch algorithms. SIAM J. Optim. 28(3):2274–2303.Crossref, Google Scholar
• [61] Tibshirani R (1996) Regression shrinkage and selection via the Lasso. J. Roy. Statist. Soc. 58(1):267–288.Google Scholar
• [62] Ulbrich M (2011) Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces (SIAM, Philadelphia).Crossref, Google Scholar
• [63] Wang X (2004) Subdifferentiability of real functions. Real Anal. Exchange 30(1):137–172.Crossref, Google Scholar
• [64] Yao J-C, Yen ND (2009) Coderivative calculation related to a parametric affine variational inequality. Part 1: Basic calculation. Acta Mathematica Vietnamica 34(1):157–172.Google Scholar