zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
Monotone projected gradient methods for large-scale box-constrained quadratic programming. (English) Zbl 1112.90056
Summary: Inspired by the success of the projected Barzilai-Borwein (PBB) method for large-scale box-constrained quadratic programming, we propose and analyze the monotone projected gradient methods in this paper. We show by experiments and analyses that for the new methods, it is generally a bad option to compute steplengths based on the negative gradients. Thus in our algorithms, some continuous or discontinuous projected gradients are used instead to compute the steplengths. Numerical experiments on a wide variety of test problems are presented, indicating that the new methods usually outperform the PBB method.

90C20Quadratic programming
Full Text: DOI
[1] Nocedal, J., Wright, S. J., Numerical Optimization, Springer Series in Operations Research, New York: Springer-Verlag, 1999. · Zbl 0930.65067
[2] Goldstein, A. A., Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 1964, 70: 709--710. · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[3] Levitin, E. S., Polyak, B. T., Constrained minimization problems, USSR Computational Mathematics and Mathematical Physics, 1966, 6: 1--50. · Zbl 0161.07002 · doi:10.1016/0041-5553(66)90114-5
[4] Burke, J. V., Moré, J. J., Exposing constraints, SIAM J. Optim., 1994, 4: 573--595. · Zbl 0809.65058 · doi:10.1137/0804032
[5] Conn, A. R., Gould, N. I. M., Toint, Ph. L., Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. Numer. Anal., 1988, 25: 433--460; 1989, 26: 764--767. · Zbl 0643.65031 · doi:10.1137/0725029
[6] Conn, A. R., Gould, N. I. M., Toint, Ph. L., Testing a class of algorithms for solving minimization problems with simple bounds on the variables, Mathematics of Computation, 1988, 50: 399--430. · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[7] Dunn, J. C., Gradient-related constrained minimization algorithms in function spaces: convergence properties and computational implications, in Large Scale Optimization: State of the Art (eds. Hager, W. W., Hearn, D. W., Pardalos, P. M.), Dordrecht: Kluwer Academic Publishers, 1994, 99--118.
[8] Moré, J. J., Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim., 1991, 13: 93--113. · Zbl 0752.90053 · doi:10.1137/0801008
[9] Barzilai, J., Borwein, J. M., Two-point step size gradient methods, IMA J. Numer. Anal., 1988, 8: 141--148. · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[10] Raydan, M., On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal., 1993, 13: 321--326. · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[11] Dai, Y. H., Liao, L.-Z., R-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal., 2002, 22: 1--10. · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[12] Grippo, L., Lampariello, F., Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 1986, 23: 707--716. · Zbl 0616.65067 · doi:10.1137/0723046
[13] Raydan, M., The Barzilai and Borwein method for the large scale unconstrained minimization problem, SIAM J. Optim., 1997, 7: 26--33. · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[14] Birgin, E. G., Martínez, J. M., Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 2000, 10: 1196--1211. · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[15] Birgin, E. G., Martínez, J. M., Raydan, M., Algorithm 813: SPG--Software for convex-constrained optimization, ACM Trans. Math. Software, 2001, 27: 340--349. · Zbl 1070.65547 · doi:10.1145/502800.502803
[16] Bongartz, I., Conn, A. R., Gould, N. I. M. et al., CUTE: Constrained and unconstrained testing environment, ACM Trans. Math. Software, 1995, 21: 123--160. · Zbl 0886.65058 · doi:10.1145/200979.201043
[17] Conn, A. R., Gould, N. I. M., Toint, Ph. L., LANCELOT: A FORTRAN package for large-scale nonlinear optimization (Release A), Springer Series in Computational Mathematics 17, New York: Springer Verlag, 1992. · Zbl 0761.90087
[18] Dai, Y. H., Fletcher, R., Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik, 2005, 100: 21--47. · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y
[19] Dai, Y. H., Yuan, Y., Analysis of monotone gradient methods, Journal of Industrial and Management Optimization, 2005, 1: 181--192. · Zbl 1071.65084
[20] Yuan, Y., A new stepsize for the steepest descent method, J. Comput. Math., 2006, 24: 149--156. · Zbl 1101.65067
[21] Bertsekas, D. P., Nonlinear Programming, Belmont (MA): Athena Scientific, 1995.
[22] Fletcher, R., On the Barzilai-Borwein method, Numerical Analysis Report NA/207, Department of Mathematics, University of Dundee, 2001. · Zbl 1118.90318
[23] Gould, N. I. M., Orban, D., Toint, Ph. L., CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 2003, 29: 373--394. · Zbl 1068.90526 · doi:10.1145/962437.962439