關(guān)于無線通信中一類二次約束二次規(guī)劃問題的混合算法

孫聰

在無線通信中，許多問題可以建模為優(yōu)化問題的求解。特別地，許多問題可以轉(zhuǎn)化為一個形如式（1）的二次約束二次規(guī)劃（Quadratic Constrained Quadratic Programming，QCQP）問題，或者是一系列的QCQP子問題[1-6]。

例如：多發(fā)多收干擾信道的波束成形問題等價為一個QCQP問題[2]。在中繼輔助的點(diǎn)對點(diǎn)通信模型中，考慮優(yōu)化中繼的波束成形系數(shù)，在滿足一定信噪比的條件下極小化中繼的發(fā)送功率，該問題可建模為一個非凸的QCQP問題[2，3]。在中繼輔助下的多發(fā)多收干擾信道中，運(yùn)用帶權(quán)重的均方差極小化模型來求解總傳輸速率極大化問題，相應(yīng)的預(yù)編碼子問題也是一個QCQP[4]。高效求解這些QCQP問題是諸多通信問題的關(guān)鍵。一些經(jīng)典的方法可用于求解QCQP問題，比如：半定規(guī)劃松弛算法、逐步二次規(guī)劃算法等等。半定規(guī)劃松弛算法將二次約束二次規(guī)劃問題松弛為一個半定規(guī)劃。當(dāng)約束個數(shù)不超過3個時，可求得QCQP問題的最優(yōu)解；但當(dāng)約束多于3個時，需要用隨機(jī)的技巧產(chǎn)生QCQP問題的可行解，得到的解沒有理論保證[7]。逐步二次規(guī)劃算法在KKT點(diǎn)的局部具有超線性收斂速度；但當(dāng)初始點(diǎn)距離KKT點(diǎn)很遠(yuǎn)時，算法迭代較慢[8]。該文針對一類特殊結(jié)構(gòu)的QCQP問題，提出了可行壓縮算法，迭代得到的點(diǎn)作為逐步二次規(guī)劃算法的初始點(diǎn)，從而很快收斂到QCQP問題的KKT點(diǎn)。該文的具體結(jié)構(gòu)如下：第一節(jié)介紹要求解的一類QCQP問題的具體形式，第二節(jié)給出可行壓縮算法的流程，第三節(jié)在數(shù)值實(shí)驗(yàn)中將本文提出的算法與其他方法做出比較。

1 二次約束二次規(guī)劃

該文考慮的二次約束二次規(guī)劃問題如下所示：

這里為不定矩陣，…為半正定矩陣。當(dāng)（1）中均為半正定矩陣；≤0，對…都成立，（1）可以等價地轉(zhuǎn)化為（2），且，，，…。問題（2）是一個非凸的二次約束二次規(guī)劃問題。在通信模型中，考慮功率約束時，常常會遇到此類問題[4，5]。

2 混合算法

2.1 可行壓縮算法

注意到問題（2）的可行域是一個凸集?？尚袎嚎s算法的主要思想是：在迭代的過程中，用可行域內(nèi)部的一個橢球代替可行域本身，并在這個橢球內(nèi)求得目標(biāo)函數(shù)的極小點(diǎn)。首先，我們通過求解下面的問題得到可行壓縮算法的初始點(diǎn)。

2.2 混合算法

在可行壓縮算法中，當(dāng)?shù)c(diǎn)非?？拷尚杏虻倪吔鐣r，某個會變得非常大，從而導(dǎo)致子問題變得病態(tài)。因此當(dāng)?shù)c(diǎn)非常靠近可行域的邊界時，可行壓縮算法終止。轉(zhuǎn)而使用逐步二次規(guī)劃算法繼續(xù)迭代，直到求得問題（2）的KKT點(diǎn)。由于可行壓縮算法為逐步二次規(guī)劃算法提供了一個較好的初始點(diǎn)，逐步二次規(guī)劃算法可以在十幾步甚至幾步迭代之內(nèi)快速收斂。通過這種混合算法，可以快速求解到問題（2）的KKT點(diǎn)。這個混合算法如下所示。

算法2（混合算法）：

Step1：運(yùn)用可行壓縮算法求解問題（2），得到可行解。

Step2：以作為初始點(diǎn)，運(yùn)用逐步二次規(guī)劃算法求解問題（2），得到其KKT點(diǎn)。

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

在該節(jié)中，將該文提出的混合算法與已有的凸規(guī)劃軟件包CVX進(jìn)行比較?？紤][4]中的帶權(quán)重的均方差極小化模型（Weighted Minimum Mean Square Error，WMMSE），其中預(yù)編碼矩陣對應(yīng)的子問題的形式與該文中問題（2）一致，可用該文提出的混合算法求解。因?yàn)樵搯栴}是一個凸優(yōu)化問題，因此，也可以用凸規(guī)劃的軟件包CVX求解[9]。我們分別用混合算法和CVX求解WMMSE模型中的預(yù)編碼子問題，WMMSE模型中的其他子問題均用相同的算法求解。這里，。實(shí)驗(yàn)結(jié)果由4G內(nèi)存、64-bit的Windows操作系統(tǒng)中的Matlab R2010a完成。

圖1畫出了在不同信噪比（SNR）的情形下，兩種方法計(jì)算WMMSE問題所得到的結(jié)果，以總傳輸速率作為衡量標(biāo)準(zhǔn)。從圖1可觀察到，這兩種方法得到的結(jié)果幾乎一致。表1給出了兩種方法的計(jì)算時間。相比較CVX，該文提出的混合算法花費(fèi)的時間非常少。這是由于CVX調(diào)用了內(nèi)點(diǎn)法求解問題，而該文的混合算法比該方法的計(jì)算復(fù)雜度更低。

實(shí)驗(yàn)結(jié)果表明，該文的混合算法用非常少的時間得到了和CVX幾乎一致的結(jié)果，因此，能夠高效求解該類QCQP問題。

4 結(jié)語

該文針對一類具有凸可行域的二次約束二次規(guī)劃問題，提出了一個混合算法。首先，運(yùn)用可行壓縮算法將迭代點(diǎn)迭代至可行域的邊界附近。其次，將該點(diǎn)作為逐步二次規(guī)劃算法的初始點(diǎn)，迭代到問題的KKT點(diǎn)。數(shù)值實(shí)驗(yàn)中，該混合算法與凸規(guī)劃的軟件包CVX相比，所得結(jié)果幾乎一致，而花費(fèi)的時間則大大減少。

參考文獻(xiàn)

[1] Z.-Q.Luo，W.-K.Ma，A.M.-C.So，et al. Semidefinite Relaxation of Quadratic Optimization Problems[J].IEEE Signal Process.Magazine，2010，27（3）：20-34.

[2] N.D.Sidiropoulos，T.N.Davidson，Z.-Q. Luo.Transmit beamforming for physical-layer multicasting[J].IEEE Trans.Signal Process.，2006，54（6）：2239-2251.

[3] S.Fazeli-Dehkordy，S.Shahbazpanahi and S. Gazor，Multiple Peer-to-Peer Communications Using a network of Relays[J].IEEE Trans.Signal Process.，2009，57（8）：3053-3062.

[4] Cong Sun，Yaxiang Yuan A Fast[C]//Acoustics，Speech and Signal Processing（ICASSP），2011 IEEE Internation Conference，2011.

[5] Kien.T.Truong，Philppe J.Sartori，Robert W.Heath Jr.Cooperative Algorithms for MIMO Amplify-and-Forward Relay Networks[J].IEEE Trans.Signal Process.，2013，61（5）：1272-1287.

[6] Cong Sun，Jorswieck，E.Jorswieck，Low complexity high throughput algorithms for MIMO AF relay networks[C]//IEEE Int. Conf.of Communications （ICC），Budapest，Hungary，2013.

[7] Wenbao Ai，Yongwei Huang，Shuzhong Zhang.New results on Hermitian matrix rank-one decomposition[J].Math. Program.，2011，128（1-2）：253-283.

[8] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，2007.

[9] M. Grant and S. Boyd， CVX： Matlab software for disciplined convex programming， version 2.0 beta[EB/OL].http：//cvxr.com/cvx，Sept.，2013.

[10] 杜德道.網(wǎng)絡(luò)技術(shù)在電力信息通信中的實(shí)踐問題分析[J].科技創(chuàng)新導(dǎo)報，2015，12（30）：32-33.