The -Lagrangian of a convex function
Authors:
Claude Lemaréchal, François Oustry and Claudia Sagastizábal
Journal:
Trans. Amer. Math. Soc. 352 (2000), 711-729
MSC (1991):
Primary 49J52, 58C20; Secondary 49Q12, 65K10
DOI:
https://doi.org/10.1090/S0002-9947-99-02243-6
Published electronically:
September 21, 1999
MathSciNet review:
1487623
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: At a given point , a convex function
is differentiable in a certain subspace
(the subspace along which
has 0-breadth). This property opens the way to defining a suitably restricted second derivative of
at
. We do this via an intermediate function, convex on
. We call this function the
-Lagrangian; it coincides with the ordinary Lagrangian in composite cases: exact penalty, semidefinite programming. Also, we use this new theory to design a conceptual pattern for superlinearly convergent minimization algorithms. Finally, we establish a connection with the Moreau-Yosida regularization.
- 1. Jean-Pierre Aubin, Contingent derivatives of set-valued maps and existence of solutions to nonlinear inclusions and differential inclusions, Mathematical analysis and applications, Part A, Adv. in Math. Suppl. Stud., vol. 7, Academic Press, New York-London, 1981, pp. 159–229. MR 634239
- 2. D. Azé, On the remainder of the first order development of convex functions, Ann. Sci. Math. Quebec 23 (1999), 1-13.
- 3. H. T. Banks and Marc Q. Jacobs, A differential calculus for multifunctions, J. Math. Anal. Appl. 29 (1970), 246–272. MR 265937, https://doi.org/10.1016/0022-247X(70)90078-8
- 4. 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, https://doi.org/10.1007/BF01585095
- 5. R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal. 9 (1985), no. 11, 1189–1209. MR 813653, https://doi.org/10.1016/0362-546X(85)90030-6
- 6. T. F. Coleman and A. R. Conn, Nonlinear programming via an exact penalty function: asymptotic analysis, Math. Programming 24 (1982), no. 2, 123–136. MR 674627, https://doi.org/10.1007/BF01585100
- 7. R. Cominetti and R. Correa, A generalized second-order derivative in nonsmooth optimization, SIAM J. Control Optim. 28 (1990), no. 4, 789–809. MR 1051624, https://doi.org/10.1137/0328045
- 8. Andrew R. Conn, Constrained optimization using a nondifferentiable penalty function, SIAM J. Numer. Anal. 10 (1973), 760–784. MR 347374, https://doi.org/10.1137/0710063
- 9. J.-B. Hiriart-Urruty, The approximate first-order and second-order directional derivatives for a convex function, Mathematical theories of optimization (Genova, 1981) Lecture Notes in Math., vol. 979, Springer, Berlin-New York, 1983, pp. 144–177. MR 713809
- 10. J.-B. Hiriart-Urruty, A new set-valued second order derivative for convex functions, FERMAT days 85: mathematics for optimization (Toulouse, 1985) North-Holland Math. Stud., vol. 129, North-Holland, Amsterdam, 1986, pp. 157–182. MR 874365, https://doi.org/10.1016/S0304-0208(08)72398-3
- 11. Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal, Convex analysis and minimization algorithms. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305, Springer-Verlag, Berlin, 1993. Fundamentals. MR 1261420
- 12. A. D. Ioffe, Nonsmooth analysis and the theory of fans, Convex analysis and optimization (London, 1980) Res. Notes in Math., vol. 57, Pitman, Boston, Mass.-London, 1982, pp. 93–117. MR 647480
- 13. Hidefumi Kawasaki, An envelope-like effect of infinitely many inequality constraints on second-order necessary conditions for minimization problems, Math. Programming 41 (1988), no. 1, (Ser. A), 73–96. MR 941318, https://doi.org/10.1007/BF01580754
- 14. C. Lemaréchal and C. Sagastizábal, More than first-order developments of convex functions: primal-dual relations, J. Convex Anal. 3 (1996), no. 2, 255–268. MR 1448055
- 15. Claude Lemaréchal and Claudia Sagastizábal, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optim. 7 (1997), no. 2, 367–385. MR 1443624, https://doi.org/10.1137/S1052623494267127
- 16. C. Lemaréchal and J. Zowe, The eclipsing concept to approximate a multi-valued mapping, Optimization 22 (1991), no. 1, 3–37. MR 1092640, https://doi.org/10.1080/02331939108843638
- 17.
R. Mifflin and C. Sagastizábal,
-decomposition derivatives for convex max-functions, Ill-Posed Problems and Variational Inequalities (R. Tichatschke and M. Théra, eds.) Lecture Notes, Springer-Verlag (to appear).
- 18. Boris S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings, J. Math. Anal. Appl. 183 (1994), no. 1, 250–288. MR 1273445, https://doi.org/10.1006/jmaa.1994.1144
- 19. Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273–299 (French). MR 201952
- 20.
F. Oustry, The
-Lagrangian of the maximum eigenvalue function, SIAM Journal of Optimization 9 (1999), 526-549.
- 21. Michael L. Overton and Robert S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, SIAM J. Matrix Anal. Appl. 16 (1995), no. 3, 697–718. MR 1337640, https://doi.org/10.1137/S089547989324598X
- 22. Michael L. Overton and Xian Jian Ye, Towards second-order methods for structured nonsmooth optimization, Advances in optimization and numerical analysis (Oaxaca, 1992) Math. Appl., vol. 275, Kluwer Acad. Publ., Dordrecht, 1994, pp. 97–109. MR 1282737
- 23. Jean-Paul Penot, Differentiability of relations and differential stability of perturbed optimization problems, SIAM J. Control Optim. 22 (1984), no. 4, 529–551. MR 747968, https://doi.org/10.1137/0322033
- 24. René A. Poliquin, Proto-differentiation of subgradient set-valued mappings, Canad. J. Math. 42 (1990), no. 3, 520–532. MR 1062743, https://doi.org/10.4153/CJM-1990-027-2
- 25. R. A. Poliquin and R. T. Rockafellar, Generalized Hessian properties of regularized nonsmooth functions, SIAM J. Optim. 6 (1996), no. 4, 1121–1137. MR 1416532, https://doi.org/10.1137/S1052623494279316
- 26. M. J. D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations, Nonlinear programming, 3 (Proc. Sympos., Special Interest Group Math. Programming, Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New York-London, 1978, pp. 27–63. MR 507858
- 27. Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353–367. MR 1216791, https://doi.org/10.1007/BF01581275
- 28. R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
- 29. 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
- 30. R. T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré Anal. Non Linéaire 6 (1989), no. suppl., 449–482. Analyse non linéaire (Perpignan, 1987). MR 1019126, https://doi.org/10.1016/S0294-1449(17)30034-3
- 31. R. T. Rockafellar, Generalized second derivatives of convex functions and saddle functions, Trans. Amer. Math. Soc. 322 (1990), no. 1, 51–77. MR 1031242, https://doi.org/10.1090/S0002-9947-1990-1031242-0
- 32. Kôsaku Yosida, Functional analysis, Die Grundlehren der Mathematischen Wissenschaften, Band 123, Academic Press, Inc., New York; Springer-Verlag, Berlin, 1965. MR 0180824
Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 49J52, 58C20, 49Q12, 65K10
Retrieve articles in all journals with MSC (1991): 49J52, 58C20, 49Q12, 65K10
Additional Information
Claude Lemaréchal
Affiliation:
INRIA, 655 avenue de l’Europe, 38330 Montbonnot, France
Email:
Claude.Lemarechal@inria.fr
François Oustry
Affiliation:
INRIA, 655 avenue de l’Europe, 38330 Montbonnot, France
Email:
Francois.Oustry@inria.fr
Claudia Sagastizábal
Affiliation:
INRIA, BP 105, 78153 Le Chesnay, France
Email:
Claudia.Sagastizabal@inria.fr
DOI:
https://doi.org/10.1090/S0002-9947-99-02243-6
Keywords:
Nonsmooth analysis,
generalized derivative,
second-order derivative,
composite optimization
Received by editor(s):
July 18, 1996
Received by editor(s) in revised form:
August 1, 1997
Published electronically:
September 21, 1999
Article copyright:
© Copyright 1999
American Mathematical Society