Recently, researchers proposed many accelerated project gradient methods based on new step length choice rules for large scale optimization problems. In this paper, we propose two project gradient methods with variants of new selection rules for quadratic programming with linear equality constraints. One is a non-monotone project gradient method for which an adaptive line search method is adopted and the Barzilai-Borwein step size is applied, and the other is a monotoneproject gradient method with Yuan step size. We give the global convergence of these two methods under mild assumptions. Numerical experiments indicate that both the new methods are more efficient than traditional project gradient methods.
LI Mingqiang
,
GUO Tiande
,
HAN Congying
. New project gradient methods for quadratic programming with linear equality constraints[J]. Journal of University of Chinese Academy of Sciences, 2018
, 35(3)
: 289
-296
.
DOI: 10.7523/j.issn.2095-6134.2018.03.001
[1] Barzilai J, Borwein J M. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8(1):141-148.
[2] Zhou B, Gao L, Dai Y H. Gradient methods with adaptive step-sizes[J]. Computational Optimization and Applications, 2006, 35(1):69-86.
[3] Raydan M. On the Barzilai and Borwein choice of steplength for the gradient method[J]. IMA Journal of Numerical Analysis, 1993, 13(3):321-326.
[4] Dai Y H, Liao L Z. R-linear convergence of the Barzilai and Borwein gradient method[J]. IMA Journal of Numerical Analysis, 2002, 22(1):1-10.
[5] Dai Y H, Fletcher R. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds[J]. Mathematical Programming, 2006, 106(3):403-421.
[6] Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem[J]. SIAM Journal on Optimization, 1997, 7(1):26-33.
[7] Yuan Y. Gradient methods for large scale convex quadratic functions[M]//Optimization and Regularization for Computational Inverse Problems and Applications. Berlin:Springer Heidelberg, 2010:141-155.
[8] Yuan Y. A new stepsize for the steepest descent method[J]. Journal of Computational Mathematics, 2006:149-156.
[9] Dai Y, Yuan Y X. Analysis of monotone gradient methods[J]. Journal of Industrial and Management Optimization, 2005, 1(2):181.
[10] Dai Y H, Fletcher R. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming[J]. Numerische Mathematik, 2005, 100(1):21-47.
[11] Hager W W, Zhang H. A new active set algorithm for box constrained optimization[J]. SIAM Journal on Optimization, 2006, 17(2):526-557.
[12] Zhou B, Gao L, Dai Y. Monotone projected gradient methods for largescale box-constrained quadratic programming[J]. Science in China Series A, 2006, 49(5):688-702.
[13] De Asmundis R, di Serafino D, Riccio F, et al. On spectral properties of steepest descent methods[J]. IMA Journal of Numerical Analysis, 2013:drs056.
[14] Zanni L, Serafini T, Zanghirati G. Parallel software for training large scale support vector machines on multiprocessor systems[J]. Journal of Machine Learning Research, 2006, 7(7):1467-1492.
[15] Serafini T, Zanghirati G, Zanni L. Parallel decomposition approaches for training support vector machines[J]. Advances in Parallel Computing, 2004, 13:259-266.
[16] Zanghirati G, Zanni L. A parallel solver for large quadratic programs in training support vector machines[J]. Parallel computing, 2003, 29(4):535-551.
[17] Grippo L, Lampariello F, Lucidi S. A nonmonotone line search technique for Newton's method[J]. SIAM Journal on Numerical Analysis, 1986, 23(4):707-716.
