蔣 峰， 黨亞崢

（上海理工大學(xué) 管理學(xué)院 上海 20093）

1 問題的提出

考慮下面的凸優(yōu)化問題：

因?yàn)榻?jīng)典的ADMM算法難以求得子問題的精確解，為了彌補(bǔ)這一缺陷，何炳生等[4]在x子問題中加入了項(xiàng)，得到了下面的新算法：

式中，G是一個半正定矩陣。何炳生等[4]證明了該算法的收斂速率。

從問題（1）本身來看，變量x和z是平等的，在設(shè)計算法時也希望能夠平等對待x和z子問題。因此何炳生等[5]提出了對稱ADMM算法，其迭代格式如下：

與原來的ADMM算法不同，式（4）在每一次迭代中更新拉格朗日乘子兩次。文獻(xiàn)[4]中分析了該算法的全局收斂性，數(shù)值計算表明該算法比原始的ADMM算法收斂速度更快。

然而，在很多實(shí)際應(yīng)用中，精確地求解式（4）中的x子問題難以實(shí)現(xiàn)，或者要付出很大代價。因此本文提出了一種改進(jìn)的對稱ADMM算法。該算法的主要創(chuàng)新之處是在對稱ADMM算法的x極小化子問題中加入半近鄰項(xiàng)近似求解此問題，同時給出了收斂性證明。數(shù)值計算表明，改進(jìn)的對稱ADMM算法的收斂速度比對稱ADMM算法更快。

2 算 法

問題（1）等價于一個變分不等式VI（），求

步驟1給定半正定矩陣G，初始點(diǎn)

步驟2計算

特別地，當(dāng)G = 0時，算法為對稱ADMM算法。

3 收斂性分析

首先，定義幾個分析算法收斂性質(zhì)需要用到的矩陣。

因?yàn)镚是半正定矩陣，所以等號右側(cè)的第一部分是半正定矩陣，只需證明第二部分也是半正定即可。令

是半正定矩陣，故引理1成立。

引理2 假設(shè)H，M，Q是式（6）定義的矩陣，則有

因?yàn)?/p>

同理，根據(jù)z極小化問題的最優(yōu)性條件，可得

證明 對于同一空間中的向量a，b，c，d和具有適當(dāng)維度的矩陣H，滿足

上式可寫為

證明 根據(jù)式（14）和式（22）得

4 數(shù)值計算

將改進(jìn)的對稱ADMM算法應(yīng)用于LASSO問題[6-9]

表1為應(yīng)用對稱ADMM算法和改進(jìn)的對稱ADMM算法解決該問題的結(jié)果，其中m表示矩陣P的維數(shù)，k表示迭代次數(shù)。從表1可以看出，當(dāng)矩陣P的維數(shù)較低時，改進(jìn)的對稱ADMM算法明顯快于對稱ADMM算法；而當(dāng)P的維數(shù)較高時，對比CPU時間發(fā)現(xiàn)，改進(jìn)的對稱ADMM算法的數(shù)值表現(xiàn)優(yōu)勢更大。

為了進(jìn)一步觀察兩種算法的收斂性，比較了初始?xì)埐詈蛯ε細(xì)埐铍S迭代次數(shù)的變化情況。從圖1和圖2可以直觀地發(fā)現(xiàn)，盡管在算法迭代的某些階段，對稱ADMM算法的初始?xì)埐?、對偶?xì)埐顪p小得更快，但是本文提出的算法先于對稱ADMM算法達(dá)到收斂條件，因此改進(jìn)的對稱ADMM算法更高效。

表 1 LASSO問題數(shù)值結(jié)果Tab.1 Numerical results for LASSO

圖1 初始?xì)埐畹淖兓闆rFig. 1 Evolution of primal residual

圖2 對偶?xì)埐畹淖兓闆rFig. 2 Evolution of dual residual

5 結(jié) 論

提出了一種求解目標(biāo)函數(shù)具有可分離結(jié)構(gòu)的凸優(yōu)化問題的改進(jìn)的對稱ADMM算法，并證明了其收斂性。該方法的基本思想是在x子問題中引入一個半近鄰項(xiàng)，從而達(dá)到加快其收斂速度的目的。數(shù)值實(shí)驗(yàn)表明，該算法在求解高維的LASSO問題時相對于對稱ADMM算法具有明顯的優(yōu)勢，但是如何選擇最優(yōu)的還需要進(jìn)一步研究。