定矩阵．
证明 由（17）、（18）、（20）式可知
． 对称正定；若
对称正定，类似文献[3]定理 5.1.3，可证明 也对称
正定；依数学归纳法，引理成立．
引理 2 设 [13]727-739 为对称正定矩阵， 由校正公
式（20）生成．若
，有
（21）
则
，不等式
至少成立 次，其中
．
（22）
为了便于描述，定义指标集
关键词：无约束优化；拟牛顿法；全局收敛性
中图分类号：O242.23
文献标识码：A
文章编号：1674-8891（2011）03-0008-04
Comparison of Some Modified Quasi-Newton Methods
HUANG Hai, LIN Sui-hua
(Department of Mathematics and Computer Science Guangxi Normal University for Nationalities，Guangxi Chongzuo, 532200)
步 2: 若
，停止迭代; 否则解线性方程组
，得到搜索方向 ．
步 3: 由 Armijio 规则确定步长因子 :
（19）
步 4:
．根据下
面的修正 BFGS 校正计算
（20）
其中 由（17），（18）计算．
步 5: 令
，转步 2．
2.2 算法收敛性分析
为了分析 MBFGS 算法的收敛性，我们作如下假设:
（2）
其中
为对称矩阵．若 正定，则极小化以上
右式，得到拟牛顿法搜索方向为
（3）
对（2）两边求导可得
，其中
，故
传统的拟牛顿法要求 满足如下标准拟牛顿条件
，
（4）
产生 的不同方法又构成不同的拟牛顿法，其中著
名的标准 BFGS 校正公式为
（5）
标准BFGS方法是传统拟牛顿法中最有效的一个[1]82-118， 然而采用非精确线搜索的标准 BFGS 拟牛顿法对非凸 函数时是不收敛的 ， [2]673-701 如何提高实际计算中的运 算效率，如何使得对非凸目标函数保持局部超线性 收敛的同时具有全局收敛性，是人们对拟牛顿算法 研究的两个方向．
Key words：unconstrained optimization, quasi-Newton method, global convergence
0 引言
考虑用数值方法求解如下无约束优化问题
（1）
其中
为二阶连续可微函数，通常利用迭
代算法
，
其中 为第 次迭代点， 为第 次搜索方向，
为步长因子，
摘 要：拟牛顿法是所有利用一阶导数求解无约束优化问题的方法中最有效的一类计算方法，如何提高实际计算中的运算效率，如何
使得对非凸目标函数保持局部超线性收敛的同时具有全局收敛性，是对拟牛顿法进行研究的两个方向．对近年来相关文献的几种修正拟牛
顿法进行分析比较，并提出和分析了一个修正 BFGS 拟牛顿法的收敛性．
1 几种修正拟牛顿法的比较
1.1 拟牛顿条件的修正及相应的校正矩阵 牛顿法成功的关键是利用了 Hesse 矩阵提供的曲
率信息 ，为提 [3]219-222 高拟牛顿算法的运算效率，自然 的想法是使 在某种意义上更好地逼近 Hesse 矩阵
，进而对标准拟牛顿条件及相应的校正矩阵进行 修正以期获得好的效果．
，
两种方式的修正 BFGS 校正并不等价，如
（i） 以下两种修正的 BFGS 校正形式都满足
:
，
其中
，
（16）
，
（ii）取
，但 不恒等 ． ，
时 ， （16） 中 两
种修正 BFGS 校正形式都满足 ，但 也不
恒等 ． 1.2 为全局收敛采取的一些修正措施
对非凸目标函数，满足标准拟牛顿条件的传统 拟牛顿法至今仍没有任何全局收敛性结果，除了要 确保 继承 的正定性外，主要难点是一致有界性
就得到相应于修正的拟牛顿条件（15）的修正 BFGS
公式．
文献[10]15-35 的动机则是基于对非凸函数全局收敛
性的需要．若 为非凸函数，则 不一定正定，由
方程
得到的牛顿法方向 可能不是下降
方向，为克服这一问题，适当修正以 代替 ，其
中
选择为使 正定的正常数，从
而得到修正的牛顿法方向
必是下降方向．
换成
， 得到新的
条件
． （7）
利用以上四个插值条件得到一个三次插值函数，再
让逼近函数（6）在 方向上是该函数的二次 Taylor
展开，得到另一 条件
． （8）
袁亚湘等[5]95-107 还研究了如下一般性的弱拟牛顿
条件
，
（9）
，给出相应于（9）的修正BFGS校正公式为
． （10）
标准拟牛顿条件（4）满足
，有
．
由 一个不等式成立．
由拉格朗日中值定理及
知 ， （21） 的 第
，可知
，使
由（17），（18）， 及 ，可得
可得（21）的第二个不等式成立．所以引理 2 的条件
满足． 又由引理 1 知， ， 从 而 由 （19）
及 知， 为严格下降序列，
引理 3，可得
，再由
． 由引理 2 可知指标集 有无限多个元素，结合上 式及（22）的第二式可得
．
引理 3 设 成立，则
．
证明 由算法步 3 的 Armijio 搜索规则，可知 不满足（19）式，即
（23）
由拉格朗日中值定理及 可知，
使
由算法步 2 知 和（22），可得
（24） ，再由（24），（23），
引理得证． 定理 1 设 ，
成立，
为 MBFGS 算法
生成的序列，则
．
证明 利用反证法．假设定理不成立，即
由（22）的第一式及上式可得
，
这与假设矛盾，定理得证．
3 结束语
拟牛顿法是一类重要的无约束优化计算方法， 其理论分析与算法改进研究已有很多成果．首先分 析比较最近的相关文献，总结出两种拟牛顿条件修 改方式及全局收敛的一些措施，发现这两种方式可 用一种形式统一起来，这种线性或非线性组合的修 正拟牛顿条件还待进一步研究；其次，应用比较的 结果，给出了一个修正的 BFGS 拟牛顿算法，在较弱 的条件下，不需要目标函数的凸性假设，证明了算 法对一般的无约束优化问题具有全局收敛性．
式，只需在（5）中将 换成 就可得到（10）．虽 然角度不一样，但方式一与方式二的修正策略本质 上是一致的．
（2）两种方式得到的修正拟牛顿条件分别对应 两种形式
实际上两者可统一于形式
，
其中
．
（注: 若 （14） 中 为 非 数 量 矩 阵 时 ， 则 取
，作为推广也可取
）．
（3）即使满足同一弱拟牛顿条件
的第 次迭代，得到比文献[8]147-167 更一般的修正拟牛
顿条件
（14）
矩阵 的选择有多种，如可取
．对目标函数
利用
Taylor 公式得到
，
取得，即，利用（14）得，结合 逼近 及
上式得到
对任何满足
， 的向量 ，上式可描述为 ，
取 可得修正拟牛顿条件
（15）
此时
与（7）是一致的， 与 的项
之间有
．将 替换（13）中的 ，
（H1） 在水平集
- 10 -
第 28 卷
黄 海，林穗华 几种修正拟牛顿法的比较
（总第 76 期）
上有界．
（H2） 的导函数 在 上 Lipschitz 连续，
即
使
，
由以上假设可知
，使
，
．不仿假设
，否则稳定点已获得，
算法有限步终止．下面简要证明算法的全局收敛性．
引理 1 MBFGS 算法生成的序列 均为对称正
Abstract： For unconstrained optimization problems， quasi-Newton methods are a class of utilizing， first derivative, the most effective approach． How to improve the computing efficiency of the actual calculation, and how to obtain global convergence and local super linear convergence for non-convex objective function are contents of quasi-Newton research． This paper compares some modified quasi-Newton methods in the recent literature, proposes a modified BFGS quasi-Newton method and analyzes its global convergence．
-9-
2011 年第 3 期
广西民族师范学院学报
6 月 25 日出版
这一思想类推到拟牛顿法，由
，可知
，使 近似 ，从而合理地得
到 满足如下修正拟牛顿条件
进而得到形如（13）的修正 BFGS 校正公式．参数
条件（
，有
）一
般不成立 ．为 [1]102-111 了全局收敛性及超线性收敛性的
需要，人们往往提出适当的假设，或采取一些修正
可能是病态的，因此提出用调比因子 使
减少
病态的方案，其做法是由
，用 近似
（亦使 克服病态），得到修正拟牛顿条件