高階張量Pareto-特征值的估計(jì)

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州310018)

0 引 言

特征值互補(bǔ)問題在科學(xué)工程領(lǐng)域有廣泛應(yīng)用，如機(jī)械結(jié)構(gòu)系統(tǒng)、電路仿真、信號(hào)處理等問題都可轉(zhuǎn)化成特征值互補(bǔ)問題并求解。眾所周知，張量特征值互補(bǔ)問題與其特征值問題關(guān)系密切，而后者不可以在多項(xiàng)式時(shí)間內(nèi)求得。著名的Gerschgorin型(圓盤)定理刻劃矩陣的特征值估計(jì)，在數(shù)值分析中有重要應(yīng)用。張量特征值是2005年提出的新概念[1]，張量特征值互補(bǔ)問題是矩陣特征值互補(bǔ)問題和張量特征值問題的推廣，也與一類非線性的微分包含問題密切相關(guān)，引起了廣泛關(guān)注[2]。與矩陣特征值問題不同，張量特征值計(jì)算是NP-難問題，張量特征值及其個(gè)數(shù)計(jì)算遠(yuǎn)比矩陣情形復(fù)雜。但與矩陣類型相似，張量特征值或Pareto-特征值可以判別高次多項(xiàng)式的正定性且實(shí)際應(yīng)用廣泛。本文給出張量特征值互補(bǔ)問題中的Pareto-特征值的估計(jì)，它們是矩陣情形相應(yīng)結(jié)果(如圓盤定理)的張量推廣，有重要理論意義和潛在應(yīng)用價(jià)值。

1 問題及相關(guān)預(yù)備知識(shí)

本文考慮張量特征值互補(bǔ)問題(簡記TEiCP)，即求λ ∈R和x ∈Rn+{0}，使得:

定義1 設(shè)A為m階n維張量。若A的任意元ai1i2…im在下標(biāo)任意置換下均保持不變，則稱A是對稱的。

定義2[3]設(shè)A為m階n維張量。若存在非空集I ?N:= {1，2，…，n}，使得對任意i1∈I和i2，…，im?I，均有ai1i2…im=0，則稱A為可約，否則稱A為不可約。

定義3 設(shè)A為m階n維張量。若A 中任意元素均非負(fù)，則稱A是非負(fù)。若對任意x ∈Rn+{ 0}，均有，則稱A為協(xié)正定(嚴(yán)格協(xié)正定)。

定義4[4]設(shè)A為m階n維張量。若存在滿足η≥ρ(C)(η ＞ρ(C))的正實(shí)數(shù)η和非負(fù)張量C，使得A=ηⅠ-C，則稱A是M-張量(強(qiáng)-M-張量)。

定義5[5]設(shè)A為m階n維張量。若從Axm-1≥0可推出x ≥0，則稱A是單調(diào)張量。

命題1[6]設(shè)和是m階n維張量。則λ∈R是張量對(A，B)的Pareto-特征值，當(dāng)且僅當(dāng)存在非空集J?N和向量使得:

針對滿足式(2)的w，定義n維向量x(若i∈J，取xi=wi;否則取xi=0)。易知，x是(A，B)對應(yīng)于λ的Pareto-特征向量。特別地，若x∈Rn++(即J=N)，則λ 即為(A，B)的特征值。當(dāng)B =Ⅰ時(shí)，λ 被簡稱為A的Pareto-特征值，其全體記作σP(A)。其中，Ⅰ=(δi1…im)1≤i1，…，im≤n表示單位張量，即δi1…im=1，若i1=…=im;否則 δi1…im=0。此時(shí)，式(1)中，Bxm-1變成 x[m-1]，相 應(yīng)的式(2)變成。其中，x[m-1]表示其分量為的n維向量。

2 Pareto-特征值的估計(jì)

張量特征值互補(bǔ)問題與一類高次齊次多項(xiàng)式優(yōu)化問題關(guān)系密切，即使在對稱張量的情形下，求解張量特征值互補(bǔ)問題也是一個(gè)困難任務(wù)。本節(jié)關(guān)注于Pareto-特征值的估計(jì)問題。

定理1 設(shè)A=(ai1i2…im)1≤i1，i2，…，im≤n是m階n維張量，則任意λ ∈σP(A)，有:

證明 因?yàn)棣?∈σP(A)，由命題1 知，存在非空集J ?N和，使得:

記wi0=max {wi:i ∈J} 。由式(5)知由此，即得式(3)。特別地，若A 對角占優(yōu)，則有從而式(4)成立。定理1 證畢。

當(dāng)m=2時(shí)，易知，上述定理即為矩陣特征值互補(bǔ)問題的圓盤定理。關(guān)于一般的特征值互補(bǔ)問題Ax =λBx(其中λ ∈C(復(fù)數(shù)域)，x ∈Cn{ 0})，若A，B是嚴(yán)格對角占優(yōu)矩陣，則有下面的定理表明，關(guān)于張量特征值互補(bǔ)問題也有類似結(jié)論。

定理2 設(shè)A，B為非零的m階n維張量。若A 對角占優(yōu)且B是不可約的，則對任意λ ∈σP(A，B)，有

定理3 設(shè)A，B是m階n維張量，其中B 非負(fù)且嚴(yán)格協(xié)正定。若A 滿足條件bi1…im=0?ai1…im≤0，則對任意λ ∈σP(A，B)，有其中

證明 記x為對應(yīng)于λ的Pareto-特征向量。由于B 非負(fù)且嚴(yán)格協(xié)正定，得Bxm＞0和bii…i＞0。從而由式(1)知，有:

如果m=2，則考慮問題退化成矩陣情形，但所得結(jié)論仍然是新的。

3 兩類特殊張量Pareto-特征值的非負(fù)性

張量Pareto-特征值的非負(fù)性有許多實(shí)際應(yīng)用。針對M-張量及單調(diào)張量，本文有如下定理，它們分別是矩陣情形相應(yīng)結(jié)論的推廣。

定理4 設(shè)A，B為m階n維張量。若A是對稱的M-張量，B是嚴(yán)格協(xié)正定的，則任意λ∈σP(A，B)都是非負(fù)的。進(jìn)一步，若A是對稱的強(qiáng)M-張量，則任意λ∈σP(A，B)都是正的。

證明 設(shè)λ∈σP(A，B)，x是相應(yīng)Pareto-特征向量。因A是M-張量(強(qiáng)-M-張量)，則存在滿足η ≥ρ(C)(η ＞ρ(C))的正實(shí)數(shù)η和非負(fù)張量C，使得A=ηⅠ-C。從而，有又由于B為嚴(yán)格協(xié)正定，知Bxm＞0(?x ≠0)。進(jìn)一步，得:

因A是對稱的，從而C是對稱的。易知，求解C的譜半徑ρ(C)(即最大的H-特征值)等價(jià)于求解優(yōu)化問題[8]所以，有:

由此和式(8)知λ ≥0(λ ＞0)。定理4 證畢。

已知，對稱的Z-張量A是強(qiáng)-M-張量，當(dāng)且僅當(dāng)A是嚴(yán)格協(xié)正定的[9]。從而，由定理4 知，嚴(yán)格協(xié)正定對稱Z-張量的Pareto-特征值均為正。下面的定理是矩陣相應(yīng)結(jié)論的推廣。

定理5 設(shè)A，B為m階n維張量。若m為偶數(shù)，A是單調(diào)張量且B是非負(fù)的，則任意λ∈σP(A，B)都是正的。

證明 設(shè)λ∈σP(A，B)。x是相應(yīng)的Pareto-特征向量。由命題1 知，存在J?N和使顯然，由于A是單調(diào)張量，AJ也是單調(diào)張量。若λ≤0，則因m為偶數(shù)且B 非負(fù)，知由單調(diào)張量的定義知，-w≥0。這與矛盾。所以任意Pareto-特征值都是正的。定理5 證畢。

4 結(jié)束語

由于張量特征值互補(bǔ)問題的求解是NP-難問題，本文給出若干張量Pareto-特征值的估計(jì)式，并證明強(qiáng)M-張量和單調(diào)張量的Pareto-特征值均為正。進(jìn)一步的估計(jì)性質(zhì)將是下一步研究的內(nèi)容。

[1]Qi L Q.Eigenvalues of a real supersymmetric tensor[J].Journal of Symbolic Computation，2005，40(6):1302-1324.

[2]Song Y S，Qi L Q.Eigenvalue analysis of constrained minimization problem for homogeneous polynomial[EB/OL].[2013-03-16].http://arxiv.org/abs/1302.6085v2.

[3]Chang K C，Pearson K，Zhang T.Perron Frobenius theorem for nonnegative tensors[J].Communications in Mathematical Sciences，2008，6(2):507-520.

[4]Zhang L P，Qi L Q，Zhou G L.M-tensors and some applications[J].SIAM Journal on Matrix Analysis and Applications，2014，35(2):437-452.

[5]Ding W，Qi L Q，Wei Y.M-tensor and nonsingular M-tensors[J].Linear Algebra and its Applications，2013，439(10):3264-3278.

[6]Adly S，Rammal H.A new method for solving Pareto eigenvalue complementarity problems[J].Computational Optimization and Applications，2013，55(3):703-731.

[7]劉裔宏.關(guān)于廣義特征值估計(jì)的一個(gè)Gerschgorin 定理[J].工科數(shù)學(xué)，1994，10(1):49-51.

[8]Qi L Q.Symmetric nonnegative tensors and copositive tensors[J].Linear Algebra and its Applications，2013，439(1):228-238.

[9]陳景良，陳向暉.特殊矩陣[M].北京:清華大學(xué)出版社，2000:276-286.