楊廷梅， 劉奇龍， 陳震， 許云霞

貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 貴陽(yáng) 550025

設(shè)R是實(shí)數(shù)域， Rn是所有n維實(shí)向量的集合． 張量是向量和矩陣的高階推廣， 通常m階n維實(shí)張量是由nm個(gè)實(shí)數(shù)構(gòu)成的多維數(shù)組， 即

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

其中N={1， 2， …，n}，M={1， 2， …，m}． 記R[m， n]為m階n維實(shí)張量的全體構(gòu)成的集合， 特別地， 當(dāng)m=0時(shí)， R[0， n]簡(jiǎn)記為R， 當(dāng)m=1時(shí)， R[1， n]簡(jiǎn)記為Rn． 如果實(shí)張量A=(ai1i2…im)的元素滿足

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

p是指標(biāo)集{1， 2， …，m}上的任意置換， 則稱A是實(shí)對(duì)稱張量．

文獻(xiàn)[1]提出了張量特征值與特征向量(也稱為張量特征對(duì))的概念， 并討論Z-特征值和H-特征值的一些性質(zhì)． 張量特征值是矩陣特征值的高階推廣， 下面給出實(shí)對(duì)稱張量的Z-特征值的定義．

定義1[1]設(shè)A∈R[m ， n]是實(shí)對(duì)稱張量， 如果存在λ∈R和非零向量x=(x1， …，xn)∈Rn使得

Axm-1=λx，xTx=1

(1)

則稱λ為A的Z-特征值，x為與λ相對(duì)應(yīng)的Z-特征向量， 或稱(λ，x)是A的Z-特征對(duì)， 其中Axm-1是n維向量， 第i個(gè)分量為

由于對(duì)稱張量Z-特征值在數(shù)據(jù)挖掘[2-3]、 目標(biāo)跟蹤[4]和超圖匹配[5]等許多實(shí)際問(wèn)題中有著重要應(yīng)用， 使得對(duì)稱張量Z-特征值問(wèn)題逐漸成為張量譜理論研究的熱點(diǎn)問(wèn)題[6-13]． 文獻(xiàn)[14]在研究基于張量算法的高階圖匹配時(shí)提出了包含邊和超邊的匹配模型． 文獻(xiàn)[15]從文獻(xiàn)[14]中提出不同階對(duì)稱張量組Z-特征值問(wèn)題， 定義如下．

定義2[15]設(shè)Ai∈R[i， n]是實(shí)對(duì)稱張量，i=2，3， 如果存在λ∈R和非零向量x∈Rn使得

A3x2+A2x=λx，xTx=1

(2)

近年來(lái)， 文獻(xiàn)[16]提出應(yīng)用Newton-Gauss-Seidel法可求解不同階張量組方程， 接著文獻(xiàn)[15]提出通過(guò)SS-HOPM求解不同階對(duì)稱張量組Z-特征值問(wèn)題(2)． 本文接下來(lái)介紹應(yīng)用改進(jìn)的Newton-法求解問(wèn)題(2)．

1 改進(jìn)的Newton-法求不同階對(duì)稱張量組Z-特征值

首先， 回顧Newton-法求解對(duì)稱張量Z-特征值， 從而將該方法推廣到求解不同階對(duì)稱張量組Z-特征值． 為了解決對(duì)稱張量Z-特征值問(wèn)題(1)， 文獻(xiàn)[17]將對(duì)稱張量組Z-特征值問(wèn)題(1)等價(jià)轉(zhuǎn)化為如下非線性方程組解的問(wèn)題：

針對(duì)問(wèn)題(2)， 將不同階對(duì)稱張量組Z-特征值問(wèn)題等價(jià)轉(zhuǎn)化為如下非線性方程組的解的問(wèn)題：

(3)

引理1[18]若Ai∈R[i， n]是實(shí)對(duì)稱張量，i=2，3， 則F(x，λ)的Jacobi矩陣?F(x，λ)為實(shí)對(duì)稱矩陣， 且具有如下形式：

?F(vk)pk=-F(vk)

(4)

為了確保Newton-法的全局收斂性， 根據(jù)文獻(xiàn)[17]提出的方法， 引入F(v)的價(jià)值函數(shù)

顯然， 若F(v*)=0， 則f(v*)=0． 由于f(v)≥0對(duì)所有的v恒成立， 因此，f(v)的全局極小值點(diǎn)為F(v)=0的根．

(5)

其中?f(vk)=?FT(vk)F(vk)，δ越靠近1， 收斂速度越快． 當(dāng)pk不滿足(5)式時(shí)， 對(duì)pk進(jìn)行修正， 修正式為

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

其中?F-T(vk)表示Jacobi矩陣?F(vk)的逆的轉(zhuǎn)置， 令

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

(6)

通過(guò)化簡(jiǎn)得

又由文獻(xiàn)[19]中的算法3.3知τk的選取使Bk為正定矩陣且使(5)式成立， 具體過(guò)程見(jiàn)算法1．

算法1[19] τk選取的算法輸入: 矩陣Hk=?FT(vk)?F(vk)6: for k=0, 1, …, do輸出: τk+17: ifL·LT=Hk+τkIn+1選取初始點(diǎn): 給定常數(shù)σ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

選取步長(zhǎng)βk滿足如下Wolfe條件

(7)

其中： 0

算法2 改進(jìn)的Newton法求解不同階對(duì)稱張量組Z特征值.輸入: 對(duì)稱張量{Ai}3i=2∈R[i, n], 初始值x0,λ0,β, 給定常數(shù)δ,ε,ρ∈(0, 1), 0f(vk)+c1β?fT(vk)pk‖?f(vk+βpk)Tpk

2 收斂性分析

本節(jié)分析算法2的收斂性， 首先給出一些假設(shè)．

假設(shè)1f在Rn+1上有下界， 并且在包含水平集E={v：f(v)≤f(v0)}的開(kāi)集Ω上連續(xù)可微， 其中v0為起始迭代點(diǎn)．

假設(shè)2f的梯度?f在Ω上Lipschitz連續(xù)． 即存在一個(gè)常數(shù)L>0， 使得

設(shè)d(f)=3, ch(f)=3-4=-1,事實(shí)上R3已經(jīng)考慮到了3-面的所有情況,依次來(lái)討論。若f是一個(gè)(3,3,3)-面,由引理1(3)和R3.1得若f是一個(gè)(3,3,k)-面(k=4,5,6),由引理1.3和R3.2得若f是一個(gè)(3,3,7+)-面,由R3.3得ch′(f)≥ch(f)+1=-1+1=0。若f是一個(gè)(3,4,4)-面,由引理1(2)和R3.4得 若f是一個(gè)(3,4,5+)-面,由R3.5得若f是一個(gè)(3,5+,5+)-面,由R3.6得 若f是一個(gè)(4+,4+,4+)-面,由R3.7得綜上,3-面得證。

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

引理2[19]如果f滿足假設(shè)1和2， 那么考慮vk+1=vk+αkpk這種形式的迭代， 其中pk是下降方向，αk是步長(zhǎng)且滿足Wolfe條件(7)， 有如下不等式成立

其中θk是pk與-?f(vk)的夾角．

定理1如果函數(shù)f(v)滿足假設(shè)1和2， 那么由算法2產(chǎn)生的序列{vk}滿足

即改進(jìn)的Newton-法全局收斂．

定理2若假設(shè)1，2，3成立， 且βk=1． 如果?F(v*)是非奇異的， 其中v*是算法2產(chǎn)生的序列{vk}的收斂點(diǎn)， 那么算法2超線性收斂．

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

即{vk}超線性收斂到v*．

3 數(shù)值實(shí)驗(yàn)

本節(jié)使用文獻(xiàn)[15]中給出的兩個(gè)例子進(jìn)行數(shù)值實(shí)驗(yàn)， 并對(duì)二者的結(jié)果進(jìn)行比較． 所有試驗(yàn)都在MATLAB R2015a中完成， 其配置為： Intel(R) Celeron(R)3205U 1.50 GHz CPU和4.00G RAM內(nèi)存．

例1設(shè)實(shí)對(duì)稱張量A3=(aijk)∈R[3，3]和實(shí)對(duì)稱正定矩陣A2=(bij)∈R[2，3]， 且元素取值如下：

使用兩種算法進(jìn)行數(shù)值實(shí)驗(yàn)， 在算法2中選取的參數(shù)分別是ε=10-7，c1=0.1，c2=0.8， 并用分布在[-2， 2]中的不同隨機(jī)初始點(diǎn)x0和λ0進(jìn)行200次實(shí)驗(yàn)， 最大迭代次數(shù)為1 000次， 如果‖?f(vk)‖≤ε， 說(shuō)明算法收斂． 實(shí)驗(yàn)結(jié)果見(jiàn)表1-3．

表1 算法2在例1上的數(shù)值結(jié)果

表2[15] SS-HOPM算法在例1上的數(shù)值結(jié)果

表3 兩種算法計(jì)算相同特征值所用平均時(shí)間

由表1與表2可知， 該數(shù)值實(shí)驗(yàn)得出的結(jié)果與文獻(xiàn)[15]中的結(jié)果相比： 第一， 兩種方法都能求出特征值0.019 4和0.431 4， 但根據(jù)表3， 可知算法2計(jì)算所用的時(shí)間更少一些； 第二， 算法2可以求出14個(gè)特征值里的9個(gè)， 比文獻(xiàn)[15]中用SS-HOPM所求的特征值多了5個(gè)， 其中有7個(gè)與文獻(xiàn)[15]求出的特征值不相同．

例2實(shí)對(duì)稱張量A3=(aijk)∈R[3， 3]和實(shí)對(duì)稱矩陣A2=(bij)∈R[2， 3]， 且元素取值如下：

再次使用兩種算法進(jìn)行數(shù)值實(shí)驗(yàn)， 算法2選取的參數(shù)分別是ε=10-7，c1=0.000 1，c2=0.8， 并用分布在[-10， 10]中的不同隨機(jī)初始點(diǎn)x0和λ0進(jìn)行100次實(shí)驗(yàn)， 其最大迭代次數(shù)為1 000次， 如果‖?f(vk)‖≤ε， 說(shuō)明算法收斂， 結(jié)果見(jiàn)表4，5．

表4 算法2在例2上的數(shù)值結(jié)果

表5[15] SS-HOPM算法在例2上的數(shù)值結(jié)果

對(duì)表4和表5的結(jié)果比較可知， 算法2要比SS-HOPM所求特征對(duì)多， 兩種方法都能算出特征值0.785 9， 但算法2用時(shí)為0.085 451 s， SS-HOPM用時(shí)為0.144 277 s， 可見(jiàn)算法2用時(shí)較少， 且與文獻(xiàn)[15]相比， 得到了新的特征值．

4 結(jié)論

數(shù)值例子實(shí)驗(yàn)表明， 改進(jìn)的Newton-法是一種有效的求解不同階對(duì)稱張量組Z-特征值的方法且算法2是全局超線性收斂的． 因此， 改進(jìn)的Newton-法和SS-HOPM相互補(bǔ)充， 可以求出更多的不同階對(duì)稱張量組的Z-特征值．