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

Rockafellar, R. T.

doi:10.1090/S0002-9947-1988-0936806-9

First- and second-order epi-differentiability in nonlinear programming
HTML articles powered by AMS MathViewer

by R. T. Rockafellar

Trans. Amer. Math. Soc. 307 (1988), 75-108

DOI: https://doi.org/10.1090/S0002-9947-1988-0936806-9

PDF | Request permission

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

Frank H. Clarke, A new approach to Lagrange multipliers, Math. Oper. Res. 1 (1976), no. 2, 165–174. MR 414104, DOI 10.1287/moor.1.2.165

Nonsmooth analysis and optimization

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, DOI 10.1137/0317019
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, DOI 10.1137/0317019
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, DOI 10.1137/0317019
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, 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
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
R. W. Chaney, Second-order sufficiency conditions for nondifferentiable programming problems, SIAM J. Control Optim. 20 (1982), no. 1, 20–33. MR 642177, DOI 10.1137/0320004
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
Robin W. Chaney, Second-order directional derivatives for nonsmooth functions, J. Math. Anal. Appl. 128 (1987), no. 2, 495–511. MR 917384, DOI 10.1016/0022-247X(87)90202-2
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
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
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
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
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, Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems, Math. Programming 24 (1982), no. 1, 70–91. MR 667940, DOI 10.1007/BF01585095
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

Directional derivatives in nonsmooth optimization

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

Convex analysis

R. T. Rockafellar and R. J.-B. Wets, Linear-quadratic programming problems with stochastic penalties: the finite generation algorithm, Stochastic optimization (Kiev, 1984) Lect. Notes Control Inf. Sci., vol. 81, Springer, Berlin, 1986, pp. 545–560. MR 891017, DOI 10.1007/BFb0007130
Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
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
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

On monotropic piecewise quadratic programming

James V. Burke, Second order necessary and sufficient conditions for convex composite NDO, Math. Programming 38 (1987), no. 3, 287–302. MR 903768, DOI 10.1007/BF02592016
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

Convergence problems for junctionals and operators

H. Attouch, Variational convergence for functions and operators, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR 773850
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
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
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, DOI 10.1007/BFb0098800

Topologie

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
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

The Fritz John conditions in the presence of equality and inequality constraints

17

A. Ben-Tal, Second-order and related extremality conditions in nonlinear programming, J. Optim. Theory Appl. 31 (1980), no. 2, 143–165. MR 600379, DOI 10.1007/BF00934107
R. T. Rockafellar, Directionally Lipschitzian functions and subdifferential calculus, Proc. London Math. Soc. (3) 39 (1979), no. 2, 331–355. MR 548983, DOI 10.1112/plms/s3-39.2.331