求实对称张量Z-特征值的牛顿法

周会晓，倪 勤，曾梅兰，2

（1.南京航空航天大学 理学院，江苏 南京 210016；2.湖北工程学院 数学与统计学院，湖北 孝感 432000）

张量特征值问题在多项式最优化、超图理论、高阶马尔科夫链、图像科学等领域有广泛的应用，从而得到越来越多的关注.本文中，我们将张量Z-特征值问题转化为等价的非线性方程组，并用牛顿法求解，在算法中改进了方向并引入线搜索技术使得算法具有全局与二阶收敛性.

1 引言

考虑实数域R中包含nm个元素的m阶n维张量A=(ai1，…im),ai1，…im∈R,1≤i1,…,im≤n.若A中的元素满足，其中j1,…,jm为下标 {i1,…,im}的任意排列，则称张量A为对称张量.高阶张量是多维线性映射，是矩阵的推广，m=2 的张量即为矩阵.定义张量与向量的乘积为

其中x∈Rn，Axm-1为n维列向量.

定义1给定m阶n维张量A，若存在λ∈R，x∈Rn，满足

则称λ为张量A的Z-特征值，x为与之对应的Z-特征向量.

目前一些学者已尝试用多种方法求解对称张量的Z-特征值.文［1］采用定点分析理论，用移位幂方法求解张量Z-特征值问题，获得了线性收敛的求解算法.文［2］利用伪规范型思想，提出求三阶三维张量所有Z-特征值的直接法.因此如何有效地求解一般对称张量的Z-特征值仍值得深入研究.

2 求张量Z-特征值的牛顿法

现在我们将张量Z-特征值问题（1.1）转化为如下等价非线性方程组

若n+1维向量(x*,λ*)为非线性方程组（2.1）的解，则它为实对称张量A的Z-特征对.

现在考虑用牛顿法来求解该非线性方程组，下述引理给出了F(x,λ)的Jacobian 矩阵.

引理 1［3］若A为实对称张量，则F(x,λ)的 Jacobian 矩阵F′(x,λ)为实对称矩阵.F′(x,λ)具有如下形式：

记wT=(xT,λ)，则w为n+1维列向量，同时引入价值函数

显然，若w*为F(w)=0 的根，则有Φ(w*)=0.由于Φ(w)≥0 对所有的w恒成立，因此F(w)=0 的任何一个根至少是Φ的一个整体极小点.

牛顿法在任一迭代点处的搜索方向dk可由

确定.为了保证全局收敛性，dk需满足

其中ε∈(0,1)为一确定常数，∇Φ(wk)=F′(wk)F(wk).若dk不满足（2.4），将对dk进行修正，即令

λk的选取使得（2.4）满足，具体技术见文献［4］.

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

其中，0＜c1＜c2＜1.下面给出求实对称张量的Z-特征值的牛顿法.

算法1

步1.取初值.给定c1,c2,0＜c1＜c2＜1,ε＞0，取初始点w0,k=0.

步3.检验下降条件.若牛顿步dk使得（2.4）成立，则dk为所求下降方向；否则，由（2.5）给出dk.

步4.求步长αk满足（2.6）.

步5.wk+1=wk+αkdk,k=k+1，转步2.

3 收敛性分析

本节给出算法1的收敛性分析，因此需要下面的假设.

假设1水平集S={w:F(w)≤F(w0)}与包含S的开凸集Ω 有界，其中w0为起始迭代点.

假设2F(w)的 Jacobian 阵F′(w)关于w连续，∇Φ在 Ω 上Lipschitz连续，即存在常数L＞0，使得

定理1如果假设1-2成立，那么由算法1产生的{wk}满足

证明由条件（2.4）与［5］中定理2.5.2得到定理的结论.

定理1证明了算法的全局收敛性.下面给出二次收敛性分析.

定理2假设1-2成立，同时假设存在足够大的k0，使得k≥k0时算法1中dk均由（2.3）确立，同时有αk=1.如果对于算法1产生的收敛到w*的序列是非奇异的.则算法1是二阶收敛的.

证明由定理1我们有是收敛的，且w*为收敛点.因为F′(w*)是非奇异的，我们

从定理的假设知，当k≥k0时，算法1与牛顿法基本一致，因此由文献［4］中定理11.2知，{wk} 至少二阶收敛到w*.

4 数值实验

在这一节中，我们对算法1进行初步数值试验.选择文献［3］中给出的4阶3维对称张量A，其元素取值如下：

算法1中的参数分别取为ε=10-6,c1=10-4,c2=0.9.

表1 算法1的计算结果

从表1中可以看出，算法1能有效地求解出张量的特征对，同时也发现有些特征对容易被求出，有些特征对并不容易被求出.因此也需要今后进一步研究能求出不是已知特征对的方法.

［1］DUPONT T F，SCOTT L R.The power method for tensor eigenproblems and limiting directions of Newton iterates［J］.Nu⁃merical Linear Algebra with Applications，2013，20（6）：956-971.

［2］QI Liqun，WANG Fei，WANG Yiju.Z-eigenvalue methods for a global polynomial optimization problem［J］.Mathematical Programming，2009，118：301-316.

［3］KOLDA T G，MAYO J R.Shifted power method for computing tensor eigenpairs［J］.SIAM J Matrix Analysis & Applica⁃tions，2011，32（4）：1095-1124.

［4］NOCEDAL J，WRIGHT S J.Numerical optimization［M］.New York ：Springer-Verlag，1999.

［5］倪勤.最优化方法与程序设计［M］.北京：科学出版社，2009.