周金玲，王 潔

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.中國計量大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

四次型極小化問題是一類特殊的多項式優(yōu)化問題，是許多實際問題的數(shù)學(xué)模型。Aittomak等[1]考慮波束優(yōu)化問題并將其建模為多元四次極小化模型。Aubry等[2]通過優(yōu)化取實值的四次極小化模型來求解雷達(dá)信號問題。Mariere等[3]提出四次多項式優(yōu)化模型并將其應(yīng)用于數(shù)字通信的研究。

眾所周知，多項式優(yōu)化問題一般是非凸和高度非線性的，一般情況下是NP-難的。因此，多項式優(yōu)化問題的求解是一個研究熱點。Qi等[4]提出求解多項式全局優(yōu)化問題的Z-特征值解法，Shor[5]將一般多項式規(guī)劃簡化為二次錐規(guī)劃，Sherali等[6]提出用分支定界法求解多項式優(yōu)化問題，Nie[7]提出多項式優(yōu)化問題的一種精確Jacobi半定規(guī)劃松弛方法。本文旨在探討求解球面約束下的四次多項式極小化問題。

1 問題描述及轉(zhuǎn)化

(1)

式中，xΤx表示向量內(nèi)積。

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

(2)

定理1令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表示矩陣為半正定矩陣。

根據(jù)定理1，將問題(1)的約束條件xΤx=1轉(zhuǎn)換為對矩陣X的約束，得到如下結(jié)果。

考慮優(yōu)化問題：

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

(3)

考慮到矩陣的秩一約束是非凸約束，為了計算方便，利用矩陣的截斷奇異值分解來近似矩陣的秩。

定理2[9]令X是n階對稱矩陣，則rank(X)=1等價于如下條件：

(4)

根據(jù)定理2將問題(1)的求解轉(zhuǎn)換為如下問題的求解

(5)

2 DC算法

矩陣A是n2×n2對稱矩陣，根據(jù)矩陣的譜分解定理，存在正交矩陣Q使得A=QTΛQ，其中Λ是由矩陣A特征值構(gòu)成的對稱矩陣，Q是由矩陣A的特征向量構(gòu)成的正交矩陣。假設(shè)Λ對角元的前r個值大于等于0，其余值小于0。令

Λ-=diag{0,…,0,-λn2-r+1,…,-λn2}，Λ+=diag{λ1,λ2，…,λr,0,…,0}

B=QTΛ+Q，C=QTΛ-Q。因此，A=B-C，其中，B,C均為半正定矩陣，則問題(5)的求解與以下問題的求解是等價的：

(6)

(7)

(8)

令

集合Ω={X|X≥0,〈I,X〉=1}，Ω是凸緊集，δΩ(X)是指示函數(shù)，即當(dāng)X∈Ω時，δΩ(X)=0；X?Ω時，δΩ(X)=∞。

問題(8)等價于：

(9)

式(9)中目標(biāo)函數(shù)是2個凸函數(shù)的差，約束為凸集，因此問題(9)是DC規(guī)劃?？衫肈C算法進(jìn)行求解。

DC算法在每一次迭代的過程中利用次微分對目標(biāo)函數(shù)的凹部分進(jìn)行線性近似，從而得到一個目標(biāo)函數(shù)的凸近似[12]。記hk(X)=h(Xk)+〈X,Yk〉，其中

矩陣次微分的計算可查閱文獻(xiàn)[13-14]。對于問題(9)，DC算法在每一次迭代中求解的問題轉(zhuǎn)化為如下形式：

ming(X)-〈X,Yk〉 s.t.X∈Rn×n

(10)

DC算法的主要步驟如下：

(1)初始化，給定對稱矩陣X0，參數(shù)ε，令k=0；

(4)計算Xk+1∈argmin{〈BX,X〉+δΩ(X)-〈X,Yk〉}；

引理1[15]DC算法產(chǎn)生的序列{Xk}和{Yk}是收斂的當(dāng)且僅當(dāng)

dom?g?dom?h,dom?h*?dom?g*

(11)

定理3DC算法求解四次型極小化問題所產(chǎn)生的序列是收斂的。

證明根據(jù)引理1可知，只需證明式(10)的目標(biāo)函數(shù)滿足式(11)。

首先證明dom?g?dom?h。由式(10)可知dom?g=Ω，dom?h=Rn×n，顯然dom?g?dom?h。

對于DC算法步驟2的子問題，利用加速投影梯度法(Accelerate Proximal Gradiet，APG)進(jìn)行求解，考慮如下問題：

p(X)=〈BX,X〉-〈X,Yk〉,q(X)=δΩ(X)

(12)

根據(jù)文獻(xiàn)[16]中對APG算法的描述，對于問題(12)的具體求解方法如下：

(1)初始化，給定對稱矩陣X0，令Y1=X0，t1=1，k=1；

(5)若滿足停機(jī)準(zhǔn)則停止循環(huán)，否則，令k=k+1，執(zhí)行步驟1。

證明定理4的證明過程與文獻(xiàn)[17]的定理3類似，這里不再贅述。證畢。

3 數(shù)值實驗

將本文提出的算法和MATLAB自帶優(yōu)化工具包中的非線性優(yōu)化函數(shù)fmincon進(jìn)行比較，所有數(shù)值實驗運行環(huán)境為Windows 10操作系統(tǒng)下的MATLAB R2016a。

為充分體現(xiàn)DC算法的效果，從算法的迭代次數(shù)d、所求矩陣X的秩r和計算時間t進(jìn)行分析和比較。實驗中，ε=1.0×10-8。

a1111=0.288 3,a1112=-0.003 1,a1113=0.197 3,a1122=-0.248 5,a1223=0.186 2,

a1133=0.384 7,a1222=0.267 2,a1123=-0.293 9,a1233=0.091 9,a1333=-0.361 9,

a2222=0.124 1,a2223=-0.342 0,a2233=0.212 7,a2333=0.272 7,a3333=-0.305 4,

對于例1中給定的張量，分別用DC算法和MATLAB中非線性優(yōu)化函數(shù)fmincon計算問題(1)的最小值，實驗結(jié)果如表1所示。

表1 2種算法求解算例1的數(shù)值結(jié)果

通過表1數(shù)據(jù)結(jié)果可知，給定張量的情況下，MATLAB中的fmincon函數(shù)所用時間短且迭代次數(shù)少，DC算法所求最優(yōu)解則更加精確。

表2 2種算法求解算例2的數(shù)值結(jié)果

MATLAB中的fmincon函數(shù)是直接得到向量x，而DC算法求解過程是先求出矩陣X，再對矩陣進(jìn)行特征值分解從而得到向量x。根據(jù)問題(1)中關(guān)于x的約束以及定理1可知，當(dāng)DC算法求解出的X為秩一矩陣時，所得到的最優(yōu)解x即為全局最優(yōu)解，為了便于比較，將MATLAB求解出的x進(jìn)行轉(zhuǎn)換，通過內(nèi)積運算得到與DC算法相對應(yīng)的矩陣X，從而判斷MATLAB所求解是否為全局最優(yōu)解。

通過表2可以看出，和MATLAB自帶優(yōu)化工具包中的非線性優(yōu)化函數(shù)fmincon相比較，當(dāng)張量維數(shù)大于6時，fmincon函數(shù)所求最優(yōu)值下降緩慢，局部最優(yōu)解已經(jīng)不再是全局最優(yōu)解，DC算法對于全局解的求解效果更好，所求最優(yōu)值更加精確，最優(yōu)解為全局最優(yōu)解。因為fmincon函數(shù)對初始點的依賴程度過高，而DC算法的求解與初始點無關(guān)，DC算法從任意初始點開始迭代都可以得到收斂序列。

4 結(jié)束語

對于球面約束下的四次型極小化問題，本文刻畫了四次型極小化問題與DC規(guī)劃問題之間的關(guān)系，利用DC算法和APG算法有效解決了四次型極小化問題的求解問題。將DC算法和APG算法結(jié)合構(gòu)造了求解球面約束下的四次型極小化問題的一個有效方法。