×
Zhou, Bin; Gao, Li; Dai, Yuhong

Monotone projected gradient methods for large-scale box-constrained quadratic programming. (English) Zbl 1112.90056

Sci. China, Ser. A 49, No. 5, 688-702 (2006).
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.

Cited in 6 Documents

MSC:

90C20 Quadratic programming

Keywords:

projected gradients; monotone gradient methods; box-constrained quadratic programming; large-scale problems

Software:

CUTEr; LANCELOT; SifDec; SPG; CUTE
PDF BibTeX XML Cite
\textit{B. Zhou} et al., Sci. China, Ser. A 49, No. 5, 688--702 (2006; Zbl 1112.90056)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[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
[3] Levitin, E. S., Polyak, B. T., Constrained minimization problems, USSR Computational Mathematics and Mathematical Physics, 1966, 6: 1–50. · Zbl 0161.07002
[4] Burke, J. V., Moré, J. J., Exposing constraints, SIAM J. Optim., 1994, 4: 573–595. · Zbl 0809.65058
[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
[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
[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
[9] Barzilai, J., Borwein, J. M., Two-point step size gradient methods, IMA J. Numer. Anal., 1988, 8: 141–148. · Zbl 0638.65055
[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
[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
[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
[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
[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
[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
[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
[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
[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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.