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

MathSciNet review:
936806

Full-text PDF Free Access

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]**Frank H. Clarke,*A new approach to Lagrange multipliers*, Math. Oper. Res.**1**(1976), no. 2, 165–174. MR**0414104****[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), no. 2, 245–250. MR**525025**, 10.1137/0317019**[4]**A. D. Ioffe,*Necessary and sufficient conditions for a local minimum. II. Conditions of Levitin-Miljutin-Osmolovskiĭ type*, SIAM J. Control Optim.**17**(1979), no. 2, 251–265. MR**525026**, 10.1137/0317020**[5]**A. D. Ioffe,*Necessary and sufficient conditions for a local minimum. III. Second order conditions and augmented duality*, SIAM J. Control Optim.**17**(1979), no. 2, 266–288. MR**525027**, 10.1137/0317021**[6]**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**, 10.1137/0320057**[7]**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**, 10.1016/0362-546X(82)90106-7**[8]**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**, 10.1137/0322025**[9]**R. W. Chaney,*On sufficient conditions in nonsmooth optimization*, Math. Oper. Res.**7**(1982), no. 3, 463–475. MR**667935**, 10.1287/moor.7.3.463**[10]**R. W. Chaney,*Second-order sufficiency conditions for nondifferentiable programming problems*, SIAM J. Control Optim.**20**(1982), no. 1, 20–33. MR**642177**, 10.1137/0320004**[11]**R. W. Chaney,*A general sufficiency theorem for nonsmooth nonlinear programming*, Trans. Amer. Math. Soc.**276**(1983), no. 1, 235–245. MR**684505**, 10.1090/S0002-9947-1983-0684505-9**[12]**Robin W. Chaney,*Second-order directional derivatives for nonsmooth functions*, J. Math. Anal. Appl.**128**(1987), no. 2, 495–511. MR**917384**, 10.1016/0022-247X(87)90202-2**[13]**Alfred Auslender,*Stability in mathematical programming with nondifferentiable data*, SIAM J. Control Optim.**22**(1984), no. 2, 239–254. MR**732426**, 10.1137/0322017**[14]**Jean-Pierre Aubin,*Lipschitz behavior of solutions to convex minimization problems*, Math. Oper. Res.**9**(1984), no. 1, 87–111. MR**736641**, 10.1287/moor.9.1.87**[15]**Alberto Seeger,*Second order directional derivatives in parametric optimization problems*, Math. Oper. Res.**13**(1988), no. 1, 124–139. MR**931491**, 10.1287/moor.13.1.124**[16]**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****[17]**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****[18]**A. Ben-Tal and J. Zowe,*Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems*, Math. Programming**24**(1982), no. 1, 70–91. MR**667940**, 10.1007/BF01585095**[19]**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****[20]**-,*Directional derivatives in nonsmooth optimization*, J. Optim. Theory Appl.**[21]**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**, 10.1287/moor.14.3.462**[22]**-,*Convex analysis*, Princeton Univ. Press, 1970.**[23]**R. T. Rockafellar and R. J.-B. Wets,*Linear-quadratic programming problems with stochastic penalties: the finite generation algorithm*, Stochastic optimization (Kiev, 1984) Lecture Notes in Control and Inform. Sci., vol. 81, Springer, Berlin, 1986, pp. 545–560. MR**891017**, 10.1007/BFb0007130**[24]**Magnus R. Hestenes,*Multiplier and gradient methods*, J. Optimization Theory Appl.**4**(1969), 303–320. MR**0271809****[25]**M. J. D. Powell,*A method for nonlinear constraints in minimization problems*, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283–298. MR**0272403****[26]**R. Tyrrell Rockafellar,*Augmented Lagrange multiplier functions and duality in nonconvex programming*, SIAM J. Control**12**(1974), 268–285. Collection of articles dedicated to the memory of Lucien W. Neustadt. MR**0384163****[27]**J. Sun,*On monotropic piecewise quadratic programming*, Ph.D. dissertation, Dept. of Appl. Math., Univ. of Washington, Seattle, 1986.**[28]**James V. Burke,*Second order necessary and sufficient conditions for convex composite NDO*, Math. Programming**38**(1987), no. 3, 287–302. MR**903768**, 10.1007/BF02592016**[29]**R. A. Wijsman,*Convergence of sequences of convex sets, cones and functions*, Bull. Amer. Math. Soc.**70**(1964), 186–188. MR**0157278**, 10.1090/S0002-9904-1964-11072-7**[30]**R. A. Wijsman,*Convergence of sequences of convex sets, cones and functions. II*, Trans. Amer. Math. Soc.**123**(1966), 32–45. MR**0196599**, 10.1090/S0002-9947-1966-0196599-8**[31]**Umberto Mosco,*Convergence of convex sets and of solutions of variational inequalities*, Advances in Math.**3**(1969), 510–585. MR**0298508****[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*, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR**773850****[34]**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****[35]**Hédy Attouch and Roger J.-B. Wets,*Approximation and convergence in nonlinear optimization*, Nonlinear programming, 4 (Madison, Wis., 1980) Academic Press, New York-London, 1981, pp. 367–394. MR**663386****[36]**R. T. Rockafellar and Roger J.-B. Wets,*Variational systems, an introduction*, Multifunctions and integrands (Catania, 1983) Lecture Notes in Math., vol. 1091, Springer, Berlin, 1984, pp. 1–54. MR**785574**, 10.1007/BFb0098800**[37]**C. Kuratowski,*Topologie*, PWN, Warsaw, 1958.**[38]**R. T. Rockafellar,*Generalized directional derivatives and subgradients of nonconvex functions*, Canad. J. Math.**32**(1980), no. 2, 257–280. MR**571922**, 10.4153/CJM-1980-020-7**[39]**Frank H. Clarke,*Generalized gradients and applications*, Trans. Amer. Math. Soc.**205**(1975), 247–262. MR**0367131**, 10.1090/S0002-9947-1975-0367131-6**[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), no. 2, 143–165. MR**600379**, 10.1007/BF00934107**[42]**R. T. Rockafellar,*Directionally Lipschitzian functions and subdifferential calculus*, Proc. London Math. Soc. (3)**39**(1979), no. 2, 331–355. MR**548983**, 10.1112/plms/s3-39.2.331

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:
http://dx.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