Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization
Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization
复制标题
DOI：
10.1016/j.ejor.2009.11.030
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
N. Andrei
中科院分区：
文献类型：
--
作者：
N. Andrei
提出了一种求解无约束优化问题的加速缩放无记忆BFGS预条件共轭梯度算法。其基本思想是在共轭梯度法的框架下，将缩放无记忆BFGS方法与预处理技术相结合。前置条件也是一个缩放的无内存BFGS矩阵，当Beale-Powell重启准则成立时，前置条件被重置。选择缩放梯度的参数作为谱梯度。对于步长计算，该方法的优点是，在共轭梯度算法中，步长可能与1相差两个数量级，并且有不可预测的变化趋势。因此，我们提出了一种能够提高算法效率的加速方案。在一般假设下，证明了该方法是全局收敛的。结果表明，对于一致凸函数，加速算法的收敛性仍然是线性的，但函数值的约简得到了显著改善。在温和条件下，算法对强凸函数是全局收敛的。750个无约束优化测试问题的计算结果表明，这种新的加速缩放共轭梯度算法大大优于已知的共轭梯度方法：SCALCG [3-6], CONMIN by Shanno and Phua (1976,1978)[42,43], Hestenes and Stiefel (1952) [25], polak - ribi<s:1> - polyak (1969) [32,33], Dai and Yuan (2001) [17], Dai and Liao (2001) (t=1)[14]，充分下降条件共轭梯度[7]，hybrid Dai and Yuan (2001) [17], hybrid Dai and Yuan zero (2001) [17], CG_DESCENT by Hager and Zhang(2005, 2006)[22,23]，以及拟牛顿LBFGS法[26]和截断牛顿法Nash(1985)[27]。
An accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for solving unconstrained optimization problems is presented. The basic idea is to combine the scaled memoryless BFGS method and the preconditioning technique in the frame of the conjugate gradient method. The preconditioner, which is also a scaled memoryless BFGS matrix, is reset when the Beale–Powell restart criterion holds. The parameter scaling the gradient is selected as a spectral gradient. For the steplength computation the method has the advantage that in conjugate gradient algorithms the step lengths may differ from 1 by two order of magnitude and tend to vary unpredictably. Thus, we suggest an acceleration scheme able to improve the efficiency of the algorithm. Under common assumptions, the method is proved to be globally convergent. It is shown that for uniformly convex functions the convergence of the accelerated algorithm is still linear, but the reduction in the function values is significantly improved. In mild conditions the algorithm is globally convergent for strongly convex functions. Computational results for a set consisting of 750 unconstrained optimization test problems show that this new accelerated scaled conjugate gradient algorithm substantially outperforms known conjugate gradient methods: SCALCG [3–6], CONMIN by Shanno and Phua (1976, 1978) [42,43], Hestenes and Stiefel (1952) [25], Polak–Ribiére–Polyak (1969) [32,33], Dai and Yuan (2001) [17], Dai and Liao (2001) (t=1)[14], conjugate gradient with sufficient descent condition [7], hybrid Dai and Yuan (2001) [17], hybrid Dai and Yuan zero (2001) [17], CG_DESCENT by Hager and Zhang (2005, 2006) [22,23], as well as quasi-Newton LBFGS method [26] and truncated Newton method by Nash (1985) [27].