改进的Newton-法求解不同阶对称张量组Z-特征值①

杨廷梅， 刘奇龙， 陈震， 许云霞

贵州师范大学 数学科学学院， 贵阳 550025

设R是实数域， Rn是所有n维实向量的集合． 张量是向量和矩阵的高阶推广， 通常m阶n维实张量是由nm个实数构成的多维数组， 即

A=(ai1i2…im)，ai1i2…im∈R，ij∈N，j∈M

其中N={1， 2， …，n}，M={1， 2， …，m}． 记R[m， n]为m阶n维实张量的全体构成的集合， 特别地， 当m=0时， R[0， n]简记为R， 当m=1时， R[1， n]简记为Rn． 如果实张量A=(ai1i2…im)的元素满足

aip(1)ip(2)…ip(m)=ai1i2…im，ij∈N，j∈M

p是指标集{1， 2， …，m}上的任意置换， 则称A是实对称张量．

文献[1]提出了张量特征值与特征向量(也称为张量特征对)的概念， 并讨论Z-特征值和H-特征值的一些性质． 张量特征值是矩阵特征值的高阶推广， 下面给出实对称张量的Z-特征值的定义．

定义1[1]设A∈R[m ， n]是实对称张量， 如果存在λ∈R和非零向量x=(x1， …，xn)∈Rn使得

Axm-1=λx，xTx=1

(1)

则称λ为A的Z-特征值，x为与λ相对应的Z-特征向量， 或称(λ，x)是A的Z-特征对， 其中Axm-1是n维向量， 第i个分量为

由于对称张量Z-特征值在数据挖掘[2-3]、 目标跟踪[4]和超图匹配[5]等许多实际问题中有着重要应用， 使得对称张量Z-特征值问题逐渐成为张量谱理论研究的热点问题[6-13]． 文献[14]在研究基于张量算法的高阶图匹配时提出了包含边和超边的匹配模型． 文献[15]从文献[14]中提出不同阶对称张量组Z-特征值问题， 定义如下．

定义2[15]设Ai∈R[i， n]是实对称张量，i=2，3， 如果存在λ∈R和非零向量x∈Rn使得

A3x2+A2x=λx，xTx=1

(2)

近年来， 文献[16]提出应用Newton-Gauss-Seidel法可求解不同阶张量组方程， 接着文献[15]提出通过SS-HOPM求解不同阶对称张量组Z-特征值问题(2)． 本文接下来介绍应用改进的Newton-法求解问题(2)．

1 改进的Newton-法求不同阶对称张量组Z-特征值

首先， 回顾Newton-法求解对称张量Z-特征值， 从而将该方法推广到求解不同阶对称张量组Z-特征值． 为了解决对称张量Z-特征值问题(1)， 文献[17]将对称张量组Z-特征值问题(1)等价转化为如下非线性方程组解的问题：

针对问题(2)， 将不同阶对称张量组Z-特征值问题等价转化为如下非线性方程组的解的问题：

(3)

引理1[18]若Ai∈R[i， n]是实对称张量，i=2，3， 则F(x，λ)的Jacobi矩阵∇F(x，λ)为实对称矩阵， 且具有如下形式：

∇F(vk)pk=-F(vk)

(4)

为了确保Newton-法的全局收敛性， 根据文献[17]提出的方法， 引入F(v)的价值函数

显然， 若F(v*)=0， 则f(v*)=0． 由于f(v)≥0对所有的v恒成立， 因此，f(v)的全局极小值点为F(v)=0的根．

(5)

其中∇f(vk)=∇FT(vk)F(vk)，δ越靠近1， 收敛速度越快． 当pk不满足(5)式时， 对pk进行修正， 修正式为

(∇F(vk)+τk∇F-T(vk))pk=-F(vk)

其中∇F-T(vk)表示Jacobi矩阵∇F(vk)的逆的转置， 令

Bk=∇FT(vk)∇F(vk)+τkIn+1

(6)

通过化简得

又由文献[19]中的算法3.3知τk的选取使Bk为正定矩阵且使(5)式成立， 具体过程见算法1．

算法1[19] τk选取的算法输入: 矩阵Hk=〠FT(vk)〠F(vk)6: for k=0, 1, …, do输出: τk+17: ifL·LT=Hk+τkIn+1选取初始点: 给定常数σ8: stop1: ifmin(hii)>09: else2: τ0=010: τk+1=max(2τk, σ)3: else 11: end if4: τ0=-min(hii)+σ12: end for5: end if

选取步长βk满足如下Wolfe条件

(7)

其中： 0

算法2 改进的Newton法求解不同阶对称张量组Z特征值.输入: 对称张量{Ai}3i=2∈R[i, n], 初始值x0,λ0,β, 给定常数δ,ε,ρ∈(0, 1), 0f(vk)+c1β〠fT(vk)pk‖〠f(vk+βpk)Tpk

2 收敛性分析

本节分析算法2的收敛性， 首先给出一些假设．

假设1f在Rn+1上有下界， 并且在包含水平集E={v：f(v)≤f(v0)}的开集Ω上连续可微， 其中v0为起始迭代点．

假设2f的梯度∇f在Ω上Lipschitz连续． 即存在一个常数L>0， 使得

设d(f)=3, ch(f)=3-4=-1,事实上R3已经考虑到了3-面的所有情况,依次来讨论。若f是一个(3,3,3)-面,由引理1(3)和R3.1得若f是一个(3,3,k)-面(k=4,5,6),由引理1.3和R3.2得若f是一个(3,3,7+)-面,由R3.3得ch′(f)≥ch(f)+1=-1+1=0。若f是一个(3,4,4)-面,由引理1(2)和R3.4得 若f是一个(3,4,5+)-面,由R3.5得若f是一个(3,5+,5+)-面,由R3.6得 若f是一个(4+,4+,4+)-面,由R3.7得综上,3-面得证。

‖∇f(v)-∇f(v′)‖≤L‖v-v′‖， ∀v，v′∈Ω

引理2[19]如果f满足假设1和2， 那么考虑vk+1=vk+αkpk这种形式的迭代， 其中pk是下降方向，αk是步长且满足Wolfe条件(7)， 有如下不等式成立

其中θk是pk与-∇f(vk)的夹角．

定理1如果函数f(v)满足假设1和2， 那么由算法2产生的序列{vk}满足

即改进的Newton-法全局收敛．

定理2若假设1，2，3成立， 且βk=1． 如果∇F(v*)是非奇异的， 其中v*是算法2产生的序列{vk}的收敛点， 那么算法2超线性收敛．

‖vk+1-v*‖=ο(‖vk-v*‖)

即{vk}超线性收敛到v*．

3 数值实验

本节使用文献[15]中给出的两个例子进行数值实验， 并对二者的结果进行比较． 所有试验都在MATLAB R2015a中完成， 其配置为： Intel(R) Celeron(R)3205U 1.50 GHz CPU和4.00G RAM内存．

例1设实对称张量A3=(aijk)∈R[3，3]和实对称正定矩阵A2=(bij)∈R[2，3]， 且元素取值如下：

使用两种算法进行数值实验， 在算法2中选取的参数分别是ε=10-7，c1=0.1，c2=0.8， 并用分布在[-2， 2]中的不同随机初始点x0和λ0进行200次实验， 最大迭代次数为1 000次， 如果‖∇f(vk)‖≤ε， 说明算法收敛． 实验结果见表1-3．

表1 算法2在例1上的数值结果

表2[15] SS-HOPM算法在例1上的数值结果

表3 两种算法计算相同特征值所用平均时间

由表1与表2可知， 该数值实验得出的结果与文献[15]中的结果相比： 第一， 两种方法都能求出特征值0.019 4和0.431 4， 但根据表3， 可知算法2计算所用的时间更少一些； 第二， 算法2可以求出14个特征值里的9个， 比文献[15]中用SS-HOPM所求的特征值多了5个， 其中有7个与文献[15]求出的特征值不相同．

例2实对称张量A3=(aijk)∈R[3， 3]和实对称矩阵A2=(bij)∈R[2， 3]， 且元素取值如下：

再次使用两种算法进行数值实验， 算法2选取的参数分别是ε=10-7，c1=0.000 1，c2=0.8， 并用分布在[-10， 10]中的不同随机初始点x0和λ0进行100次实验， 其最大迭代次数为1 000次， 如果‖∇f(vk)‖≤ε， 说明算法收敛， 结果见表4，5．

表4 算法2在例2上的数值结果

表5[15] SS-HOPM算法在例2上的数值结果

对表4和表5的结果比较可知， 算法2要比SS-HOPM所求特征对多， 两种方法都能算出特征值0.785 9， 但算法2用时为0.085 451 s， SS-HOPM用时为0.144 277 s， 可见算法2用时较少， 且与文献[15]相比， 得到了新的特征值．

4 结论

数值例子实验表明， 改进的Newton-法是一种有效的求解不同阶对称张量组Z-特征值的方法且算法2是全局超线性收敛的． 因此， 改进的Newton-法和SS-HOPM相互补充， 可以求出更多的不同阶对称张量组的Z-特征值．