新Armijo线搜索下的PRP共轭梯度法及其收敛性分析
|
摘要
优化算法研究,主要工作是给迭代点寻求可接受且有效的步长及可行的下降方向.在求解大规模无约束优化问题时,共轭梯度法被广泛应用.其中, Polak-Ribiere-Polyak方法 (简称:PRP方法)是众多共轭梯度法中数值表现相对较好的,但它在许多线搜索下并不具备全局收敛性,如何发挥PRP方法数值优良,而克服其收敛性差,是学者们致力探索的热点课题.本文提出新的PRP参数公式,并对Armijo线搜索方法进行修正,建立了新Armijo线搜索下的PRP共轭梯度算法,证明算法满足充分下降条件,并证明算法在适当条件下具有全局收敛性.
The optimization algorithm research focuses on finding an acceptable and effective step size and feasible descent direction. The conjugate gradient methods are widely used in solving the large-scale unconstrained optimization problems. Among them, Polak-Ribiere-Polyak method(PRP)has better numerical effect than other conjugate gradient methods. However, the global convergence has not been established for the PRP method with some inexact linear line search. How proposed new line search condition which was designed to get convergence theory to ensure the PRP method is globally convergent. At the same time, it remains its excellent numerical effect. In this paper, a new Armijo line searching method with a new parameter formula is proposed. The PRP conjugate gradient algorithm under the new Armijo line search is established. It is proved that the algorithm satisfies the sufficient descent condition and that the algorithm has global convergence under appropriate conditions.
The optimization algorithm research focuses on finding an acceptable and effective step size and feasible descent direction. The conjugate gradient methods are widely used in solving the large-scale unconstrained optimization problems. Among them, Polak-Ribiere-Polyak method(PRP)has better numerical effect than other conjugate gradient methods. However, the global convergence has not been established for the PRP method with some inexact linear line search. How proposed new line search condition which was designed to get convergence theory to ensure the PRP method is globally convergent. At the same time, it remains its excellent numerical effect. In this paper, a new Armijo line searching method with a new parameter formula is proposed. The PRP conjugate gradient algorithm under the new Armijo line search is established. It is proved that the algorithm satisfies the sufficient descent condition and that the algorithm has global convergence under appropriate conditions.
引文
[1]FLETCHER R,REEVES C M.Function minimization by conjugate gradients[J].Computer Journal,1964(7):149-154.
[2]HESTENES M R,STIEFEL E.Method of conjugate gradient for solving linear equations[J].Journal of Research National Bureau of Standards,1952(49):409-436.
[3]DAI Y H,YUAN Y.Convergence properties of the conjugate descent method[J].Advances in Mathematics,1996,25:552-562.
[4]POLYAK P T.The conjugate gradient method in extremal problems[J].Ussr Computation Mathematics and Mathematical physics,1969(9):94-112.
[5]AL-BAALI M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].Ima Journal and Numerical Analysis,1985(5):121-124.
[6]GILBERT J C,NOCEDAL J.Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal of Optimization,1992,2(1):21-42.
[7]WEI Z X,LI G Y,QI L Q.Global convergence of the Polak-Ribiere-Polyak conjugate method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems[J].Mathematics of Computation,2008,77(264):2173-2193.
[8]吴庆军.一个全局收敛的共轭梯度法[J].广西工学院学报,2004,15(3):89-92.
[9]朱孝晶,周圆兀,龚熠,等.基于多样性优化策略的粒子群算法[J].广西工学院学报,2001,22(1):74-77.
[2]HESTENES M R,STIEFEL E.Method of conjugate gradient for solving linear equations[J].Journal of Research National Bureau of Standards,1952(49):409-436.
[3]DAI Y H,YUAN Y.Convergence properties of the conjugate descent method[J].Advances in Mathematics,1996,25:552-562.
[4]POLYAK P T.The conjugate gradient method in extremal problems[J].Ussr Computation Mathematics and Mathematical physics,1969(9):94-112.
[5]AL-BAALI M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].Ima Journal and Numerical Analysis,1985(5):121-124.
[6]GILBERT J C,NOCEDAL J.Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal of Optimization,1992,2(1):21-42.
[7]WEI Z X,LI G Y,QI L Q.Global convergence of the Polak-Ribiere-Polyak conjugate method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems[J].Mathematics of Computation,2008,77(264):2173-2193.
[8]吴庆军.一个全局收敛的共轭梯度法[J].广西工学院学报,2004,15(3):89-92.
[9]朱孝晶,周圆兀,龚熠,等.基于多样性优化策略的粒子群算法[J].广西工学院学报,2001,22(1):74-77.