zbMATH — the first resource for mathematics

A family of variable metric proximal methods. (English) Zbl 0832.90102
Summary: We consider conceptual optimization methods combining two ideas: the Moreau-Yosida regularization in convex analysis, and quasi-Newton approximations of smooth functions. We outline several approaches based on this combination, and establish their global convergence. Then we study theoretically the local convergence properties of one of these approaches, which uses quasi-Newton updates of the objective function itself. Also, we obtain a globally and superlinearly convergent BFGS proximal method. At each step of our study, we single out the assumptions that are useful to derive the result concerned.

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
52A41 Convex functions and convex programs in convex geometry
90C25 Convex programming
49J52 Nonsmooth analysis
Full Text: DOI
[1] A. Auslender, ”Numerical methods for non-differentiable convex optimization,”Mathematical Programming Study 30 (1987) 102–126. · Zbl 0616.90052 · doi:10.1007/BFb0121157
[2] C.G. Broyden, J.E. Dennis and J.J. Moré, ”On the local and superlinear convergence of quasi-Newton methods,”Journal of the Institute of Mathematics and its Applications 12 (1973) 223–245. · Zbl 0282.65041 · doi:10.1093/imamat/12.3.223
[3] R.H. Byrd and J. Nocedal, ”A tool for the analysis of quasi-Newton methods with application to unconstrained minimization,”SIAM Journal on Numerical Analysis 26 (1989) 727–739. · Zbl 0676.65061 · doi:10.1137/0726042
[4] F.H. Clarke,Optimization and Non-Smooth Analysis (Wiley, New York, 1983). · Zbl 0582.49001
[5] R. Correa and C. Lemaréchal, ”Convergence of some algorithms for convex minimization,”Mathematical Programming 62 (1993) 261–275. · Zbl 0805.90083 · doi:10.1007/BF01585170
[6] J.E. Dennis and J.J. Moré, ”A characterization of superlinear convergence and its application to quasi-Newton methods,”Mathematics of Computation 28 (1974) 549–560. · Zbl 0282.65042 · doi:10.1090/S0025-5718-1974-0343581-1
[7] J.E. Dennis and J.J. Moré, ”Quasi-Newton methods, motivation and theory,”SIAM Review 19 (1977) 46–89. · Zbl 0356.65041 · doi:10.1137/1019005
[8] J.E. Dennis and R.B. Schnabel, ”A view of unconstrained optimization,” in: G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Handbook in Operations Research and Management Science, Vol. 1 (North-Holland, Amsterdam, 1989) 1–72.
[9] M. Fukushima, ”A descent algorithm for non-smooth convex programming,”Mathematical Programming 30 (1984) 163–175. · Zbl 0545.90082 · doi:10.1007/BF02591883
[10] J.Ch. Gilbert and C. Lemaréchal, ”Some numerical experiments with variable-storage quasi-Newton algorithms,”Mathematical Programming 45 (1989) 407–435. · Zbl 0694.90086 · doi:10.1007/BF01589113
[11] W.A. Gruver and E. Sachs,Algorithmic Methods in Optimal Control, Research Notes in Mathematics No. 47 (Pitman, London, 1980). · Zbl 0456.49001
[12] S.M. Grzegórski, ”Orthogonal projections on convex sets for Newton-like methods”,SIAM Journal on Numerical Analysis 22 (1985) 1208–1219. · Zbl 0593.65044 · doi:10.1137/0722074
[13] J.B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms, Vols. 1 and 2 (Springer-Verlag, Berlin, Heidelberg, New York, 1993).
[14] C.-M. Ip and J. Kyparisis, ”Local convergence of quasi-Newton methods for B-differentiable equations,”Mathematical Programming 56 (1992) 71–89. · Zbl 0761.90088 · doi:10.1007/BF01580895
[15] K.C. Kiwiel, ”Proximity control in bundle methods for convex non-differentiable minimization,”Mathematical Programming 46 (1990) 105–122. · Zbl 0697.90060 · doi:10.1007/BF01585731
[16] B. Kummer, ”Newton’s method based on generalized derivatives for non-smooth functions: convergence analysis,” in: W. Oettli and D. Pallaschke, eds.,Advances in Optimization, Lecture Notes in Economics and Mathematical Systems No. 382 (Springer-Verlag, Berlin, Heidelberg, New York, 1991) 171–194.
[17] C. Lemaréchal, ”A view of line-searches,” in: A Auslender, W. Oettli and J. Stoer, eds.,Optimization and Optimal Control, Lecture Notes in Control and Information Science No. 30 (Springer-Verlag, Berlin, Heidelberg, New York, 1981) 59–78.
[18] C. Lemaréchal and C. Sagastizábal, ”An approach to variable metric bundle methods,” in: J. Henry and J.P. Yvor, eds.,Proceedings IFIP Conference Systems Modelling and Optimization, Lecture Notes in Control and Information Sciences No. 197 (Springer-Verlag, New York, 1994). · Zbl 0811.90085
[19] B. Martinet, ”Régularisation d’inéquations variationelles par approximations successives,”Revue Française d’Informatique et Recherche Opérationelle R-3 (1970) 154–179.
[20] R. Mifflin, ”A quasi-second-order proximal bundle algorithm,” Technical Report 93-3, University of Washington (Pullman, Washington, 1993). · Zbl 0848.90100
[21] J.J. Moreau, ”Proximité et dualité dans un espace hilbertien,”Bulletin de la Société Mathématique de France 93 (1965) 273–299.
[22] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Non-linear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[23] J.-S. Pang, ”Newton’s method for B-differentiable equations,”Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311
[24] J.S. Pang and L.Q. Qi, ”Non-smooth equations: motivation and algorithms,”SIAM Journal on Optimization 3 (1993) 443–465. · Zbl 0784.90082 · doi:10.1137/0803021
[25] M.J.D. Powell, ”Some global convergence properties of a variable metric algorithm for minimization without exact line searches,” in: R.W. Cottle and C.E. Lemke, eds.,Non-linear Programming, SIAM–AMS Proceedings No. 9 (American Mathematical Society, Providence, RI, 1976). · Zbl 0338.65038
[26] L. Qi and J. Sun, ”A non-smooth version of Newton’s method,”Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090 · doi:10.1007/BF01581275
[27] L.Q. Qi, ”Convergence analysis of some algorithms for solving non-smooth equations,”Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227
[28] M. Qian, ”The variable metric proximal point algorithm: global and super-linear convergence,” Manuscript GN-50, University of Washington, Department of Mathematics (Seattle, WA, 1992).
[29] S.M. Robinson, ”Local structure of feasible sets in non-linear programming, part III: stability and sensitivity,”Mathematical Programming Study 30 (1987) 45–66. · Zbl 0629.90079 · doi:10.1007/BFb0121154
[30] R.T. Rockafellar,Convex Analysis (Princeton University, Princeton, NJ, 1970).
[31] R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053 · doi:10.1137/0314056
[32] C.A. Sagastizábal, ”Quelques méthodes numériques d’optimisation. Application en gestion de stocks,” Ph.D. thesis, University of Paris I, Panthéon-Sorbonne (Paris, 1993).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.