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 $\bar {p}$, a convex function $f$ is differentiable in a certain subspace $\mathcal {U}$ (the subspace along which $\partial f(\bar {p})$ has 0-breadth). This property opens the way to defining a suitably restricted second derivative of $f$ at $\bar {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.

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

D. Azé, On the remainder of the first order development of convex functions, Ann. Sci. Math. Quebec 23 (1999), 1–13.

H. T. Banks and Marc Q. Jacobs, A differential calculus for multifunctions, J. Math. Anal. Appl. 29 (1970), 246–272. MR 265937, DOI https://doi.org/10.1016/0022-247X%2870%2990078-8

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 https://doi.org/10.1007/BF01585095

R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal. 9 (1985), no. 11, 1189–1209. MR 813653, DOI https://doi.org/10.1016/0362-546X%2885%2990030-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, DOI https://doi.org/10.1007/BF01585100

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, DOI https://doi.org/10.1137/0328045

Andrew R. Conn, Constrained optimization using a nondifferentiable penalty function, SIAM J. Numer. Anal. 10 (1973), 760–784. MR 347374, DOI https://doi.org/10.1137/0710063

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

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, DOI https://doi.org/10.1016/S0304-0208%2808%2972398-3

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

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

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, DOI https://doi.org/10.1007/BF01580754

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

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, DOI https://doi.org/10.1137/S1052623494267127

C. Lemaréchal and J. Zowe, The eclipsing concept to approximate a multi-valued mapping, Optimization 22 (1991), no. 1, 3–37. MR 1092640, DOI https://doi.org/10.1080/02331939108843638

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

Boris S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings, J. Math. Anal. Appl. 183 (1994), no. 1, 250–288. MR 1273445, DOI https://doi.org/10.1006/jmaa.1994.1144

Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273–299 (French). MR 201952

F. Oustry, The $\mathcal {U}$-Lagrangian of the maximum eigenvalue function, SIAM Journal of Optimization 9 (1999), 526–549.

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, DOI https://doi.org/10.1137/S089547989324598X

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

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, DOI https://doi.org/10.1137/0322033

René A. Poliquin, Proto-differentiation of subgradient set-valued mappings, Canad. J. Math. 42 (1990), no. 3, 520–532. MR 1062743, DOI https://doi.org/10.4153/CJM-1990-027-2

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, DOI https://doi.org/10.1137/S1052623494279316

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

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, DOI https://doi.org/10.1007/BF01581275

R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683

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

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, DOI https://doi.org/10.1016/S0294-1449%2817%2930034-3

R. T. Rockafellar, Generalized second derivatives of convex functions and saddle functions, Trans. Amer. Math. Soc. 322 (1990), no. 1, 51–77. MR 1031242, DOI https://doi.org/10.1090/S0002-9947-1990-1031242-0

Kôsaku Yosida, Functional analysis, Die Grundlehren der Mathematischen Wissenschaften, Band 123, Academic Press, Inc., New York; Springer-Verlag, Berlin, 1965. MR 0180824