金雨軒，徐旭冬，趙金玲

(北京科技大學 數(shù)理學院，北京 100083)

0 引言

本文研究張量分裂可行問題，即求一個向量x，使得

x∈C并且Axm-1∈Q，

(1)

其中：C?Rn,Q?Rp，Rn和Rp分別代表n維和p維歐氏空間。A是m階p×n×…×n維張量，即張量A=(ai1i2…im)，其中，i1= 1,…,p；ij= 1,…,n(j= 2,…,m)。

張量分裂可行問題可以視為分裂可行問題的一種推廣。分裂可行問題廣泛應用于圖像重建、信號處理等領域中[1-2]。這一模型最早由文獻[3]提出，問題描述為：求一個向量x，使得

x∈C，Ax∈Q，

其中：A為矩陣。后來，分裂可行問題被文獻[4]進一步推廣為多集分裂可行問題。

CQ算法是求解分裂可行問題的經(jīng)典算法，其他求解分裂可行問題和多集分裂可行問題的方法，都可以看作是CQ算法的變形。至今已有許多學者對CQ算法進行了研究和改進[5-12]。但是，CQ算法主要應用于問題中A是矩陣的形式，并且由于CQ算法需要矩陣A的特征值，而張量的特征值與矩陣不同，所以尚無法直接應用于張量分裂可行問題。而且，CQ算法的計算效率依賴于初始點x0和參數(shù)γ的選擇。

近期，文獻[13]提高了求解多集分裂可行問題的效率,文獻[14]利用牛頓投影法求解分裂可行問題，文獻[15]研究了求解特定Banach空間中的多集分裂可行問題，但是對于張量分裂可行問題的研究較少。

半定規(guī)劃是線性規(guī)劃的推廣，許多凸規(guī)劃問題都可以轉(zhuǎn)化為半定規(guī)劃問題。文獻[16-18]提出了用矩陣不等式表示半代數(shù)集合,即一種由多項式不等式定義的集合。文獻[19]通過moment松弛法，將A為矩陣的分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題來求解，并證明了相關理論。這一方法對于集合C和Q非凸的情況也很有效。本文受到這一思路的啟發(fā)，將張量分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題來求解。

本文主要研究由多項式定義集合的張量分裂可行問題，即式(1)中的集合C和Q由多項式給出，如下所示：

C={x∈Rn|f(x)≥0},Q={y∈Rm|g(y)≥0}。

將張量分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題,即將式(1)轉(zhuǎn)化為多項式f(x)≥0，h(x)≥0,通過松弛的方法將問題映射到更高維度的空間中，求得高維空間中的解，再將解通過投影的方式映射回低維空間，最后判斷是否能求出可行解。

1 半正定松弛原理

1.1 預備知識

設A是m階n維張量，則A包括nm個元素:

A=(ai1i2…im),ai1i2…im∈R，

其中：ij=1,2，…，n,j=1,2,…,m,當m=2時，張量即變成n×n維方陣。本文所研究問題中的張量并非“方”的，其中m階張量A的維數(shù)是p×n×…×n。

當向量x=[x1,x2，…，xn]T，張量向量乘法為:

所得到的Axm-1是p維向量，Axm-2是p×n階矩陣，Ax是m-1階張量，維數(shù)變?yōu)閜×n×…×n(少一層)。

1.2 分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題

張量分裂可行問題欲求一點x，滿足

x∈C并且Axm-1∈Q。

A是m階張量，維數(shù)為p×n×…×n。 集合C和Q由多項式不等式給出：

C={x∈Rn|f(x)≥0}，Q={y∈Rm|g(y)≥0}，

(2)

將Axm-1代入g(y)，得到集合W：

Axm-1=[y1,y2,…,yp]T，w(x):=g(Axm-1)；

W={x∈Rn|w(x)≥0}。

張量的分裂可行問題就等價于找到一點x，并且滿足

x*∈C∩W={x∈Rn|f(x)≥0，w(x)≥0}。

(3)

(4)

由此，將張量分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題(4)，并且給出了相應的目標函數(shù)和約束條件。

1.3 localizing矩陣

其中:Fα為對稱矩陣。

(5)

易知，y0=1。

(6)

(7)

1.4 松弛化原理

半定規(guī)劃原問題為：

(8)

定理2若x*∈C∩W，則x*∈Hk。Hk為C∩W的松弛化集合的投影。

C∩W={x|f(x)≥0，w(x)≥0} 。

C∩W總是包含在集合Hk中，s=max 「def(f)/2?,「def(w)/2?，對于所有k≥s，每個Hk是C∩W的半定松弛后的集合，并且C∩W?Hk，包含以下嵌套關系：

Hs?Hs+1?…?C∩W。

令y=[x]2k，將式(4)映射到高維空間中，即得到k階Lasserre moment松弛(式8)，利用半定規(guī)劃松弛法求y，得到最終的x*。最后判斷，若x*∈C，Axm-1∈Q，則得到張量分裂可行問題(1)的解。

1.5 算法步驟

集合C和Q都可化為多項式的形式，令k=d。

步驟Ⅰ 將張量分裂可行問題通過moment松弛法轉(zhuǎn)化為半定規(guī)劃問題(4)。

步驟Ⅱ 求解半定規(guī)劃松弛化問題，若可以得到可行解y*，則進入步驟Ⅲ，若沒有y*符合該半定規(guī)劃問題，則停止計算。

步驟Ⅲy*投影到Rn中，得到最終的x*，判斷若x*∈C，Axm-1∈Q，則得到張量分裂可行問題(1)的解。若不成立，k=k+1，返回步驟Ⅱ。

2 數(shù)值實驗

本節(jié)主要介紹利用半定松弛法求解張量分裂可行問題的數(shù)值實驗結(jié)果。所有數(shù)值計算均應用于處理器為 Intel(R)Core(TM)i7-7500U CPU(2.70 GHz)的筆記本電腦上，所使用的軟件版本為MATLAB r2016a。主要利用了GloptiPoly[20]、SeDuMi[21]和張量工具箱[22]求解半定規(guī)劃松弛。

例1求向量x，使得x∈C并且Axm-1∈Q。C和Q定義為：

其中：集合C為球體；r1為該球體的半徑；100代表各分量值都為100的向量。A為4階張量,維數(shù)為3×2×2×2，Aijkl=0.015i+0.01(j+k+l),共有24個元素，展開形式如下所示：

將維數(shù)為3×2×2×2的張量A與未知量x=[x1,x2]相乘，得到3維向量Axm-1：

將C和Q化簡為式f(x)和w(x)，再將Axm-1代入g(y)求得w(x)：

g(y):=(y1-100)2+(y2-100)2+(y3-100)2≤4 900；

利用半定松弛法求解例1，改變r1的大小時,求解結(jié)果如表1所示。

表1 例1的求解結(jié)果

本例主要探究了r1的改變對于該算法有何影響以及是否穩(wěn)定。結(jié)果表明:隨著r1的不斷增大，半定松弛算法所花費的時間相差不大，但是迭代次數(shù)有小幅上升。當r1=5時，可行的解距離f(x)的邊界較近，出現(xiàn)了沒有計算出可行解的情況。 但是當r1不斷增大時，可行解距離f(x)的邊界較遠時，計算情況較好。

例2張量分裂可行問題中C和Q與例1一致，取r1=10,考慮張量A的大小對于算法的影響，當i=j=k=l=1時，A1111=a(0.015i+0.01(j+k+l))。 其他情況時，Aijkl=0.015i+0.01(j+k+l)。根據(jù)A計算得出相應的Axm-1、f(x)和w(x)，再利用半定松弛法求解。改變a的大小時,求解結(jié)果如表2所示。

表2 例2的求解結(jié)果

本例主要探究了張量中某個值的改變對于該算法有何影響以及是否穩(wěn)定。 結(jié)果表明：花費的時間與張量A的數(shù)值相差不大。 并且由A1111是與x1相乘可以看出，隨著a的增大，w(x)中x1的系數(shù)不斷增大，導致解x*中的x1不斷縮小，x2不斷增大。

例3張量分裂可行問題(1)中C和Q定義為:

Aijkl=0.015i+0.01(j+k+l),(1≤i≤5,1≤j,k,l≤4)；

其中：A為4階張量,維數(shù)為5×4×4×4，共有320個元素，與前2個例子相比，維數(shù)有所增加；100代表各分量值都為100的向量。

根據(jù)A計算得出相應的Axm-1、f(x)和w(x)，再利用半定松弛法求f(x)和w(x)的解，求解結(jié)果如表3所示。

表3 例3和例4的求解結(jié)果

本例主要探究了張量A的維數(shù)與算法之間的關系。與例1相比，張量維數(shù)由3×2×2×2維增加到5×4×4×4維，元素個數(shù)由24個增加到320個，變量的個數(shù)也由2個變?yōu)?個。隨著變量個數(shù)的增加，計算時間和迭代次數(shù)都有所增加，但是該算法依然可以得出結(jié)果。

例4A為6階張量,維數(shù)為3×2×2×2×2×2，共有96個元素，Aijkloq=0.015i+0.01(j+k+l+o+q)(0≤i≤3,0≤j,k,l,o,q≤2)。為了確保有解，C和Q定義為:

其中：200代表各分量值都為200的向量。

根據(jù)A計算得出相應的Axm-1、f(x)和w(x)，再利用半定松弛法求f(x)和w(x)的解，求解結(jié)果如表3所示。

本例主要探究了張量A的階數(shù)與算法之間的關系。與例1相比，張量階數(shù)由4階增加到6階，計算時間和迭代次數(shù)都相差不大，該算法依然可以計算出可行解。

3 結(jié)論

本文提出用半定松弛法解決張量分裂可行問題，將張量分裂可行問題轉(zhuǎn)化為半定規(guī)劃問題，再利用半定松弛的算法求解，并且給出了半定松弛法的收斂性證明。對于集合C取不同范圍、張量A取不同值、張量A取不同維數(shù)和張量A取不同階數(shù)的情況都進行了數(shù)值實驗，本文算法均可以計算出可行解，驗證了算法的可行性和有效性。