求解約束最小二乘半正定規劃問題的L-BFGS方法

（上海理工大學 理學院，上海 200093）

Frobenius范數矩陣逼近問題是近年來學者們研究的熱門課題，在圖像處理、統計、金融與保險等領域有著十分廣泛的應用。多年以來許多國內外學者一直致力于研究矩陣逼近問題，并取得了豐碩的成果。Higham[1]使用一種加權Frobenius范數研究了相關系數矩陣最佳逼近問題，并提出使用修改的交替投影法來計算該問題。Malick[2]提出了一種基于拉格朗日對偶的算法來解決等式約束最小二乘問題。Boyd等[3]研究了Frobenius范數意義下的最小二乘協方差矩陣逼近問題，并通過對偶的方法來求解此問題。Gao等[4]考慮具有等式和不等式約束的最小二乘半正定規劃，通過將對偶問題轉化為帶有投影算子的半光滑方程組來解決。他們設計一個非精確的光滑牛頓法來解決產生的半光滑系統，在每次迭代中，使用BiCGStab迭代求解器來獲得光滑牛頓線性系統的近似解，數值實驗驗證了該方法的高效性。He等[5]證明了交替方向法在解決最小二乘半定規劃問題上的適用性，并檢驗了交替方向法的有效性。Li等[6]提出了一種利用投影半光滑牛頓法求解帶有等式不等式約束的最佳相關系數矩陣逼近問題，該方法在適當的假設下具有全局收斂性和二次收斂速度。Savas等[7]提出了一種新的Frobenius范數下的聚類矩陣逼近框架，該框架非常靈活，可以按各種方式進行修改以適應特定應用的需要。

本文考慮應用對偶技術研究Frobenius范數意義下的矩陣逼近問題。對偶問題是帶非負約束的凸優化問題，在Slater的條件下，對偶問題的最優解與原問題最優解相等。因此，考慮將原問題轉化為相應的對偶問題，通過求解對偶問題可以達到求解原問題的目的。為了處理大規模對偶問題，本文利用積極約束技巧估計非負約束，運用L-BFGS方法對自由變量進行加速，并證明了算法的全局收斂性。

1 算法構造

考慮Frobenius范數意義下的矩陣逼近問題

步驟5運用非單調線搜索確定步長。

在確定好搜索方向后，還需確定搜索步長。Zhang等[12]提出并分析了一種新的非單調線搜索算法，證明了非凸光滑函數的全局收斂性和強凸函數的線性收斂性。與單調或傳統的非單調方法相比，該非單調線搜索技術一般需要較少的函數和梯度計算次數。因此，本文采用文獻[12]中非單調線搜索技術確定迭代步的步長。

2 收斂性分析

3 數值結果

例1的數值實驗結果見表1，從表1可以看出，當矩陣維數固定時，增加約束個數，兩種方法迭代次數都有所增加，但算法1迭代次數增加較慢，CPU時間比ISNM算法明顯少很多。當約束條件固定時，矩陣維數增加，兩種方法迭代次數都有所增加，但算法1算法迭代次數增加較慢，而且CPU時間比ISNM算法仍然少很多。這樣的結果符合預期，因為算法1只需要儲存有限個修正對，而ISNM需要求解牛頓方程，因此，算法1在CPU時間上要比ISNM好一些。另外,ISNM算法默認設置的最大迭代次數是500，表1給出了ISNM在迭代500次時所需CPU時間，對于超過最大迭代次數的情況在表中用*進行標識。算法1成功地解決了例1的所有情況，而ISNM由于達到最大迭代次數500而未能解決例1的3個實例（標記為*），且ISNM的CPU時間已經遠超過算法1所需時間。

表1 例 1 的數值實驗結果Tab.1 Numerical test results of example 1

例2矩陣C及eii同例1中定義的一樣，指標Be={(i,i)|i=1,···,n}，指標集Bl,Bu?{(i,j)|1≤i＜j≤n}，由X的第i行隨機生成的min(nz,n-i)個元素組成。

分別測試n=1 000,1 500,2 000的情形，數值實驗結果如表2所示。從表2可以看出當矩陣維數固定時，增加約束個數，兩種方法迭代次數都有所增加，但算法1迭代次數增加較慢，CPU時間比ISNM算法明顯少很多?？赡艿脑蚴牵趍很大的情況下，ISNM需要更多的計算工作來解決廣義牛頓方程。當約束條件固定時，矩陣維數增加，兩種方法迭代次數都有所增加，但算法1算法迭代次數增加較慢，而且CPU時間比ISNM算法仍然少很多，這個結果是和表1有點相似的。但表2的迭代次數略微比表1多一些，這和測試問題有關。例1中的約束條件位置呈現帶狀，而例2約束條件位置是隨機生成的，這或許是迭代多一些的原因。

表2 例 2 的數值實驗結果Tab.2 Numerical test results of example 2

4 結 論

對于該最小二乘半正定規劃問題，提出了一種基于柯西點信息的L-BFGS算法。首先將最小二乘半正定規劃問題轉化為對偶問題，然后構造相應二次模型，再沿著負梯度方向最小化該二次模型得到柯西點，并在此基礎上，利用積極約束技巧，劃分積極約束集與非積極約束集，然后再運用L-BFGS方法對自由變量進行加速。對于步長的選取，采用非單調搜索技巧確定步長，與單調或傳統的非單調方案相比，非單調線搜索算法平均使用較少的函數和梯度計算次數。對于算法1，在一定的條件下，從理論上證明了算法的全局收斂性。最后，進行了初步的數值實驗，數值實驗表明所提算法1在處理較多約束優化問題時更為有效，與ISNM算法相比，在CPU時間上有一定的優勢。