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
HTML articles powered by AMS MathViewer

by Claude Lemaréchal, François Oustry and Claudia Sagastizábal PDF

Trans. Amer. Math. Soc. 352 (2000), 711-729 Request permission

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.

References

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 10.1016/0022-247X(70)90078-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 10.1007/BF01585095
R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal. 9 (1985), no. 11, 1189–1209. MR 813653, DOI 10.1016/0362-546X(85)90030-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 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 10.1137/0328045
Andrew R. Conn, Constrained optimization using a nondifferentiable penalty function, SIAM J. Numer. Anal. 10 (1973), 760–784. MR 347374, DOI 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 10.1016/S0304-0208(08)72398-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 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 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 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 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 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 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 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 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 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é C Anal. Non Linéaire 6 (1989), no. suppl., 449–482. Analyse non linéaire (Perpignan, 1987). MR 1019126, DOI 10.1016/S0294-1449(17)30034-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 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