基于近端算法的DC規劃解球面約束下四次型極小化問題

舒 杭,王 潔

(1.杭州電子科技大學理學院,浙江 杭州 310018;2.中國計量大學理學院,浙江 杭州 310018)

0 引 言

四次型極小化問題是張量逼近和多項式優化的交叉部分,是一類特殊的多項式優化問題。此問題有很多來源,并且在實際中有著廣泛應用,許多實際問題的模型可表達為此形式,如圖的穩定集問題、四階張量的最佳秩一逼近問題、量子物理中的幾何度量、光譜超圖理論、擴散峰醫學成像等。Aittomaki等[1]考慮波束優化問題并將其建模為多元四次型極小化模型。Aubry等[2]通過優化取實值的四次極小化模型來求解雷達信號問題。Mariere等[3]提出四次多項式優化模型并將其應用于數字通信的研究。

對于球面約束下的四次型極小化問題,可使用擴展的數值線性代數中的方法,例如對稱移位高階冪法(SS-HOPM),并且可以建立這種方法的良好性質。然而,采用一般非線性優化技術無法得出計算解的質量。特別是,我們無法判斷計算解的全局最優性。對于能判斷解的最優性的SDP松弛方法,卻無法處理大規模問題。因此,我們對問題進行一些轉化,使得重構后的問題變為兩個凸函數的差的形式,此時就能采用DC算法來求解。但是該算法子問題的難度很大程度上取決于DC分解的選擇,一般情況下子問題還需要借助于其他算法來求解,比如加速近端梯度(APG)算法,這也是DC算法的一個缺陷。我們根據近端算法,對DC算法進行一定改造,使得可以在DC算法的外框架上使用APG,簡化子問題的求解,使得子問題不再需要借助于其他算法,我們將該方法根據加速方案的選擇分別記為pDCA和aDCA。實驗結果表明,此方法相較于對稱移位高階冪法和一般的DCA方法,在計算時間以及解的質量方面都得到了很大的提升。

1 問題描述及轉化

張量是基于標量和矢量向更高維度的推廣,標量和矢量都是張量的特殊情況,即標量和矢量分別是零階張量和一階張量。

(1)

s=i1+(i2-1)n,t=i3+(i4-1)n。

(2)

再將變量從向量轉化為矩陣。令X=xxT,此時目標函數等價于〈AX,X〉。此時約束條件中還有變量未進行變換。

定理1[5]令x∈Rn,則集合

U={x|x∈Rn,xTx=1}

等價于集合

V={X|X=xxT,X≥0,〈I,X〉=1,rank(X)=1},

其中〈I,X〉=trace(X),X≥0表示矩陣為半正定矩陣,rank(X)表示為X的秩。

根據定理1,我們可以將對x的約束條件轉化為對X的約束條件。此時問題形式如下:

min〈AX,X〉 s.t.X≥0, 〈I,X〉=1,rank(X)=1,

(3)

(4)

因為矩陣A是n2×n2的實對稱矩陣,則可將矩陣A對角化,對應的正交矩陣設為Q。形式如:A=QTΛQ,其中Λ是由矩陣A特征值構成的對角矩陣。顯然我們能將Λ拆分為兩個正定的對角矩陣的差的形式,即Λ=Λ1-Λ2。設B=QTΛ1Q,C=QTΛ2Q。則〈AX,X〉=〈BX,X〉-〈CX,X〉。此時問題(4)的求解與以下問題的求解是等價的:

(5)

(6)

(7)

最終問題(7)等價于:

ming(X)-h(X) s.t.X∈Rn×n,

(8)

我們記P(X)=g(X)-h(X),那么P(X)即為所求目標函數。

2 pDCA以及aDCA

對于優化問題ming(X)-h(X),DC算法的一般迭代格式是在每一次迭代的過程中利用次微分對目標函數的凹部分進行線性近似,從而得到一個目標函數的凸近似。即:

其中λt∈?h(Xt)。

對問題(8)使用以上迭代形式,此時我們得到pDCA的子問題形式為:

(9)

基于以上討論,現在給出pDCA的主要步驟:

Input:給定一個四階實對稱張量,選定初始點X0∈Ω,并設置X-1=X0輸入懲罰參數,{βt}?[0,1); for t=0,1,2,… 取ξt=2CXt+ρΓt,Γt∈?Xtσ, 令Yt=Xt+βt(Xt-Xt-1), Xt+1=argminX∈Rn×n<2BYt-ξt,X>+L2X-Yt2+δΩ(X) =PΩYt-1L[2BYt-ξt] , end for

3 收斂性分析

定理3[9](全局子序列收斂性){Xt}為pDCA算法生成的序列,則以下陳述成立:

(1)序列{Xt}有界。

(3)序列{Xt}的任意聚點都是P(X)的穩定點。

命題1設{Xt}為pDCA算法生成的序列,則以下陳述成立:

(2)設{Xt}聚點的集合為N,則函數P在集合N上恒為μ。

證明注意到Xt+1是一個強凸函數的全局極小值點,根據強凸函數的全局極小值點的唯一性和存在性定理,我們有:

(10)

另一方面〈BX,X〉是梯度L利普希茨連續的,我們有:

第二個不等式是因為次梯度不等式,第三個不等式是因為式(10),最后一個是因為函數〈BX,X〉的凸性。再將Yt的定義代入后得到

整理后得:

(11)

根據(11)可以得到序列

(12)

命題2(次線性收斂)設{Xt}為pDCA算法生成的序列,那么整個序列收斂的速度至少是次線性收斂的。

?P(Xt+1)=2BXt+1-2CXt+1-ρΓt+1+NΩ(Xt+1),

另一方面,從pDCA算法的最優性條件得出

0∈2BYt-2CXt-ρΓt+L(Xt+1-Yt)+NΩ(Xt+1),

因此存在Zt+1∈NΩ(Xt+1)使得

2BYt-2CXt-ρΓt+L(Xt+1-Yt)+Zt+1=0。

令

那么Wt+1∈?P(Xt+1)且

4 數值實驗

將本文提出的pDCA以及aDCA和對稱移位高階冪法(SS-HOPM)[14]以及DCA-APG進行比較,所有數值實驗運行環境為Windows 11操作系統下的MATLAB R2015b。

采用的張量生成形式如下:

其中每個xi,yj∈Rn停止準則使用|P(Xt)-P(Xt+1)|≤10-8。每個算法均實驗十次。

下表中Time表示所需時間;Fval表示十次實驗中的最小值;Ave表示平均值;Max表示最大值;global表示所得到的解的最優性,數值越小越精確。

表1 當n=100時各個算法的情況

實驗結果表明,pDCA和aDCA在計算時間和計算精度上相較于其他這兩個算法都有很明顯的優勢,而aDCA在保留pDCA優勢的基礎上使得時間得到進一步的縮減。通過表2和表3我們可以看到,隨著張量規模的增大,pDCA和aDCA的優勢也得到了很好地保持,表明該算法有處理大規模問題的能力。

表2 當n=500時各個算法的情況

表3 當n=1000時各個算法的情況

4 結束語

對于球面約束下的四次型極小化問題,本文基于近端算法,提出了pDCA和aDCA,并證明了算法具有局部收斂性并且次線性收斂。該算法具有收斂速度快,計算精確度高的特點。本研究的不足之處在于未證明出該算法達到線性收斂,這也是我們接下去的研究目標。