Research On Gradient Methods With Approximately Optimal Stepsizes

Large scale optimization is a subject widely emerged in these fields such as economics,engineering,management,military and space technology.Due to low storage,simple it-erate form and nice numerical performance,the gradient methods are a class of efficient algorithms for large scale unconstrained optimization,and have been applied widely to the fields such as image processing,compressed sensing,face recognition,text classification and machine learning.It is well-known that the choice of the stepsize is very crucial to the numerical performance of gradient methods.So,it is of theoretical and realistic signification to study the stepsizes of gradient methods and exploit some efficient gradient methods for large scale unconstrained optimization.Based on the existing work about gradient methods,we view the Barzilai-Borwein method from a new angle,introduce a new type of stepsize called approximately optimal stepsize for gradient method.It is remarkable that the steepest descent method and its modified versions,the BB method and its modified versions,and the gradient methods with fixed stepsize are all gradient methods with approximately optimal stepsize.We develop an efficient gradi-ent method with approximately optimal stepsize for strictly convex quadratic minimization,extend the gradient method with approximately optimal stepsize to general unconstrained optimization,and apply the idea of gradient method with approximately optimal stepsize to conjugate gradient method.The main contributions are listed as follows:1.A new type of stepsize called approximately optimal stepsize is introduced for gradient method.We design a scalar matrix based on some information at the most recent three iter-ations,update it by the BFGS formula and use the resulted matrix to construct a quadratic approximate model of the objective function at the current iteration.We obtain the approxi-mately optimal stepsize by minimizing the approximate model,present an efficient gradient method with approximately optimal stepsize for convex quadratic minimization,and estab-lish its convergence and R-linear convergence.The numerical results show the effectiveness of the proposed method.2.We extend the gradient method with approximately optimal stepsize for convex quadratic minimization to general unconstrained optimization,and present some efficient gradient methods with approximately optimal stepsize for unconstrained optimization.(1)We construct a new quadratic approximate model of the objective function at the cur-rent iterate,minimize it to generate the approximately optimal stepsize and exploit its some important properties.In addition,for the case of the nonnegative curvature,we also give a simple and efficient strategy for choosing the initial stepsize.We present an efficient gradient method with approximately optimal stepsize for unconstrained optimization by combining a nonmonotone Armijo line search,and establish the convergence of the proposed method.The numerical results show the effectiveness of the proposed method.(2)Using three modified BFGS formulae to update a scalar matrix,we obtain three modified quadratic approximate models of the objective function at the current iterate,minimize them to generate some approximately optimal stepsizes and exploit their some important proper-ties.In addition,for the case of the nonnegative curvature,we also construct a quadratic approximate model to generate approximately optimal stepsize.We present three efficient gradient methods with approximately optimal stepsizes for unconstrained optimization by combining a nonmonotone Armijo line search,and establish the convergence of the pro-posed method under weaker conditions.The numerical results show the effectiveness of the proposed method.(3)According to some properties of the objective function at the current iterate,we con-struct a tensor approximate model and some quadratic approximate models of the objective function at the current iterate,create the criteria for choosing different approximate mod-els and obtain approximately optimal stepsizes by minimizing the approximate models.We present an efficient gradient method with approximately optimal stepsizes by combining a nonmonotone Armijo line search,and establish the convergence of the proposed method un-der weak conditions.The numerical results show the effectiveness of the proposed method.(4)According to some properties of the objective function at the current iterate,we construct a conic approximate model and some quadratic approximate models of the objective function at the current iterate,create the criteria for choosing different approximate models and obtain approximately optimal stepsizes by minimizing the approximate models.We present an effi-cient gradient method with approximately optimal stepsizes(GM_AOS(cone))by combining a nonmonotone Armijo line search,and establish the convergence of GM_AOS(cone).The numerical results show that GM_AOS(cone)outperforms two famous conjugate gradient software packages CGOPT and CG_DESCENT(6.0)for the problem set collection given by Andrei,and is comparable with CG_DESCENT(5.0)and CGOPT for the CUTEst collection.3.According to some properties of the objective function at the current iterate,we construct different quadratic approximate models of the objective function over two dimensional space by using the idea of the gradient method with approximately optimal stepsize and some prop-erties of the linear conjugate gradient method.By minimizing the approximate models,we obtain the search direction satisfying the sufficient descent condition.We design a new strat-egy for choosing the initial stepsize,introduce Generalized Wolfe line search and present an efficient Barzilai-Borwein subspace minimization conjugate gradient method(SMCG_BB)for unconstrained optimization.We establish the convergence of SMCG_BB under weaker conditions and prove that SMCG-BB is R-linear convergent.The numerical results show that SMCG_BB outperforms some famous conjugate gradient software packages CGOPT and CG_DESCENT(5.3)for the problem set collection given by Andrei and the CUTEst collection.An important property of the approximately optimal stepsize is that it uses some second order or more order information about the objective function,which leads to that the ap-proximately optimal stepsize can satisfy directly the line search condition in most cases and thus the line search does not need to be evoked.As a consequence,the approximately opti-mal stepsize can reduce the computational cost greatly and thus is very efficient for gradient methods.The gradient methods with approximately optimal stepsize are a new class of gradient methods.Due to the simple search direction,the simple Armijo line search used which is easy to implement and the suprising numerical performance,the gradient meth-ods with approximately optimal stepsize are able to be a strong candidate for large scale unconstrained optimization and will be applied widely to many fields.