×

Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. (English) Zbl 1068.65073

Summary: The authors study projected Barzilai-Borwein (PBB) methods [cf. J. Barzilai and J. M. Borwein, IMA J. Numer. Anal. 8, No. 1, 141–148 (1988; Zbl 0638.65055)] 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 [cf. L. Grippo, F. Lampariello, and S. Lucidi, SIAM J. Numer. Anal. 23, 707–716 (1986; Zbl 0616.65067)] 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 PBB-like method in the positive definite case, and it compares reasonably well against the GPCG algorithm of J. J. Moré and G. Toraldo [SIAM J. Optim. 1, No. 1, 93–113 (1991; Zbl 0752.90053)]. 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.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming

Software:

CONV_QP; GPDT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akaike, H.: On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Statist. Math. Tokyo 11, 1-17 (1959) · Zbl 0100.14002 · doi:10.1007/BF01831719
[2] Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[3] Bertsekas, D.P.: On the Goldstein-Levitin-Polyak gradient projection method. IEEE Transactions on Automatic Control 21, 174-184 (1976) · Zbl 0326.49025 · doi:10.1109/TAC.1976.1101194
[4] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196-1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[5] 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) · Zbl 1047.65042 · doi:10.1093/imanum/23.4.539
[6] Brendel, M.: On two algorithms for the minimization of box constrained quadratic functions. MS344 honours project, Department of Mathematics, University of Dundee, 2001
[7] Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Mathematical Programming 39, 93-116 (1987) · Zbl 0634.90064 · doi:10.1007/BF02592073
[8] Dai, Y.H.: Alternate step gradient method. Optimization 52, 395-415 (2003) · Zbl 1056.65055 · doi:10.1080/02331930310001611547
[9] 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) · Zbl 1099.90038
[10] Dai, Y.H., Liao, L.-Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 26, 1-10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[11] Dai, Y.H., Yuan, J.Y., Yuan, Y.Y.: Modified two-point stepsize gradient methods for unconstrained optimization. Computational Optimization and Applications 22, 103-109 (2002) · Zbl 1008.90056 · doi:10.1023/A:1014838419611
[12] Dai, Y.H., Zhang, H.C.: An adaptive two-point stepsize gradient algorithm. Numerical Algorithms 27, 377-385 (2001) · Zbl 0992.65063 · doi:10.1023/A:1013844413130
[13] De Angelis, P.L., Toraldo, G.: On the identification property of a projected gradient method. SIAM J. Numer. Anal. 30, 1483-1497 (1993) · Zbl 0802.65080 · doi:10.1137/0730077
[14] 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
[15] Demyanov, V.F., Rubinov, A.R.: Approximate methods in optimization problems. Elsevier, New York, 1970 · Zbl 0217.46203
[16] Fletcher, R.: On the Barzilai-Borwein Method. Research report NA/207, Department of Mathematics, University of Dundee, 2001 · Zbl 1118.90318
[17] Friedlander, A., Martínez, J.M.: On the maximization of a concave quadratic function with box constraints. SIAM J. Optim. 4, 204-212 (1994) · Zbl 0801.65058
[18] Friedlander, A., Martínez, J.M., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36, 275-289 (1999) · Zbl 0940.65032 · doi:10.1137/S003614299427315X
[19] 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 · Zbl 1129.90335
[20] Goldstein, A.A.: Convex programming in Hilbert space. Bulletin of the American Mathematical Society 70, 709-710 (1964) · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[21] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton?s method. SIAM J. Numer. Anal. 23, 707-716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046
[22] Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Computational Optimization and Applications 23, 143-169 (2002) · Zbl 1028.90061 · doi:10.1023/A:1020587701058
[23] Levitin, E.S., Polyak, B.T.: Constrained minimization problems. USSR Computational Mathematics and Mathematical Physics 6, 1-50 (1966) · Zbl 0161.07002 · doi:10.1016/0041-5553(66)90114-5
[24] Moré, J., Toraldo, G.: Algorithms for bound constrained quadratic programming problems. Numer. Math. 55, 377-400 (1989) · Zbl 0675.65061 · doi:10.1007/BF01396045
[25] Moré, J., Toraldo, G.: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1, 93-113 (1991) · Zbl 0752.90053 · doi:10.1137/0801008
[26] Polyak, B.T.: The conjugate gradient method in extremal problems. USSR Comput. Math. and Math. Phys. 9, 94-112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4
[27] Raydan, M.: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13, 321-326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[28] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[29] Serafini, T., Zanghirati, G., Zanni, L.: Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines. Research report, 2003 · Zbl 1054.65062
[30] Toint, Ph.L.: A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Prog. 77, 69-94 (1997) · Zbl 0891.90153
[31] Wright, S.J.: Implementing proximal point methods for linear programming. Journal of Optimization Theory and Applications 65, 531-554 (1990) · Zbl 0676.90042 · doi:10.1007/BF00939565
[32] 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) · Zbl 0737.90046 · doi:10.1007/BF01586934
[33] Zanghirati, G., Zanni, L.: A parallel solver for large quadratic programs in training support vector machines. Parallel Computing. To appear, 2003 · Zbl 1054.65062
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.