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)

 
 

 

First- and second-order epi-differentiability in nonlinear programming


Author: R. T. Rockafellar
Journal: Trans. Amer. Math. Soc. 307 (1988), 75-108
MSC: Primary 90C48; Secondary 49A52, 58C20, 90C30
DOI: https://doi.org/10.1090/S0002-9947-1988-0936806-9
MathSciNet review: 936806
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Problems are considered in which an objective function expressible as a max of finitely many $ {C^2}$ functions, or more generally as the composition of a piecewise linear-quadratic function with a $ {C^2}$ mapping, is minimized subject to finitely many $ {C^2}$ constraints. The essential objective function in such a problem, which is the sum of the given objective and the indicator of the constraints, is shown to be twice epi-differentiable at any point where the active constraints (if any) satisfy the Mangasarian-Fromovitz qualification. The epi-derivatives are defined by taking epigraphical limits of classical first-and second-order difference quotients instead of pointwise limits, and they reveal properties of local geometric approximation that have not previously been observed.


References [Enhancements On Off] (What's this?)

  • [1] F. H. Clarke, A new approach to Lagrange multipliers, Math. Oper. Res. 1 (1976), 165-174. MR 0414104 (54:2209)
  • [2] -, Nonsmooth analysis and optimization, Wiley, 1983.
  • [3] A. D. Ioffe, Necessary and sufficient conditions for a local minimum. I: A reduction theorem and first order conditions, SIAM J. Control Optim. 17 (1979), 245-250. MR 525025 (82j:49005a)
  • [4] -, Necessary and sufficient conditions for a local minimum. II: Conditions of Levilin-Miljutin-Osmolovskii type, SIAM J. Control Optim. 17 (1979), 251-265. MR 525026 (82j:49005b)
  • [5] -, Necessary and sufficient conditions for a local minimum. III: Second order conditions and augmented duality, SIAM J. Control Optim. 17 (1979), 266-288. MR 525027 (82j:49005c)
  • [6] J.-B. Hiriart-Urruty, Approximating a second order directional derivative for nonsmooth convex functions, SIAM J. Control Optim. 20 (1982), 783-807. MR 675570 (84k:49021)
  • [7] -, Limiting behavior of the approximate first and second order directional derivatives for a convex function, Nonlinear Anal. 6 (1982), 1309-1326. MR 684967 (85f:58009)
  • [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] R. W. Chaney, On sufficient conditions in nonsmooth optimization, Math. Oper. Res. 7 (1982), 463-475. MR 667935 (83m:49021)
  • [10] -, Second-order sufficient conditions for nondifferentiable programming problems, SIAM J. Control Optim. 20 (1982), 20-33. MR 642177 (83j:90077)
  • [11] -, A general sufficiency theorem for nonsmooth nonlinear programming, Trans. Amer. Math. Soc. 276 (1983), 235-245. MR 684505 (84d:90092)
  • [12] -, Second-order directional derivatives for nonsmooth functions, J. Math. Anal. Appl. 128 (1987), 495-511. MR 917384 (89c:90092)
  • [13] A. Auslender, Stability in mathematical programming with nondifferentiable data, SIAM J. Control Optim. 22 (1984), 239-254. MR 732426 (85d:90082)
  • [14] J. P. Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984), 87-111. MR 736641 (86f:90119)
  • [15] A. Seeger, Second-order directional derivatives in parametric optimization problems, Math. Oper. Res. (to appear). MR 931491 (89d:90217)
  • [16] R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré 2 (1985), 167-184. MR 797269 (87c:49021)
  • [17] A. Ben-Tal, Second order theory for extremum problems, Systems Analysis and External Methods (A. V. Fiacco and K. Kostaneta, eds.), Lecture Notes in Economics and Math. Sciences, Springer-Verlag, 1980, pp. 336-356. MR 563871 (83c:90143)
  • [18] A. Ben-Tal and J. Zowe, Necessary and sufficient conditions for a class of nonsmooth minimization problems, Math. Programming 24 (1982), 70-91. MR 667940 (83m:90075)
  • [19] -, A unified theory of first and second order conditions for extremum problems in topological vector spaces, Math. Programming Stud. 19 (1982), 39-76. MR 669725 (84d:90090)
  • [20] -, Directional derivatives in nonsmooth optimization, J. Optim. Theory Appl.
  • [21] R. T. Rockafellar, Second-order optimality conditions in nonlinear programming obtained by way of epi-derivatives, Math. Oper. Res. (forthcoming). MR 1008425 (91b:49022)
  • [22] -, Convex analysis, Princeton Univ. Press, 1970.
  • [23] R. T. Rockafellar and R. J.-B. Wets, Linear-quadratic programming with stochastic penalties: the finite generation algorithm, Stochastic Optimization (V. Arkin, A. Shiraeu and R. J.-B. Wets, eds.), Lecture Notes in Control and Information Sciences, No. 81, Springer-Verlag, 1986, pp. 545-560. MR 891017 (88f:90120)
  • [24] M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303-320. MR 0271809 (42:6690)
  • [25] M. J. D. Powell, A method for nonlinear optimization in minimization problems, Optimization (R. Fletcher, ed.), Academic Press, 1969. MR 0272403 (42:7284)
  • [26] R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control 12 (1974), 268-285. MR 0384163 (52:5040)
  • [27] J. Sun, On monotropic piecewise quadratic programming, Ph.D. dissertation, Dept. of Appl. Math., Univ. of Washington, Seattle, 1986.
  • [28] J. Burke, Second order necessary and sufficient conditions for convex composite $ NDO$, Math. Prog. 38 (1987), 287-302. MR 903768 (89d:90181)
  • [29] R. A. Wijsman, Convergence of sequences of convex sets, cones and functions. I, Bull. Amer. Math. Soc. 70 (1964), 186-188. MR 0157278 (28:514)
  • [30] -, Convergence of sequences of convex sets, cones and functions. II, Trans. Amer. Math. Soc. 123 (1966), 32-45. MR 0196599 (33:4786)
  • [31] U. Mosco, Convergence of convex sets and solutions to variational inequalities, Adv. in Math. 3 (1969), 510-585. MR 0298508 (45:7560)
  • [32] E. DeGiorgi, Convergence problems for junctionals and operators, Recent Methods in Non-Linear Analysis (E. DeGiorgi, E. Magenes and U. Mosco, eds.), Pitagoro Editrice, Bologna, 1980.
  • [33] H. Attouch, Variational convergence for functions and operators, Pitman, London, 1984. MR 773850 (86f:49002)
  • [34] R. J.-B. Wets, Convergence of convex functions, variational inequalities and convex optimization problems, Variational Inequalities and Complementary Problems (R. Cottle, F. Gianessi and J.-L. Lions, eds.), Wiley, 1980, pp. 405-419. MR 578760 (83a:90140)
  • [35] H. Attouch and R. J.-B. Wets, Approximation and convergence in nonlinear optimization, Nonlinear Programming 4, (O. L. Mangasarian et al., eds.), Academic Press, 1981, pp. 367-394. MR 663386 (83k:90090)
  • [36] R. T. Rockafellar and R. J.-B. Wets, Variational systems, an introduction, Multifunctions and Integrands (G. Salinetti, ed.), Lecture Notes in Math., vol. 1091, Springer-Verlag, 1984, pp. 1-54. MR 785574 (86h:90116)
  • [37] C. Kuratowski, Topologie, PWN, Warsaw, 1958.
  • [38] R. T. Rockafellar, Generalized directional derivatives and subgradients of nonconvex functions, Canad. J. Math. 37 (1980), 257-280. MR 571922 (81f:49006)
  • [39] F. H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247-262. MR 0367131 (51:3373)
  • [40] O. L. Mangasarian and S. Fromovitz, The Fritz John conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl. 17 (1967), 73-74.
  • [41] A. Ben-Tal, Second-order and related extremality conditions in nonlinear programming, J. Optim. Theory Appl. 31 (1980), 143-165. MR 600379 (83g:90115)
  • [42] R. T. Rockafellar, Directionally Lipschitzian functions and subdifferential calculus, Proc. London Math. Soc. 39 (1979), 339-355. MR 548983 (80j:46070)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 90C48, 49A52, 58C20, 90C30

Retrieve articles in all journals with MSC: 90C48, 49A52, 58C20, 90C30


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0936806-9
Keywords: Nonlinear programming, nonsmooth programming, epi-convergence, epi-derivatives, generalized second derivatives
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society