關于無線通信中一類二次約束二次規劃問題的混合算法

孫聰

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

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

1 二次約束二次規劃

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

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

2 混合算法

2.1 可行壓縮算法

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

2.2 混合算法

在可行壓縮算法中，當迭代點非?？拷尚杏虻倪吔鐣r，某個會變得非常大，從而導致子問題變得病態。因此當迭代點非?？拷尚杏虻倪吔鐣r，可行壓縮算法終止。轉而使用逐步二次規劃算法繼續迭代，直到求得問題（2）的KKT點。由于可行壓縮算法為逐步二次規劃算法提供了一個較好的初始點，逐步二次規劃算法可以在十幾步甚至幾步迭代之內快速收斂。通過這種混合算法，可以快速求解到問題（2）的KKT點。這個混合算法如下所示。

算法2（混合算法）：

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

Step2：以作為初始點，運用逐步二次規劃算法求解問題（2），得到其KKT點。

3 數值實驗

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

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

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

4 結語

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

參考文獻

[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] 袁亞湘，孫文瑜.最優化理論與方法[M].北京：科學出版社，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] 杜德道.網絡技術在電力信息通信中的實踐問題分析[J].科技創新導報，2015，12（30）：32-33.