Abstract

For a convex function, we consider a space decomposition that allows us to identify a subspace on which a Lagrangian related to the function appears to be smooth. We study a particular trajectory, that we call a fast track, on which a certain second-order expansion of the function can be obtained. We show how to obtain such fast tracks for a general class of convex functions having primal-dual gradient structure. Finally, we show that for a point near a minimizer its corresponding proximal point is on the fast track.

Author information

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

Robert Mifflin

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

mifflin@math.wsu.edu

Claudia Sagastizábal

National Institute of Pure and Applied Mathematics, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil
and: INRIA, BP 105, 78153 Le Chesnay, France

sagastiz@impa.br

Keywords

  • Convex minimization
  • proximal points
  • second-order derivatives
  • VU-decomposition

Mathematics Subject Classification

49K35, 49M27; 65K10, 90C25

References

  1. A. Auslender: Numerical methods for nondifferentiable convex optimization, Math. Programming Stud. 30 (1987) 102–126.https://doi.org/10.1007/BFb0121157Google Scholar
  2. D. P. Bertsekas: Nonlinear Programming, Athena Scientific (1995).Google Scholar
  3. M. Fukushima: A descent algorithm for nonsmooth convex optimization, Math. Program. 30 (1984) 163–175.https://doi.org/10.1007/BF02591883Google Scholar
  4. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I & II, Grund. der math. Wiss. 305–306, Springer-Verlag (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  5. A. S. Lewis: Active sets, nonsmoothness and sensitivity, SIAM Journal on Optimization, to appear.Google Scholar
  6. A. S. Lewis, M. L. Overton:. Eigenvalue optimization, Acta Numerica (1996) 149–190.https://doi.org/10.1017/S0962492900002646Google Scholar
  7. 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
  8. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4(R-3) (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  9. R. Mifflin: A quasi-second-order proximal bundle algorithm, Math. Program. 73(1) (1996) 51–72.https://doi.org/10.1007/BF02592098Google Scholar
  10. R. Mifflin, C. Sagastizábal: VU-decomposition derivatives for convex max-functions, in: Ill-posed Variational Problems and Regularization Techniques 477, Lecture Notes in Economics and Mathematical Systems, R. Tichatschke, M. Théra (eds.), Springer-Verlag, Berlin, Heidelberg (1999) 167–186.https://doi.org/10.1007/978-3-642-45780-7_11Google Scholar
  11. R. Mifflin, C. Sagastizábal: Functions with primal-dual gradient structure and U-Hessians, in: Nonlinear Optimization and Related Topics, Applied Optimization 36, G. Di Pillo, F. Giannessi (eds.), Kluwer Academic Publishers B.V. (2000) 219–233.https://doi.org/10.1007/978-1-4757-3226-9_12Google Scholar
  12. R. Mifflin, C. Sagastizábal: On VU-theory for functions with primal-dual gradient structure, SIAM Journal on Optimization 11(2) (2000) 547–571.https://doi.org/10.1137/S1052623499350967Google Scholar
  13. R. Mifflin, C. Sagastizábal: A VU -proximal point algorithm for minimization, in: “http://www.sci.wsu.edu/math/faculty/mifflin/” (2001).Google Scholar
  14. J. J. Moreau: Proximité et dualité dans un espace hilbertien, Bulletin de la Société Mathématique de France 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  15. F. Oustry: The U-Lagrangian of the maximum eigenvalue function, SIAM Journal on Optimization 9 (1999) 526–549.https://doi.org/10.1137/S1052623496311776Google Scholar
  16. F. Oustry: A second-order bundle method to minimize the maximum eigenvalue function, Math. Program. 89(1), Ser. A (2000) 1–33.https://doi.org/10.1007/PL00011388Google Scholar
  17. M. L. Overton, R. S. Womersley: Second derivatives for optimizing eigenvalues of symmetric matrices, Journal of Mathematical Analysis and Applications 3 (July 1995) 667–718.https://doi.org/10.1137/S089547989324598XGoogle Scholar
  18. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  19. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grund. der math. Wiss. 317, Springer-Verlag (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  20. A. Shapiro, M. K. H. Fan: On eigenvalue optimization, SIAM Journal on Optimization 5 (1995) 552–569.https://doi.org/10.1137/0805028Google Scholar
  21. K. Yosida: Functional Analysis, Springer-Verlag (1964).https://doi.org/10.1007/978-3-642-52814-9Google Scholar

Suggested citation

R. Mifflin, C. Sagastizábal. “Proximal Points are on the Fast Track.” Journal of Convex Analysis 9 (2002), No. 2, 563–579. https://doi.org/10.68381/jca09033

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2002. Rights now held by Banach Press.