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 functions, or more generally as the composition of a piecewise linear-quadratic function with a mapping, is minimized subject to finitely many 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.

**[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*, 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)**

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