兰州大学机构库 >数学与统计学院
Barzilai-Borwein梯度法及其在优化算法中的应用
Alternative TitleOn the Barzilai-Borwein gradient method and its applications in other optimization methods
郑燏涛
Subtype博士
Thesis Advisor郑兵
2018-03-15
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
KeywordBarzilai-Borwein梯度法 拟牛顿方程 BFGS 方法 自适应三次正则化方法 共轭梯度法
Abstract

梯度法是求解无约束优化问题的基本方法之一, 其算法简单, 所需存储较少. 但此方法中步长的选取对计算效果有较大的影响, Barzilai和Borwein提出的两点步长其对应的Barzilai-Borwein (BB) 梯度法由于有较好的计算效果和收敛性, 现在已经发展成为求解大规模问题竞争力很强的一种方法, 受到众多学者的广泛关注. 本文主要探讨新的BB型梯度算法及其在优化算法中的应用. 主要内容包括以下几个方面:

1. 探寻新的 BB 型梯度算法. 基于Ford和Moghrabi的多步拟牛顿方程, 通过修正原始的 BB 步长使其满足这一特定的拟牛顿特性, 提出了一族新的BB型步长并建立了采用新步长的梯度型算法对严格凸二次极小化问题的全局收敛性. 将新方法应用于实际问题与由机器产生的随机问题, 结果表明, 新的 BB 型方法优于现存的一些梯度型算法.

2. 研究 BB 型步长在优化算法中的应用. 首先, 结合非单调线搜索, 将第一部分内容中的MBB方法推广到一般的非二次无约束优化问题的求解当中. 其次, 由于改进的拟牛顿方程与 Dai-Liao共轭梯度法之间存在着紧密的联系, 将在Dai-Liao方法中使用过的具有一定最优特性的 BB型参数值应用到变尺度 BFGS 方法与修正的BFGS方法当中. 最后, 将BB型步长嵌入到自适应三次正则化方法中, 用实正定数量矩阵代替精确Hessian或其拟牛顿逼近, 简化了算法中子问题的求解且改进后的算法适用于大规模问题. 数值试验表明, 这些修正合理且有效. 在此期间, 还通过插值的方式, 统一了现有的对拟牛顿方程的大部分改进, 为这些改进的提出给出了一个自然的阐释.

3. 研究BB型方法求解对称不定线性方程组的收敛性. 我们得出: 二维情形下, 采用第二种形式 BB步长的方法是R-超线性收敛的. 这一理论结果和戴彧红在对称正定情形下关于BB方法的结果一致.

4. 改进共轭梯度法. 通过修正共轭梯度法中的共轭参数, 提出了几个改进的共轭梯度算法, 其中包括两种Dai-Liao形式的共轭梯度法. 在一定条件下, 结合强Wolfe线搜索, 给出了算法对一致凸函数的强收敛性以及一般函数的全局收敛性. 数值试验表明本章给出的算法比已有的同类算法更有效.

Other Abstract

Gradient method is one of the most foundational methods for solving unconstrained optimization problems, its algorithm is very simple and low in memory. However, the choice of the step length greatly affect the gradient-type algorithm. Due to its very satisfactory performance and better convergence property compared to the steepest descent method, Barzilai-Borwein (BB) gradient method had been developed into a competitive method for large scale problems and got broad attention of numerous experts. This thesis mainly studies the new Barzilai-Borwein-type gradient method and its applications in other optimization algorithms. The research contents contain the following aspects:

Firstly, we aim to find some new BB-type gradient algorithms. Based on Ford and Moghrabi's multi-step quasi-Newton equation, by correcting the original BB stepsize to satisfy this particular quasi-Newton property, we introduce a new family of BB-type stepsizes. Furthermore, we establish the global convergence of the gradient algorithm utilizing this new stepsize for the strict convex quadratic minimization problem. When applied to some practical and random problems, the numerical results show that the modified BB method can outperform some existing gradient algorithms.

Secondly, we mainly consider the applications of BB-type stepsize in other optimization algorithms. Firstly, combining with the nonmonotone line search, we generalize the modified BB method proposed in part one to solve the general non-quadratic unconstrained optimization problem. Secondly, due to the close relationship between the improved quasi-Newton equation and the Dai-Liao conjugate gradient method, also the BB-type step length is widely used in these two methods, we consider using the BB-type parameter value, which was used in the Dai-Liao method with some certain optimal characteristics, in the scaled BFGS method and the modified BFGS method. Finally, we embed the BB-type step length into the adaptive cubic regularization method. By taking a positive definite scale matrix as the exact Hessian or its quasi-Newton approximation, the minimizer of the resulted subproblems can be easily determined, and at the same time, the convergence of the algorithm is maintained. The modified algorithm is also suitable for large scale problems. Numerical results show that these corrections are reasonable and effective. During this period, we also unified most of the existing improvements to the quasi-Newton equation by means of the interpolation, doing this gives a natural interpretation to the developments of these quasi-Newton equations.

Thirdly, we study the convergence of the BB-type method for solving symmetric indefinite linear system. We conclude that, in the two-dimensional case, the gradient method of adopting the second form of the BB stepsize is R-superlinear convergent. This result is consistent with the result of Dai in the symmetric positive definite case with respect to the BB method.

Finally, we improve the conjugate gradient methods. By modifying the conjugate parameters, we propose several improved conjugate gradient methods, including two Dai-Liao-type conjugate gradient methods. Under some certain conditions, combined with the strong Wolfe line search, we analyze the strong convergence of the algorithms for the uniformly convex functions and global convergence for general objective functions. Numerical experiments show that our algorithms are more effective when compared with some existing conjugate gradient methods.

URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225739
Collection数学与统计学院
Recommended Citation
GB/T 7714
郑燏涛. Barzilai-Borwein梯度法及其在优化算法中的应用[D]. 兰州. 兰州大学,2018.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[郑燏涛]'s Articles
Baidu academic
Similar articles in Baidu academic
[郑燏涛]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[郑燏涛]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.