A Calculus of EPI-Derivatives Applicable to Optimization

Poliquin, R. A. ; Rockafellar, R. T.

Canadian journal of mathematics, Tome 45 (1993) no. 4, pp. 879-896

Résumé

When an optimization problem is represented by its essential objective function, which incorporates constraints through infinite penalties, first- and secondorder conditions for optimality can be stated in terms of the first- and second-order epi-derivatives of that function. Such derivatives also are the key to the formulation of subproblems determining the response of a problem's solution when the data values on which the problem depends are perturbed. It is vital for such reasons to have available a calculus of epi-derivatives. This paper builds on a central case already understood, where the essential objective function is the composite of a convex function and a smooth mapping with certain qualifications, in order to develop differentiation rules covering operations such as addition of functions and a more general form of composition. Classes of "amenable" functions are introduced to mark out territory in which this sharper form of nonsmooth analysis can be carried out.

Détail

DOI : 10.4153/CJM-1993-050-7

Mots-clés : 90C48, 49A52, 58C20, 90C30, epi-derivatives, generalized second derivatives, amenable sets and functions, nonsmooth analysis, composite optimization, parametric optimization, sensitivity analysis

Bibliographie

[1] 1. Clarke, F. H., Generalized gradients and applications, Transactions Amer. Math. Soc. 205(1975), 247–262. Google Scholar

[2] 2. Clarke, F. H., Optimization and Nonsmooth Analysis, Wiley, 1983. Google Scholar

[3] 3. Clarke, F. H., Methods of Dynamic and Nonsmooth Optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, 57, SIAM Publications, Philadelphia, PA, 1989. Google Scholar

[4] 4. Cominetti, R., On Pseudo-differentiability, Transactions Amer. Math. Soc, 324(1991), 843–865. Google Scholar

[5] 5. Cominetti, R. and Correa, R., A generalized second order derivative in nonsmooth optimization, SIAM J. Control Opt. 28(1990), 789–809. Google Scholar

[6] 6. Do, C. N., Generalized second derivatives of convex functions in reflexive Banach spaces, Transactions Amer. Math. Soc, to appear. Google Scholar

[7] 7. Ioffe, A. D., Variational analysis of a composite function: a formula for the lower second order directional derivative, J. Math. Anal. Appl., 160(1991), 379–405. Google Scholar

[8] 8. Ioffe, A. D., Variational analysis of a composite function: perturbations, value function and sensitivity. Google Scholar

[9] 9. McLinden, L. and R. C. Bergstrom, Preservation of convergence of convex sets and functions, Transactions Amer. Math. Soc. 268(1981), 127–142. Google Scholar

[10] 10. Poliquin, R. A., Proto-differentiation of subgradient set-valued mappings, Canadian J. Math 42( 1990), 520- 532. 11 , An extension ofAttouch 's Theorem and its application to second-order epi-differentiation of convex composite functions, Trans. Amer. Math. Soc. 322(1992), 861–874. Google Scholar

[13] 13. Robinson, S. M., Some continuity properties of polyhedral multifunctions, Math. Programming Study 14 (1981), 206–214. Google Scholar

[12] 12. Poliquin, R. A. and Rockafellar, R. T., Differentiability of solution mappings and sensitivity analysis in parametric optimization, preprint. Google Scholar

[14] 14. Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, NJ, 1970. Google Scholar

[15] 15. Rockafellar, R. T., Directionally Lipschitzian functions and subdifferential calculus, Proc. London Math. Soc. 39 (1979), 331–355. Google Scholar

[16] 16. Rockafellar, R. T., First- and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc. 307(1988),75–107. Google Scholar

[17] 17. Rockafellar, R. T., Proto-differentiability of set-valued mappings and its applications in optimization. In: Analyse Non Linéaire, (editor H. Attouch et al.), Gauthier-Villars, Paris (1989), 449-482. Google Scholar

[18] 18. Rockafellar, R. T., Second-order optimality conditions in nonlinear programming obtained by way ofepi-derivatives, Math, of Open Research 14(1989), 462–484. Google Scholar

[19] 19. Rockafellar, R. T., Generalized second derivatives of convex functions and saddle functions, Transactions Amer. Math. Soc. 320(1990), 810–822. Google Scholar

[20] 20. Rockafellar, R. T., Nonsmooth analysis and parametric optimization. In: Methods of Nonconvex Analysis., (editor A. Cellina), Springer-Verlag Lecture Notes in Math. (1446), (1990), 137-151. Google Scholar

[21] 21. Rockafellar, R. T., Dualization of subgradient conditions for optimality. Google Scholar

[22] 22. Sun, J., On Monotropic Piecewise quadratic Programming, dissertation, Department of Applied Math., University of Washington, August, 1986. Google Scholar

[23] 23. Hiriart-Urruty, J.-B., Calculus rules on the approximate second order directional derivative of a convex Junction, SIAM J. Control Opt. 22 (1984), 381–404. Google Scholar

[24] 24. Hiriart-Urruty, J.-B. and Seeger, A., Calculus rules on a new set-valued second order derivative for convex functions, Nonlinear Analysis Th. Meth. Appl. 13(1989), 721–738. Google Scholar

[25] 25. Ward, D. E. and Borwein, J. M., Nonsmooth calculus infinite dimensions, SIAM J. Control Opt. 25(1987), 1312–1340 Google Scholar