周會(huì)曉，倪 勤，曾梅蘭，2

（1.南京航空航天大學(xué) 理學(xué)院，江蘇 南京 210016；2.湖北工程學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 孝感 432000）

張量特征值問(wèn)題在多項(xiàng)式最優(yōu)化、超圖理論、高階馬爾科夫鏈、圖像科學(xué)等領(lǐng)域有廣泛的應(yīng)用，從而得到越來(lái)越多的關(guān)注.本文中，我們將張量Z-特征值問(wèn)題轉(zhuǎn)化為等價(jià)的非線性方程組，并用牛頓法求解，在算法中改進(jìn)了方向并引入線搜索技術(shù)使得算法具有全局與二階收斂性.

1 引言

考慮實(shí)數(shù)域R中包含nm個(gè)元素的m階n維張量A=(ai1，…im),ai1，…im∈R,1≤i1,…,im≤n.若A中的元素滿足，其中j1,…,jm為下標(biāo) {i1,…,im}的任意排列，則稱張量A為對(duì)稱張量.高階張量是多維線性映射，是矩陣的推廣，m=2 的張量即為矩陣.定義張量與向量的乘積為

其中x∈Rn，Axm-1為n維列向量.

定義1給定m階n維張量A，若存在λ∈R，x∈Rn，滿足

則稱λ為張量A的Z-特征值，x為與之對(duì)應(yīng)的Z-特征向量.

目前一些學(xué)者已嘗試用多種方法求解對(duì)稱張量的Z-特征值.文［1］采用定點(diǎn)分析理論，用移位冪方法求解張量Z-特征值問(wèn)題，獲得了線性收斂的求解算法.文［2］利用偽規(guī)范型思想，提出求三階三維張量所有Z-特征值的直接法.因此如何有效地求解一般對(duì)稱張量的Z-特征值仍值得深入研究.

2 求張量Z-特征值的牛頓法

現(xiàn)在我們將張量Z-特征值問(wèn)題（1.1）轉(zhuǎn)化為如下等價(jià)非線性方程組

若n+1維向量(x*,λ*)為非線性方程組（2.1）的解，則它為實(shí)對(duì)稱張量A的Z-特征對(duì).

現(xiàn)在考慮用牛頓法來(lái)求解該非線性方程組，下述引理給出了F(x,λ)的Jacobian 矩陣.

引理 1［3］若A為實(shí)對(duì)稱張量，則F(x,λ)的 Jacobian 矩陣F′(x,λ)為實(shí)對(duì)稱矩陣.F′(x,λ)具有如下形式：

記wT=(xT,λ)，則w為n+1維列向量，同時(shí)引入價(jià)值函數(shù)

顯然，若w*為F(w)=0 的根，則有Φ(w*)=0.由于Φ(w)≥0 對(duì)所有的w恒成立，因此F(w)=0 的任何一個(gè)根至少是Φ的一個(gè)整體極小點(diǎn).

牛頓法在任一迭代點(diǎn)處的搜索方向dk可由

確定.為了保證全局收斂性，dk需滿足

其中ε∈(0,1)為一確定常數(shù)，?Φ(wk)=F′(wk)F(wk).若dk不滿足（2.4），將對(duì)dk進(jìn)行修正，即令

λk的選取使得（2.4）滿足，具體技術(shù)見(jiàn)文獻(xiàn)［4］.

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

其中，0＜c1＜c2＜1.下面給出求實(shí)對(duì)稱張量的Z-特征值的牛頓法.

算法1

步1.取初值.給定c1,c2,0＜c1＜c2＜1,ε＞0，取初始點(diǎn)w0,k=0.

步3.檢驗(yàn)下降條件.若牛頓步dk使得（2.4）成立，則dk為所求下降方向；否則，由（2.5）給出dk.

步4.求步長(zhǎng)αk滿足（2.6）.

步5.wk+1=wk+αkdk,k=k+1，轉(zhuǎn)步2.

3 收斂性分析

本節(jié)給出算法1的收斂性分析，因此需要下面的假設(shè).

假設(shè)1水平集S={w:F(w)≤F(w0)}與包含S的開(kāi)凸集Ω 有界，其中w0為起始迭代點(diǎn).

假設(shè)2F(w)的 Jacobian 陣F′(w)關(guān)于w連續(xù)，?Φ在 Ω 上Lipschitz連續(xù)，即存在常數(shù)L＞0，使得

定理1如果假設(shè)1-2成立，那么由算法1產(chǎn)生的{wk}滿足

證明由條件（2.4）與［5］中定理2.5.2得到定理的結(jié)論.

定理1證明了算法的全局收斂性.下面給出二次收斂性分析.

定理2假設(shè)1-2成立，同時(shí)假設(shè)存在足夠大的k0，使得k≥k0時(shí)算法1中dk均由（2.3）確立，同時(shí)有αk=1.如果對(duì)于算法1產(chǎn)生的收斂到w*的序列是非奇異的.則算法1是二階收斂的.

證明由定理1我們有是收斂的，且w*為收斂點(diǎn).因?yàn)镕′(w*)是非奇異的，我們

從定理的假設(shè)知，當(dāng)k≥k0時(shí)，算法1與牛頓法基本一致，因此由文獻(xiàn)［4］中定理11.2知，{wk} 至少二階收斂到w*.

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

在這一節(jié)中，我們對(duì)算法1進(jìn)行初步數(shù)值試驗(yàn).選擇文獻(xiàn)［3］中給出的4階3維對(duì)稱張量A，其元素取值如下：

算法1中的參數(shù)分別取為ε=10-6,c1=10-4,c2=0.9.

表1 算法1的計(jì)算結(jié)果

從表1中可以看出，算法1能有效地求解出張量的特征對(duì)，同時(shí)也發(fā)現(xiàn)有些特征對(duì)容易被求出，有些特征對(duì)并不容易被求出.因此也需要今后進(jìn)一步研究能求出不是已知特征對(duì)的方法.

［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］倪勤.最優(yōu)化方法與程序設(shè)計(jì)［M］.北京：科學(xué)出版社，2009.