Abstract

We make use of VU\mathcal{VU}-space decomposition theory to connect three minimization-oriented objects. These objects are U\mathcal{U}-Lagrangians obtained from minimizing a function over V\mathcal{V}-space, proximal points depending on minimization over Rn=U⊕V\mathbb{R}^n = \mathcal{U} \oplus \mathcal{V}, and epi-derivatives determined by lower limits associated with epigraphs. We relate second-order epi-derivatives of a function to the Hessian of its associated U\mathcal{U}-Lagrangian. We also show that the function's proximal points are on a trajectory determined by certain V\mathcal{V}-space minimizers.

Author information

Contact details are reproduced from the original publication and may be historical.

Robert Mifflin

Dept. of Mathematics, Washington State University, Pullman, WA 99164-3113, U.S.A.

mifflin@math.wsu.edu

Claudia Sagastizábal

IMPA, Estrada Doña Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil
and: INRIA, BP 105, 78153 Le Chesnay, France

sagastiz@impa.br

Keywords

  • U-Lagrangian
  • proximal point
  • second-order epi-derivatives

Mathematics Subject Classification

90C31, 49J52, 65K10; 49J53

References

  1. J.-F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: A family of variable metric proximal methods, Math. Program., Ser. A 68(1) (1995) 15–47.https://doi.org/10.1007/BF01585756Google Scholar
  2. J. V. Burke, Maijian Qian: On the super-linear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating, Math. Program., Ser. A 88(1) (2000) 157–181.https://doi.org/10.1007/PL00011373Google Scholar
  3. A. Ben-Tal, J. Zowe: Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems, Math. Program. 24(1) (1982) 70–91.https://doi.org/10.1007/BF01585095Google Scholar
  4. R. Cominetti, R. Correa: A generalized second-order derivative in nonsmooth optimization, SIAM J. Control Optimization 28(4) (1990) 789–809.https://doi.org/10.1137/0328045Google Scholar
  5. X. Chen, M. Fukushima: Proximal quasi-Newton methods for nondifferentiable convex optimization, Math. Program., Ser. A 85(2) (1999) 313–334.https://doi.org/10.1007/s101070050059Google Scholar
  6. R. Correa, C. Lemaréchal: Convergence of some algorithms for convex minimization, Math. Program., Ser. B 62(2) (1993) 261–275.https://doi.org/10.1007/BF01585170Google Scholar
  7. R. Cominetti: On pseudo-differentiability, Trans. Amer. Math. Soc. 2324(2) (1991) 843–865.https://doi.org/10.1090/S0002-9947-1991-0992605-3Google Scholar
  8. M. Fukushima, L. Qi: A globally and superlinearly convergent algorithm for nonsmooth convex minimization, SIAM J. Optimization 6(4) (1996) 1106–1120.https://doi.org/10.1137/S1052623494278839Google Scholar
  9. W. L. Hare: The Quadratic Sub-Lagrangian of Prox-Regular Functions, M. Sc. Dissertation, Department of Mathematical and Statistical Sciences, University of Alberta, Canada (2000),available at http://www.cecm.sfu.ca/~whare.Google Scholar
  10. W. L. Hare: Recent functions and sets of smooth substructure: Relationships and examples, preprint, available at http://www.cecm.sfu.ca/~whare.Google Scholar
  11. W. L. Hare, A. S. Lewis: Identifying active contraints via partial smoothness and prox-regularity, J. Convex Analysis 11(2) (2003) 251–266.https://doi.org/10.68381/jca11017Google Scholar
  12. W. L. Hare, R. A. Poliquin: The quadratic sub-Lagrangian of a prox-regular function, Nonlinear Anal. 47(2) (2001) 1117–1128.https://doi.org/10.1016/S0362-546X(01)00251-6Google Scholar
  13. J.-B. Hiriart-Urruty: Refinements of necessary optimality conditions in nondifferentiable programming I, Appl. Math. Optimization 5 (1979) 63–82.https://doi.org/10.1007/BF01442544Google Scholar
  14. J.-B. Hiriart-Urruty: Refinements of necessary optimality conditions in nondifferentiable programming II, Math. Program. Study 19 (1982) 120–139.https://doi.org/10.1007/BFb0120985Google Scholar
  15. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms, Grundlehren der Mathematischen Wissenschaften 305-306, Springer, Berlin (1993) (two volumes).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  16. A. D. Ioffe: Variational analysis of a composite function: A formula for the lower second order epi-derivative, J. Math. Anal. Appl. (1991) 379–405.https://doi.org/10.1016/0022-247X(91)90312-NGoogle Scholar
  17. C. Lemaréchal: Extensions Diverses des Méthodes de Gradient et Applications, Thèse d’Etat, Université de Paris IX (1980).Google Scholar
  18. C. Lemaréchal, R. Mifflin: Global and superlinear convergence of an algorithm for one-dimensional minimization of convex functions, Math. Program. 24 (1982) 241–256.https://doi.org/10.1007/BF01585109Google Scholar
  19. C. Lemaréchal, F. Oustry, C. Sagastizábal: The U-Lagrangian of a convex function, Trans. Amer. Math. Soc. 352(2) (2000) 711–729.https://doi.org/10.1090/S0002-9947-99-02243-6Google Scholar
  20. C. Lemaréchal, C. Sagastizábal: An approach to variable metric bundle methods, in: Systems Modelling and Optimization, J. Henry, J.-P. Yvon (eds.), Lecture Notes in Control and Information Sciences 197, Springer (1994) 144–162.https://doi.org/10.1007/BFb0035464Google Scholar
  21. C. Lemaréchal, C. Sagastizábal: Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optimization 7(2) (1997) 367–385.https://doi.org/10.1137/S1052623494267127Google Scholar
  22. C. Lemaréchal, C. Sagastizábal: Variable metric bundle methods: From conceptual to implementable forms, Math. Program., Ser. B 76(3) (1997) 393–410.https://doi.org/10.1007/BF02614390Google Scholar
  23. R. Mifflin: On superlinear convergence in univariate nonsmooth minimization, Math. Program., Ser. A 49(2) (1991) 273–279.https://doi.org/10.1007/BF01588792Google Scholar
  24. R. Mifflin: A quasi-second-order proximal bundle algorithm, Math. Program., Ser. A 73(1) (1996) 51–72.https://doi.org/10.1007/BF02592098Google Scholar
  25. R. Mifflin, C. Sagastizábal: On VU-theory for functions with primal-dual gradient structure, SIAM J. Optimization 11(2) (2000) 547–571.https://doi.org/10.1137/S1052623499350967Google Scholar
  26. R. Mifflin, C. Sagastizábal: Proximal points are on the fast track, J. Convex Analysis 9(2) (2002) 563–579.https://doi.org/10.68381/jca09033Google Scholar
  27. R. Mifflin, C. Sagastizábal: On the relation between U-Hessians and second-order epiderivatives, European Journal of Operations Research 157 (2004) 28–38.https://doi.org/10.1016/j.ejor.2003.08.010Google Scholar
  28. R. Mifflin, C. Sagastizábal: Primal-dual gradient structured functions: Second-order results; links to epi-derivatives and partly smooth functions, SIAM J. Optimization 13(4) (2003) 1174–1194.https://doi.org/10.1137/S1052623402412441Google Scholar
  29. R. Mifflin, C. Sagastizábal: VU-Smoothness and proximal point results for nonconvex functions, Optimization Methods and Software 19 (2004) 463–478.https://doi.org/10.1080/10556780410001704902Google Scholar
  30. R. Mifflin, D. F. Sun, L. Q. Qi: Quasi-Newton bundle-type methods for nondifferentiable convex optimization, SIAM J. Optimization 8(2) (1998) 583–603.https://doi.org/10.1137/S1052623496303329Google Scholar
  31. B. Sh. Mordukhovich: Maximum principle in the problem of time optimal response with nonsmooth constraints, Prikl. Mat. Meh. 40(6) (1976) 1014–1023.https://doi.org/10.1016/0021-8928(76)90136-2Google Scholar
  32. J. M. Ortega, W. C. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York (1970).Google Scholar
  33. J.-P. Penot: Subhessians, superhessians and conjugation, Nonlinear Analysis: Theory, Methods and Applications 23(6) (1994) 689–702.https://doi.org/10.1016/0362-546X(94)90212-7Google Scholar
  34. R. A. Poliquin, R. T. Rockafellar: Second-order nonsmooth analysis in nonlinear programming, in: Recent Advances in Nonsmooth Optimization, World Sci. Publishing, River Edge (1995) 322–349.https://doi.org/10.1142/9789812812827_0018Google Scholar
  35. R. A. Poliquin, R. T. Rockafellar: Prox-regular functions in variational analysis, Trans. Amer. Math. Soc. 348(5) (1996) 1805–1838.https://doi.org/10.1090/S0002-9947-96-01544-9Google Scholar
  36. L. Qi, X. Chen: A preconditioning proximal Newton method for nondifferentiable convex optimization, Math. Program., Ser. B 76(3) (1997) 411–429.https://doi.org/10.1007/BF02614391Google Scholar
  37. L. Qi: Superlinearly convergent approximate Newton methods for LC 1 optimization problems, Math. Program., Ser. A 64(3) (1994) 277–294.https://doi.org/10.1007/BF01582577Google Scholar
  38. A. I. Rauf, M. Fukushima: Globally convergent BFGS method for nonsmooth convex optimization, J. Optim. Theory Appl. 104(3) (2000) 539–558.https://doi.org/10.1023/A:1004633524446Google Scholar
  39. S. M. Robinson: Local structure of feasible sets in nonlinear programming, Part III: Stability and sensitivity, Math. Program. Study 30 (1987) 45–66.https://doi.org/10.1007/BFb0121154Google Scholar
  40. R. T. Rockafellar: Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. Henri Poincaré, Anal. Non Linéaire 6 (1989) 449–482.https://doi.org/10.1016/s0294-1449(17)30034-3Google Scholar
  41. R. T. Rockafellar: Second-order optimality conditions in nonlinear programming obtained by way of epi-derivatives, Math. Oper. Res. 14 (1989) 462–484.https://doi.org/10.1287/moor.14.3.462Google Scholar
  42. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar

Suggested citation

R. Mifflin, C. Sagastizábal. “Relating 𝒰-Lagrangians to Second-Order Epi-Derivatives and Proximal Tracks.” Journal of Convex Analysis 12 (2005), No. 1, 81–93. https://doi.org/10.68381/jca12005

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2005. Rights now held by Banach Press LLC.