赵耿威，黄敬频
(广西民族大学 数学与物理学院， 南宁 530006)
鞍点问题出现在许多计算科学与工程学领域[1-3]，比如大型稀疏矩阵压缩存储与求解[4]、约束最优化计算[5]。文献[6]指出高维非凸优化问题之所以困难，是因为存在大量的鞍点而不是局部极值。这些鞍点通常被一个具有相同误差的平面所包围，使得各个维度上的梯度都趋于零且导致随机梯度下降难于逃脱。鞍点矩阵一般是不定矩阵且具有较弱的谱条件，因此对鞍点问题的计算是困难而重要的研究领域。多年来，国内外学者针对鞍点问题的研究提出了较多的研究方法，其中包括变尺度外梯度离散方法[7]、Uzawa类方法[8-9]、SOR类方法[10]和HSS类方法[11-12]等。此后一些学者又提出了改进的方法，如GSOR迭代法[13-14]、ASOR迭代法[15]等。
鞍点问题的一般形式为：
(1)
式中A∈Rm×m为非对称正定矩阵，B∈Rm×n(m>n)为列满秩矩阵，BT为B的转置矩阵，x,f∈Rm且y,g∈Rn，这里f,g是已知向量，x,y是未知向量。
文献[16]引入对称正定矩阵Q∈Rn×n并对式(1)的系数矩阵作如下分解：
DM-LM-UM
(2)
并给出MSOR-like的迭代格式为[16]：
(3)
分析迭代(3)可知，MSOR-like迭代至少存在2个方面的缺陷：
1) 参变量正定矩阵Q在矩阵分裂(2)中不确定，使得应用过程难以把握。
2) 单一松弛变量ω关联系数矩阵的灵敏度低，不利于增强整体收敛速度。
针对上述问题，进一步改进MSOR-like迭代十分必要，从而提升式(1)的求解效率。
为进一步改进MSOR-like迭代，在对矩阵A进行H，S分裂的基础上，得到新的分解矩阵D，L，U，同时新增加2个参数来提高迭代关联系数矩阵的灵敏度，以期提升迭代收敛速度。首先引入待定的对称正定矩阵Q∈Rn×n及参数α和β，并对式(1)的系数矩阵分裂如下：
(4)
(5)
式中：ω>0,α>0,β≥0且D,L,U如式(4)所示。称迭代(5)为修正MSOR-like方法，记为MMSOR-like。
显然，当α=1,β=0时，式(5)即为MSOR-like迭代(3)[16]；
当H=A,S=0时，式(5)即为SOR-like迭代[17]；
当H=A,S=0,α=1,β=0时，式(5)即为SOR-like迭代[18]；
当H=A,S=0,α=1时，式(5)即为SOR-like迭代[19]；
当H=A,S=0,β=1/2时，式(5)即为SOR-like迭代[20]。因此，新迭代格式(5)具有更广泛的参数选取，从而进一步提升式(1)的求解效率。下面具体导出式(5)的求解格式。由于
(6)
根据矩阵H,Q的正定性和S的反对称可知，矩阵D-ωL是非奇异的当且仅当ωβ≠1。因此假设ωβ≠1，并记
G=(D-ωL)-1[(1-ω)D+ωU]
T=ω(D-ωL)-1
通过简单的计算可得
(7)
(8)
于是式(5)等价于
(9)
式中：G,T如式(7)和(8)所示。
本节主要讨论MMSOR-like迭代(9)的收敛性及相关参数的选取方法。用ρ(G)表示矩阵G的谱半径，则由数值分析理论可知，迭代(9)收敛当且仅当ρ(G)<1。下面先给出几个引理。
引理1设λ为矩阵(7)中G的非零特征值，则λ≠1。
证明由条件可设(xT,yT)T∈Rm+n为非零特征值λ对应的特征向量，则有
G(xT,yT)T=λ(xT,yT)T
(10)
若λ=1，则把式(7)代入式(10)得
(11)
由式(11)及ω>0,可以导出
由于矩阵A是正定矩阵，B是列满秩矩阵，从而方程(1)是非奇异的，所以有x=0,y=0，这与 (xT,yT)T是矩阵G的一个特征向量矛盾，因此λ≠1。证毕。
引理2设H∈Rm×m是一个对称正定矩阵，S∈Rm×m是一个反对称矩阵，非零向量x∈Rm，则H,S的Rayleigh商RH(x)>0,RS(x)=0。
证明根据Rayleigh商定义得
RH(x)=(xTHx)/(xTx)
由于H∈Rm×m是一个对称正定矩阵，所以∀0≠x∈Rm，xTHx>0，从而RH(x)>0。同理，当S是反对称矩阵时xTSx=0，所以RS(x)=0。证毕。
引理3设λ为式(7)中矩阵G的1个特征值且(xT,yT)T为λ对应的特征向量，则x≠0。若y=0且限制0<αω<1，那么λ是实特征值且-1<λ<1。
证明设λ是G的特征值，(xT,yT)T为对应的特征向量，则有等式(10)成立，把矩阵(7)代入式(10)可得
(12)
由式(12)可得
(13)
由式(13)可推知x≠0，否则由B列满秩，从式(13)中第一式可得y=0，这与(xT,yT)T是矩阵G的一个特征向量相矛盾。若y=0，那么从式(13)中第一式可得
(14)
式(14)两边同时左乘xT/(xTx)得
(15)
引理4[21]实二次方程λ2-pλ+q=0的2个根的模均小于1，当且仅当|q|<1且|p| 定理1设式(7)中矩阵G的参数ω,α,β满足以下条件： (16) 式中：λmin[·]表示矩阵[·]的最小特征值，则求鞍点问题(1)的MMSOR-like迭代(9)收敛。 证明由引理1可得，迭代矩阵G的特征值λ≠1，因此当0<ωβ<1时可以将特征方程(13)写成如下形式： (17) 将式(17)中的第二个等式y代入第一个等式，并两边同时左乘xT/(xTx)，可得 (18) 式中：a,b,c分别是矩阵H,S,BQ-1BT的Rayleigh商。注意到矩阵H对称正定，S反对称，BQ-1BT半正定，因此由引理2得a>0,b=0,c≥0。于是可将式(18)进一步化简为： (19) 又由式(19)及引理4得，若要满足|λ|<1，当且仅当 (20) 从而由ω>0,0<ωβ<1求解不等式(20)可得 (21) 由式(21)的第二个不等式的右边式子可知 所以有 (22) (23) (24) 式中： 将式(24)代入式(23)，并令u=Uv=(u1,u2,…,un)T得 λ1|u1|2+λ2|u2|2+…+λn|un|2 (25) 由于‖u‖2=‖Uv‖2=‖v‖2=1，故由式(25)可得 λ1(|u1|2+|u2|2+…+|un|2)=λ1 (26) 综合式(22)和(26)可得，当参数ω,α,β满足不等式(16)时ρ(G)<1，即MMSOR-like迭代(9)收敛。证毕。 根据定理1，立即可得如下推论 (27) 在矩阵分裂(4)中，引入了待定的对称正定矩阵Q∈Rn×n，由于Q的不确定，导致应用过程难以把握，因此在执行迭代(9)之前，很有必要考虑Q的选取问题。根据定理1可知，参数α的选取范围是 表1 预处理矩阵Q具体形式 考虑如下形式的鞍点问题[16]： 式中： ⊗表示克罗内克积，取h=1/(p+1)为离散网络值且m=2p2,n=p2。 分别用MMSOR-like和MSOR-like方法计算case 1和case 2，IT和CPU结果见表2和表3。 表2 Q=BT[diag(H)]-1B时2种迭代的IT和CPU(case 1) 表3 Q=BT[tridiag(H)]-1B时2种迭代的IT和CPU(case 2) 数值实验结果表明，适当选取对称正定矩阵Q及参数ω,α,β时，所提的求解鞍点问题(1)的MMSOR-like方法相比文献[16]所给的MSOR-like方法具有更快的收敛速度。 为更高效求解鞍点问题，在MSOR-like迭代法的基础上，提出了一种修正的迭代方法，即MMSOR-like迭代方法(9)。该方法在对矩阵A进行H,S分裂后，引入参数建立新的分解矩阵D,L,U，使得迭代格式适用范围更广。在定理1用特征值理论证明了迭代的收敛性，并获得参数ω,α,β的选取范围(16)；
同时给出了预优矩阵Q的2种选取方法，使得矩阵Q与矩阵A,B的关联性强且易计算。数值实验结果表明，适当选取正定矩阵Q及相关参数ω,α,β，MMSOR-like方法能显著提高收敛效率。