|
The -Lagrangian of a convex function
Author(s):
Claude
Lemaréchal;
François
Oustry;
Claudia
Sagastizábal
Journal:
Trans. Amer. Math. Soc.
352
(2000),
711-729.
MSC (1991):
Primary 49J52, 58C20;
Secondary 49Q12, 65K10
Posted:
September 21, 1999
Retrieve article in:
PDF
This article is available free of charge
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.
References:
- 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,
-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
-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
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:
10.1090/S0002-9947-99-02243-6
PII:
S 0002-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
Posted:
September 21, 1999
Copyright of article:
Copyright
1999,
American Mathematical Society
|