Abstract

We readdress the classical topic of second-order sufficient optimality conditions for optimization problems with nonsmooth structure. Based on the so-called second subderivative of the objective function and of the indicator function associated with the feasible set, one easily obtains second-order sufficient optimality conditions of abstract form. In order to exploit further structure of the problem, e.g., composite terms in the objective function or feasible sets given as (images of) pre-images of closed sets under smooth transformations, to make these conditions fully explicit, we study calculus rules for the second subderivative under mild conditions. To be precise, we investigate a chain rule and a marginal function rule, which then also give a pre-image and image rule, respectively. As it turns out, the chain rule and the pre-image rule yield lower estimates, desirable in order to obtain sufficient optimality conditions, for free. Similar estimates for the marginal function and the image rule are valid under a comparatively mild inner calmness* assumption. Our findings are illustrated by several examples including problems from composite, disjunctive, and nonlinear second-order cone programming.

Author information

Contact details are reproduced from the original publication and may be historical.

Matúš Benko

Institut für Mathematik, Applied Mathematics and Optimization, University of Vienna, Austria

matus.benko@univie.ac.at

Patrick Mehlitz

Institute of Mathematics, Brandenburgische Technische Universität, Cottbus-Senftenberg, Germany

mehlitz@b-tu.de

Keywords

  • Composite optimization
  • optimization with geometric constraints
  • second-order sufficient optimality conditions
  • second-order variational calculus
  • second subderivative

Mathematics Subject Classification

49J52, 49J53, 90C26, 90C46

References

  1. J.-P. Aubin, H. Frankowska: Set-Valued Analysis, Birkhäuser, Boston, 2009.https://doi.org/10.1007/978-0-8176-4848-0Google Scholar
  2. K. Bai, J. J. Ye: Directional necessary optimality conditions for bilevel programs, Math. Oper. Res. 47/2 (2022) 1169–1191.https://doi.org/10.1287/moor.2021.1164Google Scholar
  3. A. Ben-Tal: Second-order and related extremality conditions in nonlinear programming, J. Optim. Theory Appl. 31/2 (1980) 143–165.https://doi.org/10.1007/BF00934107Google Scholar
  4. M. Benko: On inner calmness∗, generalized calculus, and derivatives of the normal cone mapping, J. Nonsmooth Anal. Optim. 2 (2021), art. no. 5881.https://doi.org/10.46298/jnsao-2021-5881Google Scholar
  5. M. Benko, M. Červinka, T. Hoheisel: Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs, Set-Valued Var. Analysis 30/1 (2022) 143–177https://doi.org/10.1007/s11228-020-00569-7Google Scholar
  6. M. Benko, H. Gfrerer, J. V. Outrata: Calculus for directional limiting normal cones and subdifferentials, Set-Valued Var. Analysis 27/3 (2019) 713–745.https://doi.org/10.1007/s11228-018-0492-5Google Scholar
  7. M. Benko, H. Gfrerer, J. J. Ye, J. Zhang, J. Zhou: Second-order optimality conditions for general nonconvex optimization problems and variational analysis of disjunctive systems, arXiv: 2203.10015 (2022).Google Scholar
  8. M. Benko, P. Mehlitz: On implicit variables in optimization theory, J. Nonsmooth Anal. Optim. 2 (2021), art. no. 7215.https://doi.org/10.46298/jnsao-2021-7215Google Scholar
  9. M. Benko, P. Mehlitz: Calmness and calculus: two basic patterns, Set-Valued Var. Analysis 30 (2022) 81–117.https://doi.org/10.1007/s11228-021-00589-xGoogle Scholar
  10. J. F. Bonnans, R. Cominetti, A. Shapiro: Second order optimality conditions based on parabolic second order tangent sets, SIAM J. Optimization 9/2 (1999) 466–492.https://doi.org/10.1137/S1052623496306760Google Scholar
  11. J. F. Bonnans, C. H. Ramírez: Perturbation analysis of second-order cone programming problems, Math. Programming 104 (2005) 205–227.https://doi.org/10.1007/s10107-005-0613-4Google Scholar
  12. J. F. Bonnans, A. Shapiro: Perturbation Analysis of Optimization Problems, Springer, New York (2000).https://doi.org/10.1007/978-1-4612-1394-9Google Scholar
  13. C. Christof, G. Wachsmuth: No-gap second-order conditions via a directional curvature functional, SIAM J. Optimization 28/3 (2018) 2097–2130.https://doi.org/10.1137/17M1140418Google Scholar
  14. F. H. Clarke: Optimization and Nonsmooth Analysis, Wiley Interscience, New York (1983).Google Scholar
  15. S. Dempe: Foundations of Bilevel Programming, Kluwer Academic, Dordrecht (2002).Google Scholar
  16. F. Facchinei, J.-S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York (2003).https://doi.org/10.1007/b97544Google Scholar
  17. M. L. Flegel, C. Kanzow, J. V. Outrata: Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Analysis 15/2 (2007) 139–162.https://doi.org/10.1007/s11228-006-0033-5Google Scholar
  18. H. Gfrerer: On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs, Set-Valued Var. Analysis 21/2 (2013) 151–176.https://doi.org/10.1007/s11228-012-0220-5Google Scholar
  19. H. Gfrerer: Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints, SIAM J. Optimization 24/2 (2014) 898–931.https://doi.org/10.1137/130914449Google Scholar
  20. H. Gfrerer, J. V. Outrata: On computation of generalized derivatives of the normalcone mapping and their applications, Math. Oper. Res. 41/4 (2016) 1535–1556.https://doi.org/10.1287/moor.2016.0789Google Scholar
  21. H. Gfrerer, J. J. Ye, J. Zhou: Second-order optimality conditions for nonconvex set-constrained optimization problems, Math. Oper. Res. 47/3 (2022) 2344–2365.https://doi.org/10.1287/moor.2021.1211Google Scholar
  22. I. Ginchev, B. S. Mordukhovich: On directionally dependent subdifferentials, Proc. Bulgarian Acad. Sci. 64/4 (2011) 497–508.Google Scholar
  23. L. Guo, G.-H. Lin, J. J. Ye, J. Zhang: Sensitivity analysis of the value function for parametric mathematical programs with equilibrium constraints, SIAM J. Optimization 24/3 (2014) 1206–1237.https://doi.org/10.1137/130929783Google Scholar
  24. N. T. V. Hang, B. S. Mordukhovich, M. E. Sarabi: Second-order variational analysis in second-order cone programming, Math. Programming 180/1 (2020) 75–116.https://doi.org/10.1007/s10107-018-1345-6Google Scholar
  25. N. T. V. Hang, B. S. Mordukhovich, M. E. Sarabi: Augmented Lagrangian method for second-order cone programs under second-order sufficiency, J. Global Optim. 82 (2022) 51–81.https://doi.org/10.1007/s10898-021-01068-1Google Scholar
  26. N. T. V. Hang, M. E. Sarabi: Local convergence analysis of augmented Lagrangian methods for piecewise linear-quadratic composite optimization problems, SIAM J. Optimization 31/4 (2021) 2665–2694.https://doi.org/10.1137/20M1375188Google Scholar
  27. Z.-Q. Luo, J.-S. Pang, D. Ralph: Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511983658Google Scholar
  28. G. McCormick: Second order conditions for constrained minima, SIAM J. Appl. Math. 15/3 (1967) 641–652.https://doi.org/10.1137/0115056Google Scholar
  29. P. Mehlitz: On the linear independence constraint qualification in disjunctive programming, Optimization 69/10 (2020) 2241–2277.https://doi.org/10.1080/02331934.2019.1679811Google Scholar
  30. A. Mohammadi, B. S. Mordukhovich, M. E. Sarabi: Parabolic regularity in geometric variational analysis, Trans. Amer. Math. Soc. 374 (2021) 1711–1763.https://doi.org/10.1090/tran/8253Google Scholar
  31. J. V. Outrata, M. Kočvara, J. Zowe: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic, Dordrecht (1998).https://doi.org/10.1007/978-1-4757-2825-5Google Scholar
  32. J. Penot: Second-order conditions for optimization problems with constraints, SIAM J. Control Optim. 37/1 (1998) 303–318.https://doi.org/10.1137/S0363012996311095Google Scholar
  33. R. A. Poliquin, R. T. Rockafellar: Tilt stability of a local minimum, SIAM J. Optimization 8/2 (1998) 287–299.https://doi.org/10.1137/S1052623496309296Google Scholar
  34. S. M. Robinson: Some continuity properties of polyhedral multifunctions, in: Mathematical Programming at Oberwolfach, H. König et al. (eds.), Springer, Berlin (1981) 206–214.https://doi.org/10.1007/BFb0120929Google Scholar
  35. R. T. Rockafellar: Second-order optimality conditions in nonlinear programming obtained by way of epi-derivatives, Math. Oper. Res. 14/3 (1989) 462–484https://doi.org/10.1287/moor.14.3.462Google Scholar
  36. R. T. Rockafellar. Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality, Math. Programming (2022).https://doi.org/10.1007/s10107-022-01768-wGoogle Scholar
  37. R. T. Rockafellar: Convergence of augmented Lagrangian methods in extensions beyond nonlinear programming, Math. Programming (2022).https://doi.org/10.1007/s10107-022-01832-5Google Scholar
  38. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  39. M. E. Sarabi: Primal superlinear convergence of SQP methods in piecewise linear-quadratic composite optimization, Set-Valued Var. Analysis 30 (2022) 1–37.https://doi.org/10.1007/s11228-021-00580-6Google Scholar
  40. V. D. Thinh, T. D. Chuong, N. L. H. Anh: Second order variational analysis of disjunctive constraint sets and its applications to optimization problems, Optimization Letters 15 (2021) 2201–2224.https://doi.org/10.1007/s11590-020-01681-1Google Scholar
  41. D. Wachsmuth, G. Wachsmuth: Second-order conditions for non-uniformly convex integrands: quadratic growth in L1, J. Nonsmooth Anal. Optim. 3 (2022), art. no. 8733.https://doi.org/10.46298/jnsao-2022-8733Google Scholar
  42. D. W. Walkup, R. J.-B. Wets: A Lipschitz characterization of convex polyhedra, Proc. Amer. Math. Soc. 23/1 (1969) 167–173.https://doi.org/10.1090/S0002-9939-1969-0246200-8Google Scholar

Suggested citation

M. Benko, P. Mehlitz. “Why Second-Order Sufficient Conditions are, in a Way, Easy – or – Revisiting the Calculus for Second Subderivatives.” Journal of Convex Analysis 30 (2023), No. 2, 541–589. https://doi.org/10.68381/jca30031

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press.