可分離二次規劃問題的自適應交替方向乘子法

唐 瑜，張守貴

(重慶師范大學 數學科學學院， 重慶 401331)

0 引言

交替方向乘子法是求解可分離凸優化問題的一種經典方法。該算法利用目標函數的可分離性，將原問題分解成多個極小化子問題，然后通過迭代交替求解[1-3]。交替方向乘子法有很好的理論基礎，其收斂性和計算復雜性已得到深入研究，且應用廣泛[4-5]。理論和實際應用證明，拉格朗日乘子法是求解最優化問題的一種有效方法[6-7]。該算法的主要優點在于每次迭代均把所求解的問題分解為2個子問題，迭代矩陣始終保持不變[8-9]。另外，算法對罰參數具有全局收斂性。然而，該方法的罰參數取值對收斂速度影響很大，罰參數太小或太大都將極大地減緩收斂速度，因此在實際應用中面臨如何優化選擇罰參數的問題[10-11]。

針對交替方向乘子法求解具有等式約束的可分離二次規劃問題，對罰參數的選擇給出了具體可行的自適應方法[12]。引入1個罰參數和增廣拉格朗日乘子法表示的極小值問題，再用交替方向乘子法求解，得到1個簡單的兩步迭代方法。該方法的每次迭代均是先求解2個簡單的極小值問題，在此基礎上更新拉格朗日乘子。為了克服罰參數對收斂速度的影響，給出基于平衡原理選擇合適罰參數的自適應法則，該法則已成功應用于投影算法和Uzawa塊松弛算法[13-15]。在上述交替方向乘子法的基礎上，進一步得到類似的法則，自動選取使算法收斂較快的可變罰參數，從而顯著提高算法性能。最后，通過數值算例驗證算法的可行性和有效性。

1 交替方向乘子法

考慮具有等式約束的可分離二次規劃問題：

(1)

其中：A∈Rr×n，B∈Rr×m是行滿秩矩陣；b∈Rr是一個給定列向量；f(x)、g(y)均為二次函數；X?Rn、Y?Rm為非空閉凸集。顯然，問題(1)存在唯一最優解(x*,y*)。

引入問題(1)的增廣拉格朗日函數：

lρ(x,y,λ)=f(x)+g(y)+

λT(Ax+By-b)+

其中：λ∈Rr是拉格朗日乘子；ρ>0是給定的罰參數。

采用交替方向乘子法求解，將原問題進行等價變形和分解，并交替求解，使每個極小化問題以更簡單的形式有效解決，具體算法過程見算法1[1]。

算法1交替方向乘子法(ADMM)

步驟1給定初始值{y0,λ0}∈Rm×Rr，ρ>0，令k=0。

步驟2計算xk+1∈Rn，使得對?x∈Rn有

(2)

步驟3計算yk+1∈Rm，使得對?y∈Rm有

(3)

步驟4更新拉格朗日乘子

(4)

步驟5對給定的誤差限ε>0，若滿足

則停止迭代，得到數值解(xk+1,yk+1)；否則，令k=k+1，返回步驟2。

對于上述交替方向乘子法，在文獻[1]中已得到一些重要結果。最優解(x*,y*)和拉格朗日乘子λ*滿足

(5)

引理1 由交替方向乘子法得到的序列{xk,yk,λk}滿足

(6)

(7)

則當k→∞時，右端收斂于0。

引理1和引理2的證明過程參見文獻[1]。

2 自適應交替方向乘子法

交替方向乘子法對所有正的罰參數都收斂，通常取固定參數。然而，交替方向乘子法的收斂速度高度依賴于罰參數，而且在具體問題中很難選擇合適的罰參數。針對如何選擇合適罰參數的問題，提出一種改進交替方向乘子法，即利用自適應法則和迭代結果近似選取合適罰參數來代替固定參數[12-15]。

在引理1中，用ρk代替ρ，則由交替方向乘子法生成的序列{xk,yk,λk}滿足不等式：

||λk-λ*||≈ρk||B(yk-y*)||

分別用λk+1和yk+1替代λ*和y*，可得

||λk-λk+1||≈ρk||B(yk-yk+1)||

于是得到選擇罰參數ρk+1的基本思路。對于一個給定的正常數τ，如果

ρk||B(yk-yk+1)||>(1+τ)||λk-λk+1||

則在下一次迭代中減小ρk；如果

則在下一次迭代中增大ρk。

綜上，改進交替方向乘子法即自適應交替方向乘子法算法過程見算法2。

算法2自適應交替方向乘子法(SADMM)

步驟1給定初始值{y0,λ0}∈Rm×Rr，ρ>0，ρk=ρ>0，令k=0。

步驟2計算xk+1∈Rn，使得對?x∈Rn有

(8)

步驟3計算yk+1∈Rm，使得對?y∈Rm有

(9)

步驟4更新拉格朗日乘子

(10)

步驟5選擇罰參數ρk+1

步驟6對給定的誤差限ε>0，若滿足

則停止迭代得到數值解(xk+1,yk+1)；否則，令k=k+1，返回步驟2。

3 收斂性分析

為了證明自適應交替方向乘子法的收斂性，在此先給出引理3。

記

得到有關收斂性結果的定理1。

定理1當k→∞時，由改進交替方向乘子法得到的序列{xk,yk,λk}收斂于{x*,y*,λ*}。

(11)

(12)

因此，由式(11)和式(12)得

(13)

從而有

(14)

(15)

對不等式(13)兩端求和，結合式(15)得到

(16)

這表明，

(17)

由式(8)—(10)得到

(18)

把式(18)的最后1個式子代入其余2個等式得到

(19)

這樣就有

由式(17)得到

當k→∞時，序列{xk,yk,λk}的極限滿足問題的最優化條件(5)，從而收斂于{x*,y*,λ*}。

4 算例分析

利用自適應交替方向乘子法求解可分離二次規劃問題。迭代過程中，利用迭代數據自動調整罰參數，用變參數ρk代替固定參數ρ，從而達到提高算法效率的目的[12-15]。對于交替方向乘子法(算法1)，取固定罰參數ρ；對于自適應交替方向乘子法(算法2)，序列{sk}按照如下方式得到：

其中：cmax是一個正常數；ck表示ρk改變的次數，即

顯然，序列{sk}滿足引理3的條件。在數值算例中，取τ=2，cmax=100。

考慮求解等式約束的二次規劃問題：

(20)

對于不同的初始罰參數取值ρ，表1分別對n=10 000，20 000，40 000時的交替方向乘子法和自適應交替方向乘子法所需迭代次數進行了比較，表中“—”表示迭代次數超過500次。表2分別給出了迭代所需的CPU運行時間，時間單位為s。表1和表2的結果表明，自適應交替方向乘子法不僅使迭代次數有效減少，收斂速度更快，而且非常穩定。自適應交替方向乘子法的收斂速度和CPU運行時間幾乎不受初始參數ρ的影響。

表1 2種算法的迭代次數

表2 2種算法的CPU運行時間

5 結論

在求解具有等式約束二次規劃問題的交替方向乘子法的基礎上，提出了自適應罰參數算法。交替方向乘子法的主要優點是迭代計算簡單，對所有罰參數都具有全局收斂性。然而，交替方向乘子法的收斂速度高度依賴罰參數的取值，而且事先很難選擇合適的罰參數。為了提高算法的性能，提出了采用可變罰參數的自適應交替方向乘子法。該方法在迭代過程中利用迭代數據自動調整罰參數，加快收斂速度。數值算例表明了新算法具有優越性。