zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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:
65K05Mathematical programming (numerical methods)
90C20Quadratic programming
90C06Large-scale problems (mathematical programming)
Software:
CONV_QP; GPDT
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)
[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
[16]Fletcher, R.: On the Barzilai-Borwein Method. Research report NA/207, Department of Mathematics, University of Dundee, 2001
[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)
[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
[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) · 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
[30]Toint, Ph.L.: A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Prog. 77, 69-94 (1997)
[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