Generalized second derivatives of convex functions and saddle functions

Rockafellar, R. T.

doi:10.1090/S0002-9947-1990-1031242-0

Generalized second derivatives of convex functions and saddle functions
HTML articles powered by AMS MathViewer

by R. T. Rockafellar PDF

Trans. Amer. Math. Soc. 322 (1990), 51-77 Request permission

Abstract:

The theory of second-order epi-derivatives of extended-real-valued functions is applied to convex functions on ${\mathbb {R}^n}$ and shown to be closely tied to proto-differentiation of the corresponding subgradient multifunctions, as well as to second-order epi-differentiation of conjugate functions. An extension is then made to saddle functions, which by definition are convex in one argument and concave in another. For this case a concept of epi-hypo-differentiability is introduced. The saddle function results provide a foundation for the sensitivity analysis of primal and dual optimal solutions to general finite-dimensional problems in convex optimization, since such solutions are characterized as saddlepoints of a convex-concave Lagrangian function, or equivalently as subgradients of the saddle function conjugate to the Lagrangian.

References

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
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
Alfred Auslender, On the differential properties of the support function of the $\varepsilon$-subdifferential of a convex function, Math. Programming 24 (1982), no. 3, 257–268. MR 676945, DOI 10.1007/BF01585110
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
J.-B. Hiriart-Urruty, Approximate first-order and second-order directional derivatives of a marginal function in convex optimization, J. Optim. Theory Appl. 48 (1986), no. 1, 127–140. MR 825388, DOI 10.1007/BF00938593
J.-B. Hiriart-Urruty, The approximate first-order and second-order directional derivatives for a convex function, Mathematical theories of optimization (Genova, 1981) Lecture Notes in Math., vol. 979, Springer, Berlin-New York, 1983, pp. 144–177. MR 713809
J.-B. Hiriart-Urruty, Calculus rules on the approximate second-order directional derivative of a convex function, SIAM J. Control Optim. 22 (1984), no. 3, 381–404. MR 739833, DOI 10.1137/0322025
J.-B. Hiriart-Urruty and A. Seeger, Calculus rules on a new set-valued second order derivative for convex functions, Nonlinear Anal. 13 (1989), no. 6, 721–738. MR 998516, DOI 10.1016/0362-546X(89)90090-4
Jean-Baptiste Hiriart-Urruty, Jean-Jacques Strodiot, and V. Hien Nguyen, Generalized Hessian matrix and second-order optimality conditions for problems with $C^{1,1}$ data, Appl. Math. Optim. 11 (1984), no. 1, 43–56. MR 726975, DOI 10.1007/BF01442169
Frank H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247–262. MR 367131, DOI 10.1090/S0002-9947-1975-0367131-6

Nonsmooth analysis and optimization

Jean-Pierre Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984), no. 1, 87–111. MR 736641, DOI 10.1287/moor.9.1.87
Jean-Pierre Aubin and Ivar Ekeland, Applied nonlinear analysis, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984. A Wiley-Interscience Publication. MR 749753
R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré Anal. Non Linéaire 2 (1985), no. 3, 167–184 (English, with French summary). MR 797269
Hédy Attouch, Convergence de fonctions convexes, des sous-différentiels et semi-groupes associés, C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 10, A539–A542 (French, with English summary). MR 473929

Variational convergence for functions and operators

The existence almost everywhere of the second differential of a convex function and some associated properties of convex surfaces

37

R. M. Dudley, On second derivatives of convex functions, Math. Scand. 41 (1977), no. 1, 159–174. MR 482164, DOI 10.7146/math.scand.a-11710

Épi-convergence en calcul différentiel généralisé: Résultats de convergence et approximation

Alfred Auslender, Stability in mathematical programming with nondifferentiable data, SIAM J. Control Optim. 22 (1984), no. 2, 239–254. MR 732426, DOI 10.1137/0322017
R. W. Chaney, On sufficient conditions in nonsmooth optimization, Math. Oper. Res. 7 (1982), no. 3, 463–475. MR 667935, DOI 10.1287/moor.7.3.463

Second-order sufficient conditions for nondifferentiable progrmming problems

20

R. W. Chaney, A general sufficiency theorem for nonsmooth nonlinear programming, Trans. Amer. Math. Soc. 276 (1983), no. 1, 235–245. MR 684505, DOI 10.1090/S0002-9947-1983-0684505-9
X. Q. Yang, On second-order directional derivatives, Nonlinear Anal. 26 (1996), no. 1, 55–66. MR 1354791, DOI 10.1016/0362-546X(94)00209-Z
Robin W. Chaney, Second-order necessary conditions in constrained semismooth optimization, SIAM J. Control Optim. 25 (1987), no. 4, 1072–1081. MR 893999, DOI 10.1137/0325059
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
Aharon Ben-Tal, Second order theory of extremum problems, Extremal methods and systems analysis (Internat. Sympos., Univ. Texas, Austin, Tex., 1977) Lecture Notes in Econom. and Math. Systems, vol. 174, Springer, Berlin-New York, 1980, pp. 336–356. MR 563871
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
Alberto Seeger, Second order directional derivatives in parametric optimization problems, Math. Oper. Res. 13 (1988), no. 1, 124–139. MR 931491, DOI 10.1287/moor.13.1.124
Alexander Shapiro, Perturbation theory of nonlinear programs when the set of optimal solutions is not a singleton, Appl. Math. Optim. 18 (1988), no. 3, 215–229. MR 945763, DOI 10.1007/BF01443623
Alexander Shapiro, Second-order derivatives of extremal-value functions and optimality conditions for semi-infinite programs, Math. Oper. Res. 10 (1985), no. 2, 207–219. MR 793879, DOI 10.1287/moor.10.2.207
Alexander Shapiro, Sensitivity analysis of nonlinear programs and differentiability properties of metric projections, SIAM J. Control Optim. 26 (1988), no. 3, 628–645. MR 937676, DOI 10.1137/0326037
R. Cominetti and R. Correa, A generalized second-order derivative in nonsmooth optimization, SIAM J. Control Optim. 28 (1990), no. 4, 789–809. MR 1051624, DOI 10.1137/0328045
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. 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
Dominique Azé, Hédy Attouch, and Roger J.-B. Wets, Convergence of convex-concave saddle functions: applications to convex programming and mechanics, Ann. Inst. H. Poincaré Anal. Non Linéaire 5 (1988), no. 6, 537–572 (English, with French summary). MR 978671
Gabriella Salinetti and Roger J.-B. Wets, On the convergence of sequences of convex sets in finite dimensions, SIAM Rev. 21 (1979), no. 1, 18–33. MR 516381, DOI 10.1137/1021002
R. T. Rockafellar, Generalized directional derivatives and subgradients of nonconvex functions, Canadian J. Math. 32 (1980), no. 2, 257–280. MR 571922, DOI 10.4153/CJM-1980-020-7
R. A. Wijsman, Convergence of sequences of convex sets, cones and functions, Bull. Amer. Math. Soc. 70 (1964), 186–188. MR 157278, DOI 10.1090/S0002-9904-1964-11072-7
R. A. Wijsman, Convergence of sequences of convex sets, cones and functions. II, Trans. Amer. Math. Soc. 123 (1966), 32–45. MR 196599, DOI 10.1090/S0002-9947-1966-0196599-8
Umberto Mosco, Convergence of convex sets and of solutions of variational inequalities, Advances in Math. 3 (1969), 510–585. MR 298508, DOI 10.1016/0001-8708(69)90009-7
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. J.-B. Wets, Convergence of convex functions, variational inequalities and convex optimization problems, Variational inequalities and complementarity problems (Proc. Internat. School, Erice, 1978) Wiley, Chichester, 1980, pp. 375–403. MR 578760
R. T. Rockafellar, Minimax theorems and conjugate saddle-functions, Math. Scand. 14 (1964), 151–173. MR 175037, DOI 10.7146/math.scand.a-10714
Hédy Attouch and Roger J.-B. Wets, A convergence theory for saddle functions, Trans. Amer. Math. Soc. 280 (1983), no. 1, 1–41. MR 712247, DOI 10.1090/S0002-9947-1983-0712247-X

Analyse du second ordre de problèmes d’optimisation non différentiable