下载: -
设
$\mathbb{R}$ 是实数域，$\mathbb{R}$ n是所有n维实向量的集合. 张量是向量和矩阵的高阶推广，通常m阶n维实张量是由nm个实数构成的多维数组，即其中N={1，2，…，n}，M={1，2，…，m}. 记
$\mathbb{R}$ [m，n]为m阶n维实张量的全体构成的集合，特别地，当m=0时，$\mathbb{R}$ [0，n]简记为$\mathbb{R}$ ，当m=1时，$\mathbb{R}$ [1，n]简记为$\mathbb{R}$ n. 如果实张量A=(ai1i2…im)的元素满足p是指标集{1，2，…，m}上的任意置换，则称A是实对称张量.
文献[1]提出了张量特征值与特征向量(也称为张量特征对)的概念，并讨论Z-特征值和H-特征值的一些性质. 张量特征值是矩阵特征值的高阶推广，下面给出实对称张量的Z-特征值的定义.
定义1[1] 设A∈
$\mathbb{R}$ [m，n]是实对称张量，如果存在λ∈$\mathbb{R}$ 和非零向量x=(x1，…，xn)∈$\mathbb{R}$ n使得则称λ为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∈
$\mathbb{R}$ [i，n]是实对称张量，i=2，3，如果存在λ∈$\mathbb{R}$ 和非零向量x∈$\mathbb{R}$ n使得则称λ为不同阶对称张量组{Ai}i=23的Z-特征值，x为与λ相对应的Z-特征向量，或称(λ，x)是不同阶对称张量组{Ai}i=23的Z-特征对.
近年来，文献[16]提出应用Newton-Gauss-Seidel法可求解不同阶张量组方程，接着文献[15]提出通过SS-HOPM求解不同阶对称张量组Z-特征值问题(2). 本文接下来介绍应用改进的Newton-法求解问题(2).
全文HTML
-
首先，回顾Newton-法求解对称张量Z-特征值，从而将该方法推广到求解不同阶对称张量组Z-特征值. 为了解决对称张量Z-特征值问题(1)，文献[17]将对称张量组Z-特征值问题(1)等价转化为如下非线性方程组解的问题：
设w=(xT，μ)T是(n+1)维向量，其价值函数为
$g(\boldsymbol{w})=\frac{1}{2} \sum\limits_{i=1}^{n+1}\left(G_{i}(\boldsymbol{w})\right)^{2}$ . 在此基础上，文献[17]利用Newton-法求解问题(1).针对问题(2)，将不同阶对称张量组Z-特征值问题等价转化为如下非线性方程组的解的问题：
易知(n+1)维向量(x*T，λ*)T为非线性方程组(3)的解当且仅当(λ*，x*)为不同阶对称张量组{Ai}i=23的Z-特征对. 现在考虑用改进Newton-法求解非线性方程组(3). 首先，给出F(x，λ)的Jacobi矩阵.
引理1[18] 若Ai∈
$\mathbb{R}$ [i，n]是实对称张量，i=2，3，则F(x，λ)的Jacobi矩阵$\nabla $ F(x，λ)为实对称矩阵，且具有如下形式：记v=(xT，λ)T，则v为(n+1)维列向量，当使用Newton-法求解非线性方程组(3)时，若p为Newton-法的下降方向，则在任意一迭代点vk=(xkT，λk)T处的下降方向pk满足
为了确保Newton-法的全局收敛性，根据文献[17]提出的方法，引入F(v)的价值函数
显然，若F(v*)=0，则f(v*)=0. 由于f(v)≥0对所有的v恒成立，因此，f(v)的全局极小值点为F(v)=0的根.
通常，满足(4)式时，Newton-法的下降方向pk与f(v)的负梯度方向-
$\nabla $ f(vk)的夹角为θk∈$\left[0, \frac{\pi}{2}\right)$ . 为了加快收敛速度，给定常数δ∈(0，1)，使得其中
$\nabla $ f(vk)=$\nabla $ FT(vk)F(vk)，δ越靠近1，收敛速度越快. 当pk不满足(5)式时，对pk进行修正，修正式为其中
$\nabla $ F-T(vk)表示Jacobi矩阵$\nabla $ F(vk)的逆的转置，令通过化简得
又由文献[19]中的算法3.3知τk的选取使Bk为正定矩阵且使(5)式成立，具体过程见算法1.
算法1[19] τk选取的算法
输入：矩阵Hk=
$\nabla $ FT(vk)$\nabla $ F(vk)输出：τk+1
选取初始点：给定常数σ
1：if min(hii)>0
2： τ0=0
3：else
4： τ0=－min(hii)+σ
5：end if
6：for k=0，1，…，do
7： if L·LT=Hk+τkIn+1
8： stop
9： else
10： τk+1=max(2τk，σ)
11： end if
12：end for
选取步长βk满足如下Wolfe条件
其中：0 < c1 < c2 < 1. 通过上述的分析，下面给出改进的Newton-法求不同阶实对称张量组Z-特征值的算法.
算法2 改进的Newton-法求解不同阶对称张量组Z-特征值.
输入：对称张量
$\left\{\boldsymbol{A}_{i}\right\}_{i=2}^{3} \in \mathbb{R}^{[i, n]}$ ，初始值x0，λ0，β，给定常数δ，ε，ρ∈(0，1)，0 < c1 < c2 < 1.输出：特征值λk+1.
1：for k=0，1，…，do
2： pk=－
$\nabla $ F－1(vk)F(vk)3： if －pkT
$\nabla $ f(vk)≤δ‖pk‖‖$\nabla $ f(vk)‖4： pk=－Bk－1
$\nabla $ f(vk)5： end if
6： while f(vk+βpk)>f(vk)+c1β
$\nabla $ fT(vk)pk‖$\nabla $ f(vk+βpk)Tpk < c2$\nabla $ fT(vk)pk7： β=ρβ
8： end while
9： βk=β
10： (xk+1T，λk+1)T=(xkT，λk)T+βkpk
11： vk=(xk+1T，λk+1)T
12： if ‖
$\nabla $ f(vk)‖≤ε13： break
14： end if
15：end for
-
本节分析算法2的收敛性，首先给出一些假设.
假设1 f在
$\mathbb{R}$ n+1上有下界，并且在包含水平集E={v：f(v)≤f(v0)}的开集Ω上连续可微，其中v0为起始迭代点.假设2 f的梯度
$\nabla $ f在Ω上Lipschitz连续. 即存在一个常数L>0，使得假设3 F：
$\mathbb{R}$ n+1$\mathbb{R}$ n+1在凸开集D上连续可微且v和v+p是D中的向量.引理2[19] 如果f满足假设1和2，那么考虑vk+1=vk+αkpk这种形式的迭代，其中pk是下降方向，αk是步长且满足Wolfe条件(7)，有如下不等式成立
其中θk是pk与－
$\nabla $ f(vk)的夹角.定理1 如果函数f(v)满足假设1和2，那么由算法2产生的序列{vk}满足
即改进的Newton-法全局收敛.
证 当pk满足条件(5)时，由引理2可知，由于
$\sum\limits_{k \geqslant 0} \cos ^{2} \theta_{k}\left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|^{2} < \infty$ ，可得$\lim\limits _{k \rightarrow \infty} \cos ^{2} \theta_{k} \cdot \left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|^{2}=0 $ ，又由条件(5)可知对任意的k都有cosθk≥δ>0，由此可得$\lim\limits _{k \rightarrow \infty}\left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|=0$ . 当pk不满足条件(5)时，根据(6)式构造的矩阵Bk是正定矩阵并具有有界条件数，因此，存在常数U>0，使得对任意k都有‖Bk－1‖‖Bk‖≤U，又由条件(5)可得其中ρmin，ρmax分别是Bk的最小特征值和最大特征值，由引理2可知
$\lim\limits _{k \rightarrow \infty}\left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|=0$ .通过上面的分析，两种情况都可得到
$\lim\limits _{k \rightarrow \infty}\left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|=0$ ，由文献[19]可知改进的Newton-法全局收敛，即定理1得证.定理2 若假设1，2，3成立，且βk=1. 如果
$\nabla $ F(v*)是非奇异的，其中v*是算法2产生的序列{vk}的收敛点，那么算法2超线性收敛.证 由定理1得到
$\lim\limits _{k \rightarrow \infty}\left\|\nabla f\left(\boldsymbol{v}_{k}\right)\right\|=0$ ，即$\lim\limits _{k \rightarrow \infty}$ ‖$\nabla $ FT(vk)F(vk)‖=0，因为v*是序列{vk}的收敛点，$\nabla $ F(v*)是非奇异的，所以$\lim\limits _{k \rightarrow \infty}$ ‖F(vk)‖=0. 又由假设1，2，3成立可知，通过文献[19]中的定理11.1和11.2可得即{vk}超线性收敛到v*.
-
本节使用文献[15]中给出的两个例子进行数值实验，并对二者的结果进行比较. 所有试验都在MATLAB R2015a中完成，其配置为：Intel(R) Celeron(R)3205U 1.50 GHz CPU和4.00G RAM内存.
例1 设实对称张量A3=(aijk)∈
$\mathbb{R}$ [3, 3]和实对称正定矩阵A2=(bij)∈$\mathbb{R}$ [2, 3]，且元素取值如下：使用两种算法进行数值实验，在算法2中选取的参数分别是ε=10－7，c1=0.1，c2=0.8，并用分布在[-2, 2]中的不同随机初始点x0和λ0进行200次实验，最大迭代次数为1 000次，如果‖
$\nabla $ f(vk)‖≤ε，说明算法收敛. 实验结果见表 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)∈
$\mathbb{R}$ [3, 3]和实对称矩阵A2=(bij)∈$\mathbb{R}$ [2, 3]，且元素取值如下：再次使用两种算法进行数值实验，算法2选取的参数分别是ε=10－7，c1=0.000 1，c2=0.8，并用分布在[-10, 10]中的不同随机初始点x0和λ0进行100次实验，其最大迭代次数为1 000次，如果‖
$\nabla $ f(vk)‖≤ε，说明算法收敛，结果见表 4，5.对表 4和表 5的结果比较可知，算法2要比SS-HOPM所求特征对多，两种方法都能算出特征值0.785 9，但算法2用时为0.085 451 s，SS-HOPM用时为0.144 277 s，可见算法2用时较少，且与文献[15]相比，得到了新的特征值.
-
数值例子实验表明，改进的Newton-法是一种有效的求解不同阶对称张量组Z-特征值的方法且算法2是全局超线性收敛的. 因此，改进的Newton-法和SS-HOPM相互补充，可以求出更多的不同阶对称张量组的Z-特征值.