Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
Published electronically: September 21, 1999
MathSciNet review: 1487623
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: At a given point ${\overline{p}}$, a convex function $f$ 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 $f$ 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.

References [Enhancements On Off] (What's this?)

  • 1. J.P. Aubin, Contingent derivatives of set-valued maps and existence of solutions to nonlinear inclusions and differential equations, Mathematical Analysis and Applications (L. Nachbin, ed.), Academic Press, 1981, pp. 159-229. MR 83m:58014
  • 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 M.Q. Jacobs, A differential calculus for multifunctions, Journal of Mathematical Analysis and Applications 29 (1970), 246-272. MR 42:846
  • 4. A. Ben-Tal and J. Zowe, Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems, Mathematical Programming 24 (1982), no. 1, 70-91. MR 83m:90075
  • 5. R.W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Analysis: Theory, Methods and Applications 9 (1985), no. 11, 1189-1209. MR 87c:49018
  • 6. T.F. Coleman and A.R. Conn, Nonlinear programming via an exact penalty function: asymptotic analysis, Mathematical Programming 24 (1982), 123-136. MR 84e:90087a
  • 7. R. Cominetti and R. Correa, A generalized second-order derivative in nonsmooth optimization, SIAM Journal on Control and Optimization 28 (1990), no. 4, 789-809. MR 91h:49017
  • 8. A.R. Conn, Constrained optimization using a nondifferentiable penalty function, SIAM Journal on Numerical Analysis 10 (1973), no. 4, 760-784. MR 49:12094
  • 9. J.-B. Hiriart-Urruty, The approximate first-order and second-order directional derivatives for a convex function, Mathematical Theories of Optimization (J.-P. Cecconi and T. Zolezzi, eds.), Lecture Notes in Mathematics, no. 979, Springer-Verlag, 1983, pp. 144-177. MR 84i:49029
  • 10. -, A new set-valued second order derivative for convex functions, Fermat Days 85: Mathematics for Optimization (J.B. Hiriart-Urruty, ed.), Mathematics Studies, no. 129, North-Holland, 1986, pp. 157-182. MR 88d:90092
  • 11. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms, Grundlehren der mathematischen Wissenschaften, no. 305-306, Springer-Verlag, 1993. MR 95m:90001; MR 95m:90002
  • 12. A.D. Ioffe, Nonsmooth analysis and the theory of fans, Convex Analysis and Optimization (J.P. Aubin and R.B. Vinter, eds.), Pitman, 1982, pp. 93-118. MR 83h:58012
  • 13. M. Kawasaki, An envelope-like effect of infinitely many inequality constraints on second-order conditions for minimization problems, Mathematical Programming 41 (1988), no. 1, 73-96. MR 89d:90191
  • 14. C. Lemaréchal and C. Sagastizábal, More than first-order developments of convex functions: primal-dual relations, Journal of Convex Analysis 3 (1996), 255-268. MR 98k:49048
  • 15. -, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM Journal on Optimization 7 (1997), no. 2, 367-385. MR 98e:49085
  • 16. C. Lemaréchal and J. Zowe, The eclipsing concept to approximate a multi-valued mapping, Optimization 22 (1991), no. 1, 3-37. MR 92a:49024
  • 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. B.S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings, Journal of Mathematical Analysis and Applications 183 (1993), no. 1, 250-288. MR 95i:49029
  • 19. J.J. Moreau, Proximité et dualité dans un espace hilbertien, Bulletin de la Société Mathématique de France 93 (1965), 273-299. MR 34:1829
  • 20. F. Oustry, The $\cal U$-Lagrangian of the maximum eigenvalue function, SIAM Journal of Optimization 9 (1999), 526-549.
  • 21. M. L. Overton and R.S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, SIAM J. Matrix Anal. Appl. 16 (1995), 697-718. MR 96c:65062
  • 22. M.L. Overton and X.J. Ye, Towards second-order methods for structured nonsmooth optimization, Advances in Optimization and Numerical Analysis (S. Gomez and J.P. Hennart, eds.), Kluwer, 1994, pp. 97-109. MR 95e:90099
  • 23. J.-P. Penot, Differentiability of relations and differential stability of perturbed optimization problems, SIAM Journal on Control and Optimization 22 (1984), no. 4, 529-551, 26 (1988), 997-998. MR 85i:49041; MR 89d:49027.
  • 24. R.A. Poliquin, Proto-differentiation of subgradient set-valued mappings, Canadian Journal of Mathematics 42 (1990), no. 3, 520-532. MR 91g:49007
  • 25. R.A. Poliquin and R.T. Rockafellar, Generalized hessian properties of regularized nonsmooth functions, SIAM Journal on Optimization 6 (1996), no. 4, 1121-1137. MR 97j:49025
  • 26. M.J.D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations, Nonlinear Programming 3 (O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, eds.), 1978, pp. 27-63. MR 80c:90138
  • 27. L.Q. Qi and D.F. Sun, A nonsmooth version of Newton's method, Mathematical Programming 58 (1993), no. 3, 353-367. MR 94b:90077
  • 28. R.T. Rockafellar, Convex analysis, Princeton Mathematics Ser., no. 28, Princeton University Press, 1970. MR 43:445
  • 29. -, Maximal monotone relations and the second derivatives of nonsmooth functions, Annales de l'Institut Henri Poincaré, Analyse non linéaire 2 (1985), no. 3, 167-186. MR 87c:49021
  • 30. -, Proto-differentiability of set-valued mappings and its applications in optimization, Annales de l'Institut Henri Poincaré, Analyse Non Linéaire 6 (1989), 449-482. MR 90k:90140
  • 31. -, Generalized second derivatives of convex function and saddle functions, Transactions of the American Mathematical Society 322 (1990), no. 1, 51-78. MR 91b:90190
  • 32. K. Yosida, Functional analysis, Springer Verlag, 1965. MR 31:5054

Similar Articles

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

François Oustry
Affiliation: INRIA, 655 avenue de l’Europe, 38330 Montbonnot, France

Claudia Sagastizábal
Affiliation: INRIA, BP 105, 78153 Le Chesnay, France

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