冯茹茹，王希云

(太原科技大学应用科学学院，太原030024)

无约束优化问题的一般形式为:

其中f:Rn→R为二次连续可微函数，fk表示f(xk)，gk表示▽f(xk)。定义dk=-Hkgk为拟牛顿方向，其中Hk为Hessen矩阵的逆近似，要求Hk正定且满足拟牛顿条件

其中yk-1=gk-gk-1，sk-1=xk-xk-1.在拟牛顿算法中，存储量至少为O(n2)。如果用稀疏矩阵来逼近Hessen阵的逆，要求存储量为O(n)，且近似满足拟牛顿条件。对角稀疏拟牛顿算法的提出使存储量和工作量明显减少，适合于大规模稀疏问题的求解。

1988 年，Barzilai和 Borwein[1]提出两点步长法，迭代公式为xk+1=xk-Dkgk，其中Dk=αkI是一个矩阵。为了使Dk具有拟 Newton性质，计算 αk使min‖sk-1-Dkyk-1‖，得

时贞军[2]提出了对角稀疏拟牛顿法，该算法在每次迭代中利用对角矩阵近似拟牛顿法中的校正矩阵，通过求解得到min‖Hkyk-1-sk-1‖2得到Hk，从而构造对角稀疏拟牛顿法。

之后，很多学者对此类算法进行了研究，其中对角二阶拟牛顿法[3]对Hessen阵具有二阶逼近阶;孙清滢，崔彬[4]和郑艳梅[5]分别将 Grippo 非单调线搜索和Zhang H.C.提出的非单调线搜索引入对角稀疏拟牛顿法进行了研究。

基于三阶拟牛顿方程[6]

来获得Hessen阵的正定对角矩阵逆近似，同时将Zhang H.C.[7]提出的非单调线搜索规则与时贞军提出的大步长线搜索技巧结合设计求解无约束优化问题的对角三阶拟牛顿法。

1 对角三阶拟牛顿法

为保证搜索方向dk=-Hkgk为下降方向，要求，因此有问题(SP)

在问题(SP)中，m，M取正常数。

算法1(DSQN):

(Ⅰ)∀x0∈Rn，H0=In，C0=f0=f(x0)，Q0=0＜ηmin≤ ηmax＜1，k=0，ε＞0.

(Ⅱ)若‖gk‖ ＜ε，则停，否则转(Ⅲ)。

(Ⅲ)令dk=-Hkgk，其中Hk由式(5)确定，转(Ⅳ)。

令xk+1=xk+αkdk，fk+1=f(xk+1).

(Ⅴ)通过某种规则给出 ηk∈[ηmin，ηmax]，

令k∶=k+1，转(Ⅱ)。

引理1 若xk不是问题(SP)的稳定点，则有‖dk‖≤M‖gk‖.

引理2 若xk不是问题(SP)的稳定点，则有

引理 3[7]对∀k有，fk≤Ck.

2 全局收敛性

假设1f(x)在水平集L(x0)={x∈Rn|f(x)≤f(x0)}上有下界。……