近些年来，众多学者提出基于新步长选择策略的加速梯度投影算法求解大规模优化问题。本文针对线性约束二次规划问题提出两种基于新步长的梯度投影算法。一种是基于采用自适应线搜索和Barzilai-Borwein步长的非单调投影算法。另一种是基于Yuan步长的单调投影算法。在较弱的假设条件下，给出这两种算法的全局收敛性。数值实验表明新算法比传统的梯度投影算法求解效率更高。
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.
[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.
