The 𝒰-Lagrangian of a convex function

Lemaréchal, Claude; Oustry, François; Sagastizábal, Claudia

doi:10.1090/S0002-9947-99-02243-6

The $\mathcal{U}$ -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 ${\overline{p}}$ , a convex function is differentiable in a certain subspace $\mathcal{U}$ (the subspace along which $\partial f({\overline{p}})$ has 0-breadth). This property opens the way to defining a suitably restricted second derivative of at ${\overline{p}}$ . We do this via an intermediate function, convex on $\mathcal{U}$ . We call this function the $\mathcal{U}$ -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, $\mathcal{VU}$ -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 $\cal U$ -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