Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Generalized second derivatives of convex functions and saddle functions


Author: R. T. Rockafellar
Journal: Trans. Amer. Math. Soc. 322 (1990), 51-77
MSC: Primary 90C30; Secondary 49J52
DOI: https://doi.org/10.1090/S0002-9947-1990-1031242-0
MathSciNet review: 1031242
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] C. Lemarechal and E. Nurminski, Sur la différentiabilité de la fonction d'appui du sous-différential approaché, C.R. Acad. Sci Paris 290 (1980), 855-858. MR 579988 (81m:46060)
  • [2] R. T. Rockafellar, Convex analysis, Princeton Univ. Press, Princeton, N.J., 1970. MR 0274683 (43:445)
  • [3] A. Auslender, Differential properties of the support function of the $ \varepsilon $-subdifferential of a convex function, Math. Programming 24 (1982), 257-268 (also C.R. Acad. Sci. Paris 292 (1981), 221-224). MR 676945 (84d:58007)
  • [4] J.-B. Hiriart-Urruty, Approximating a second-order directional derivative for nonsmooth convex functions, SIAM J. Control. Optim. 20 (1982), 381-404. MR 675570 (84k:49021)
  • [5] -, Limiting behavior of the approximate first and second-order directional derivatives for a convex function, Nonlinear Anal. Theory Methods Appl. 6 (1982), 1309-1326. MR 684967 (85f:58009)
  • [6] -, The approximate first-order and second-order directional derivatives of a marginal function in convex optimization, J. Optim. Theory Appl. 48 (1986), 127-140. MR 825388 (87f:90094)
  • [7] -, The approximate first-order and second-order directional derivatives for a convex function, Mathematical Theories of Optimization, Lecture Notes in Math., vol. 979, Springer-Verlag, 1983, pp. 144-177. MR 713809 (84i:49029)
  • [8] -, Calculus rules on the approximate second-order directional derivative of a convex function, SIAM J. Control Optim. 22 (1984), 381-404. MR 739833 (85i:49023)
  • [9] J.-B. Hiriart-Urruty and A. Seeger, Calculus rules on a new set-valued second-order derivative for convex functions, Nonlinear Anal. Theory Methods Appl. 13 (1989), 721-738. MR 998516 (90e:26024)
  • [10] J.-B. Hiriart-Urruty, J.-J. Strodiot and V. Hien Nguyen, Generalized Hessian matrix and second-order optimality conditions for problems with $ {\mathcal{C}^{1,1}}$ data, Appl. Math. Optim. 11 (1984), 43-56. MR 726975 (85g:49031)
  • [11] F. H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247-262. MR 0367131 (51:3373)
  • [12] -, Nonsmooth analysis and optimization, Wiley, 1983.
  • [13] J. P. Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984), 87-111. MR 736641 (86f:90119)
  • [14] J. P. Aubin and I. Ekeland, Applied nonlinear analysis, Wiley, 1984. MR 749753 (87a:58002)
  • [15] R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré. Anal. Non Linéaire 2 (1985), 167-184. MR 797269 (87c:49021)
  • [16] H. Attouch, Convergence de fonctions convexes, des sous-différentiels, et semi-groupes associés, C.R. Acad. Sci. Paris 284 (1977), 539-542. MR 0473929 (57:13587)
  • [17] -, Variational convergence for functions and operators, Pitman, London, 1984.
  • [18] A. D. Alexandroff, The existence almost everywhere of the second differential of a convex function and some associated properties of convex surfaces, Uchen. Zap. Gos. Univ. Ser. Mat. 37 (1939), 3-35. (Russian)
  • [19] R. M. Dudley, On second derivatives of convex functions, Math. Scand. 41 (1977), 159-174, and 46 (1980), 61. MR 0482164 (58:2250)
  • [20] J. L. Ndoutoume, Épi-convergence en calcul différentiel généralisé: Résultats de convergence et approximation, Thèse, Université de Perpignan, 1987.
  • [21] A. Auslender, Stability in mathematical programming with nondifferentiable data, SIAM J. Control. Optim. 22 (1984), 239-254. MR 732426 (85d:90082)
  • [22] R. W. Chaney, On sufficient conditions in nonsmooth optimization, Math. Oper. Res. 7 (1982), 463-475. MR 667935 (83m:49021)
  • [23] -, Second-order sufficient conditions for nondifferentiable progrmming problems, SIAM J. Control Optim. 20 (1982), 20-33.
  • [24] -, A general sufficiency theorem for nonsmooth nonlinear programming, Trans. Amer. Math. Soc. 276 (1983), 235-245. MR 684505 (84d:90092)
  • [25] -, On second-order directional derivatives for nonsmooth functions, J. Nonlinear Anal. Theory Math. Appl. (to appear). MR 1354791 (97k:49029)
  • [26] -, Second-order necessary conditions in semismooth optimization, SIAM J. Control. Optim. 25 (1987), 1072-1081. MR 893999 (89d:90183)
  • [27] -, Second-order sufficient conditions in nonsmooth optimization, Math. Oper. Res. 13 (1988), 660-673. MR 971917 (90b:90112)
  • [28] A. Ben-Tal, Second order theory for extremum problems, System Analysis and External Methods (A.V. Fiacco and K. Kostaneta, eds.), Lecture Notes in Economics and Mathematical Sciences, Springer-Verlag, 1980, pp. 336-356. MR 563871 (83c:90143)
  • [29] A. Ben-Tal and J. Zowe, A unified theory of first and second-order conditions for extremum problems in topological vector spaces, Math. Programming Studies 19 (1982), 39-76. MR 669725 (84d:90090)
  • [30] -, Directional derivatives in nonsmooth optimization, J. Optim. Theory Appl. 47 (1985), 483-490. MR 818873 (87b:49037)
  • [31] A. Seeger, Second order directional derivatives in parametric optimization problems, Math. Oper. Res. 13 (1988), 124-139. MR 931491 (89d:90217)
  • [32] A. Shapiro, Perturbation theory of nonlinear programs when the set of optimal solutions is not a singleton, Appl. Math. Optim. 18 (1988), 215-229. MR 945763 (89g:90219)
  • [33] -, Second-order derivatives of extremal-value functions and optimality conditions for semiinfinite programs, Math. Oper. Res. 10 (1985), 207-219. MR 793879 (86k:90130)
  • [34] -, Sensitivity analysis of nonlinear programs and differentiability properties of metric projections, SIAM J. Control Optim. 26 (1988), 628-645. MR 937676 (89j:90230)
  • [35] R. Cominetti and R. Correa, A generalized second order derivative in nonsmooth optimization, SIAM J. Control Optim. (to appear). MR 1051624 (91h:49017)
  • [36] R. T. Rockafellar, First and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc. 307 (1988), 75-108. MR 936806 (90a:90216)
  • [37] -, Second-order optimality conditions in nonlinear programming obtained by way of epiderivatives, Math. Oper. Res. 14 (1989), 462-484. MR 1008425 (91b:49022)
  • [38] H. Attouch, D. Azé, and R. J-B Wets, Convergence of convex-concave saddle functions: continuity properties of the Legendre-Fenchel transform and applications to convex programming and mechanics, Ann. Inst. H. Poincaré Anal. Non Linéaire 5 (1988), 537-572. MR 978671 (90g:90118)
  • [39] G. Salinetti and R. J.-B. Wets, On the convergence of sequences of convex sets in finite dimensions, SIAM Rev. 21 (1979), 18-33. MR 516381 (80h:52007)
  • [40] R. T. Rockafellar, Generalized directional derivatives and subgradients of nonconvex functions, Canad. J. Math. 32 (1980), 157-180. MR 571922 (81f:49006)
  • [41] R. A. Wijsman, Convergence of sequencs of convex sets, cones and functions, I, Bull. Amer. Math. Soc. 70 (1964), 186-188. MR 0157278 (28:514)
  • [42] -, Convergence of sequences of convex sets, cones and functions, II, Trans. Amer. Math. Soc. 123 (1966), 32-45. MR 0196599 (33:4786)
  • [43] U. Mosco, Convergence of convex sets and solutions to variational inequalities, Adv. in Math. 3 (1969), 510-585. MR 0298508 (45:7560)
  • [44] R. T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré Anal. Non Linéaire 6 (1989), 449-482. MR 1019126 (90k:90140)
  • [45] R. J-B Wets, Convergence of convex functions, variational inequalities and convex optimization problems, Variational Inequalities and Complementarity Problems (R. Cottle, F. Gianessi, and J.-L. Lions, eds.), Wiley, 1980, pp. 375-403. MR 578760 (83a:90140)
  • [46] R. T. Rockafellar, Minimax theorems and conjugate saddle functions, Math. Scand. 14 (1964), 151-173. MR 0175037 (30:5223)
  • [47] H. Attouch and R. J.-B. Wets, A convergence theory for saddle functions, Trans. Amer. Math. Soc. 280 (1983), 1-41. MR 712247 (85f:49024)
  • [48] R. Cominetti, Analyse du second ordre de problèmes d'optimisation non différentiable, thèse, Université de Clermont-Ferrand, France, 1989.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 90C30, 49J52

Retrieve articles in all journals with MSC: 90C30, 49J52


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1990-1031242-0
Keywords: Nonsmooth analysis, epi-derivatives, sensitivity analysis, saddle functions, subgradients, epi-hypo-derivatives
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society