1678Accesses
Summary.
This paper studies projected Barzilai-Borwein (PBB) methods for large-scale box-constrained quadratic programming. Recent work on this method has modified the PBB method by incorporating the Grippo-Lampariello-Lucidi (GLL) nonmonotone line search, so as to enable global convergence to be proved. We show by many numerical experiments that the performance of the PBB method deteriorates if the GLL line search is used. We have therefore considered the question of whether the unmodified method is globally convergent, which we show not to be the case, by exhibiting a counter example in which the method cycles. A new projected gradient method (PABB) is then considered that alternately uses the two Barzilai-Borwein steplengths. We also give an example in which this method may cycle, although its practical performance is seen to be superior to the PBB method. With the aim of both ensuring global convergence and preserving the good numerical performance of the unmodified methods, we examine other recent work on nonmonotone line searches, and propose a new adaptive variant with some attractive features. Further numerical experiments show that the PABB method with the adaptive line search is the best BB-like method in the positive definite case, and it compares reasonably well against the GPCG algorithm of Moré and Toraldo. In the indefinite case, the PBB method with the adaptive line search is shown on some examples to find local minima with better solution values, and hence may be preferred for this reason.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Akaike, H.: On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Statist. Math. Tokyo11, 1–17 (1959)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal.8, 141–148 (1988)
Bertsekas, D.P.: On the Goldstein-Levitin-Polyak gradient projection method. IEEE Transactions on Automatic Control21, 174–184 (1976)
Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim.10, 1196–1211 (2000)
Birgin, E.G., Martínez, J.M., Raydan, M.: Inexact spectral projected gradient methods on convex sets. IMA J. Numer. Anal.23, 539–559 (2003)
Brendel, M.: On two algorithms for the minimization of box constrained quadratic functions. MS344 honours project, Department of Mathematics, University of Dundee, 2001
Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Mathematical Programming39, 93–116 (1987)
Dai, Y.H.: Alternate step gradient method. Optimization52, 395–415 (2003)
Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Research report NA/212, Department of Mathematics, University of Dundee, 2003 (accepted by Mathematical Programming)
Dai, Y.H., Liao, L.-Z.:R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal.26, 1–10 (2002)
Dai, Y.H., Yuan, J.Y., Yuan, Y.Y.: Modified two-point stepsize gradient methods for unconstrained optimization. Computational Optimization and Applications22, 103–109 (2002)
Dai, Y.H., Zhang, H.C.: An adaptive two-point stepsize gradient algorithm. Numerical Algorithms27, 377–385 (2001)
De Angelis, P.L., Toraldo, G.: On the identification property of a projected gradient method. SIAM J. Numer. Anal.30, 1483–1497 (1993)
Dembo, R.S., Tulowitzki, U.: On the minimization of quadratic functions subject to box constraints. Working Paper 71, School of Organization and Management, Yale University, New Haven, CT, 1983
Demyanov, V.F., Rubinov, A.R.: Approximate methods in optimization problems. Elsevier, New York, 1970
Fletcher, R.: On the Barzilai-Borwein Method. Research report NA/207, Department of Mathematics, University of Dundee, 2001
Friedlander, A., Martínez, J.M.: On the maximization of a concave quadratic function with box constraints. SIAM J. Optim.4, 204–212 (1994)
Friedlander, A., Martínez, J.M., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal.36, 275–289 (1999)
Galligani, E., Ruggiero, V., Zanni, L.: Variable projection methods for large-scale quadratic optimization in data analysis applications. In: Equilibrium Problems and Variational Models, F. Giannessi, A. Maugeri, P.M. Pardalos (eds.), Nonconvex Optim. and Its Applic., Kluwer Academic PUbl. To appear, 2002
Goldstein, A.A.: Convex programming in Hilbert space. Bulletin of the American Mathematical Society70, 709–710 (1964)
Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal.23, 707–716 (1986)
Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Computational Optimization and Applications23, 143–169 (2002)
Levitin, E.S., Polyak, B.T.: Constrained minimization problems. USSR Computational Mathematics and Mathematical Physics6, 1–50 (1966)
Moré, J., Toraldo, G.: Algorithms for bound constrained quadratic programming problems. Numer. Math.55, 377–400 (1989)
Moré, J., Toraldo, G.: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim.1, 93–113 (1991)
Polyak, B.T.: The conjugate gradient method in extremal problems. USSR Comput. Math. and Math. Phys.9, 94–112 (1969)
Raydan, M.: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal.13, 321–326 (1993)
Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim.7, 26–33 (1997)
Serafini, T., Zanghirati, G., Zanni, L.: Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines. Research report, 2003
Toint, Ph.L.: A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Prog.77, 69–94 (1997)
Wright, S.J.: Implementing proximal point methods for linear programming. Journal of Optimization Theory and Applications65, 531–554 (1990)
Yang, E.K., Tolle, J.W.: A class of methods for solving large, convex quadratic programs subject to box constraints. Math. Prog.51, 223–228 (1991)
Zanghirati, G., Zanni, L.: A parallel solver for large quadratic programs in training support vector machines. Parallel Computing. To appear, 2003
Author information
Authors and Affiliations
State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, PO Box 2719, Beijing, 100080, PR China
Yu-Hong Dai
Department of Mathematics, University of Dundee, Dundee, DD1 4HN, Scotland, UK
Roger Fletcher
- Yu-Hong Dai
You can also search for this author inPubMed Google Scholar
- Roger Fletcher
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toYu-Hong Dai.
Additional information
This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grant (no. 10171104).
Acknowledgement The authors would like to thank the two anonymous referees for their useful suggestions and comments.
Rights and permissions
About this article
Cite this article
Dai, YH., Fletcher, R. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming.Numer. Math.100, 21–47 (2005). https://doi.org/10.1007/s00211-004-0569-y
Received:
Revised:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative