求解張量分裂可行問題的半定松弛法

金雨軒，徐旭冬，趙金玲

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

0 引言

本文研究張量分裂可行問題，即求一個(gè)向量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)。

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

x∈C，Ax∈Q，

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

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

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

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

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

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

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

1 半正定松弛原理

1.1 預(yù)備知識(shí)

設(shè)A是m階n維張量，則A包括nm個(gè)元素:

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

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

當(dāng)向量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ī)劃問題

張量分裂可行問題欲求一點(diǎn)x，滿足

x∈C并且Axm-1∈Q。

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

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}。

張量的分裂可行問題就等價(jià)于找到一點(diǎn)x，并且滿足

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

(3)

(4)

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

1.3 localizing矩陣

其中:Fα為對(duì)稱矩陣。

(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?，對(duì)于所有k≥s，每個(gè)Hk是C∩W的半定松弛后的集合，并且C∩W?Hk，包含以下嵌套關(guān)系：

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都可化為多項(xiàng)式的形式，令k=d。

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

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

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

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

本節(jié)主要介紹利用半定松弛法求解張量分裂可行問題的數(shù)值實(shí)驗(yàn)結(jié)果。所有數(shù)值計(jì)算均應(yīng)用于處理器為 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個(gè)元素，展開形式如下所示：

將維數(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，改變r(jià)1的大小時(shí),求解結(jié)果如表1所示。

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

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

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

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

本例主要探究了張量中某個(gè)值的改變對(duì)于該算法有何影響以及是否穩(wěn)定。 結(jié)果表明：花費(fèi)的時(shí)間與張量A的數(shù)值相差不大。 并且由A1111是與x1相乘可以看出，隨著a的增大，w(x)中x1的系數(shù)不斷增大，導(dǎo)致解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個(gè)元素，與前2個(gè)例子相比，維數(shù)有所增加；100代表各分量值都為100的向量。

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

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

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

例4A為6階張量,維數(shù)為3×2×2×2×2×2，共有96個(gè)元素，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計(jì)算得出相應(yīng)的Axm-1、f(x)和w(x)，再利用半定松弛法求f(x)和w(x)的解，求解結(jié)果如表3所示。

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

3 結(jié)論

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