求解鞍点问题的修正MSOR-like方法

赵耿威，黄敬频

(广西民族大学 数学与物理学院， 南宁 530006)

0 引言

鞍点问题出现在许多计算科学与工程学领域[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)的求解效率。

1 修正MSOR-like迭代构建

为进一步改进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)所示。

2 MMSOR-like方法的收敛性

本节主要讨论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)

3 预优矩阵Q的选取

在矩阵分裂(4)中，引入了待定的对称正定矩阵Q∈Rn×n，由于Q的不确定，导致应用过程难以把握，因此在执行迭代(9)之前，很有必要考虑Q的选取问题。根据定理1可知，参数α的选取范围是

表1 预处理矩阵Q具体形式

4 数值实验

考虑如下形式的鞍点问题[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方法具有更快的收敛速度。

5 结论

为更高效求解鞍点问题，在MSOR-like迭代法的基础上，提出了一种修正的迭代方法，即MMSOR-like迭代方法(9)。该方法在对矩阵A进行H,S分裂后，引入参数建立新的分解矩阵D,L,U，使得迭代格式适用范围更广。在定理1用特征值理论证明了迭代的收敛性，并获得参数ω,α,β的选取范围(16)；同时给出了预优矩阵Q的2种选取方法，使得矩阵Q与矩阵A,B的关联性强且易计算。数值实验结果表明，适当选取正定矩阵Q及相关参数ω,α,β，MMSOR-like方法能显著提高收敛效率。