×

Globally convergent BFGS method for nonsmooth convex optimization. (English) Zbl 0986.90076

For the unconstrained minimization of a nonsmooth strongly convex function \(f:\mathbb{R}^n\to \mathbb{R}\), the authors apply the BFGS method to its Moreau-Yosida regularization. The algorithm they propose makes use of approximate values of the regularized function and of its gradient; it is proved to converge to the unique optimal solution.

MSC:

90C53 Methods of quasi-Newton type
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yosida, K., Functional Analysis, Springer Verlag, Berlin, Germany, 1964. · Zbl 0152.32102
[2] Moreau, J., Proximitéet Dualitédans un Espace Hilbertien, Bulletin de la Socièté Mathématique de France, Vol. 93, pp. 273–299, 1965.
[3] Hiriart-urruty, J., and LemarÉchal, C., Convex Analysis and Minimization Algorithms, Springer Verlag, Berlin, Germany, 1993. · Zbl 0795.49001
[4] LemarÉchal, C., and SagastizÁbal, C., Practical Aspects of the Moreau- Yosida Regularization, I: Theoretical Preliminaries, SIAM Journal on Optimization, Vol. 7, pp. 367–385, 1997. · Zbl 0876.49019
[5] qi, L., Second-Order Analysis of the Moreau-Yosida Regularization of a Convex Function, Preprint, School of Mathematics, University of New South Wales, Sydney, Australia, 1995.
[6] LemarÉchal, C., and SagastizÁbal, C., An Approach to Variable-Metric Bundle Methods, Proceedings of the 16th IFIP-TC7 Conference on Systems Modelling and Optimization, Edited by J. Henry and J. P. Yuvor, Springer Verlag, New York, NY, pp. 144–162, 1994. · Zbl 0811.90085
[7] Bonnans, J. F., Gilbert, J. C., LemarÉchal, C., and SagastizÁbal, C., A Family of Variable-Metric Proximal Methods, Mathematical Programming, Vol. 68, pp. 15–47, 1995. · Zbl 0832.90102
[8] Mifflin, R., A Quasi-Second-Order Proximal Bundle Algorithm, Mathematical Programming, Vol. 73, pp. 51–72, 1996. · Zbl 0848.90100
[9] LemarÉchal, C., and SagastizÁbal, C., Variable-Metric Bundle Methods: From Conceptual to Implementable Forms, Mathematical Programming, Vol. 76, pp. 393–410, 1997. · Zbl 0872.90072
[10] Fukushima, M., and Qi, L., A Globally and Superlinearly Convergent Algorithm for Nonsmooth Convex Minimization, SIAM Journal on Optimization, Vol. 6, pp. 1106–1120, 1996. · Zbl 0868.90109
[11] Qi, L., and Chen, X., A Preconditioned Proximal Newton Method for Nondifferentiable Convex Optimization, Mathematical Programming, Vol. 76, pp. 411–429, 1997. · Zbl 0871.90065
[12] Chen, X., and Fukushima, M., Proximal Quasi-Newton Methods for Nondifferentiable Convex Optimization, Mathematical Programming, Vol. 85, pp. 313–334, 1999. · Zbl 0946.90111
[13] Burke, J. V., and Qian, M., On the Superlinear Convergence of the Variable-Metric Proximal Point-Algorithm Using Broyden and BFGS Matrix Secant Updating, Mathematical Programming (to appear). · Zbl 1028.90086
[14] Qian, M., and Burke, J. V., On the Local Superlinear Convergence of a Matrix Secant Implementation of the Variable-Metric Proximal-Point Algorithm for Monotone Operators, Reformulation: Nonsmooth, Piecewise Smooth, Semismooth, and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Dordrecht, Holland, pp. 317–334, 1998.
[15] Mifflin, R., Sun, D., and Qi, L., Quasi-Newton Bundle-Type Methods for Nondifferentiable Convex Optimization, SIAM Journal on Optimization, Vol. 8, pp. 583–603, 1998. · Zbl 0927.65074
[16] Chen, X., Convergence of the BFGS Method for LC 1-Convex Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 34, pp. 2051–2063, 1996. · Zbl 0871.90062
[17] Ip, C. M., and Kyparisis, J., Local Convergence of Quasi-Newton Methods for B-Differentiable Equations, Mathematical Programming, Vol. 56, pp. 71–89, 1992. · Zbl 0761.90088
[18] Robinson, S. M., Local Structure of Feasible Sets in Nonlinear Programming, Part 3: Stability and Sensitivity, Mathematical Programming Study, Vol. 30, pp. 45–66, 1987. · Zbl 0629.90079
[19] Fukushima, M., A Descent Algorithm for Nonsmooth Convex Optimization, Mathematical Programming, Vol. 30, pp. 163–175, 1984. · Zbl 0545.90082
[20] Auslender, A., Numerical Methods for Nondifferentiable Convex Optimization, Mathematical Programming Study, Vol. 30, pp. 102–126, 1987. · Zbl 0616.90052
[21] Correa, R., and LemarÉchal, C., Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62, pp. 261–275, 1993. · Zbl 0805.90083
[22] Dennis, J. E., Jr., and Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1983. · Zbl 0579.65058
[23] Fletcher, R., Practical Methods of Optimization, 2nd Edition, John Wiley, Chichester, England, 1987. · Zbl 0905.65002
[24] Ortega, J. M., and Rheinboldt, W. C., Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, New York, NY, 1970. · Zbl 0241.65046
[25] Byrd, R. H., and Nocedal, J., A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Optimization, SIAM Journal on Numerical Analysis, Vol. 26, pp. 727–739, 1989. · Zbl 0676.65061
[26] Byrd, R. H., Nocedal, J., and Yuan, Y., Global Convergence of a Class of Quasi-Newton Methods on Convex Problems, SIAM Journal on Numerical Analysis, Vol. 24, pp. 1171–1190, 1987. · Zbl 0657.65083
[27] Powell, M. J. D., Some Global Convergence Properties of a Variable Metric Algorithm for Minimization without Exact Line Searches, Nonlinear Programming, Edited by R. W. Cottle and C. E. Lemke, American Mathematical Society, Providence, Rhode Island, pp. 53–72, 1976.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.