唐 瑜，張守貴

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

0 引言

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

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

1 交替方向乘子法

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

(1)

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

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

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

λT(Ax+By-b)+

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

采用交替方向乘子法求解，將原問題進行等價變形和分解，并交替求解，使每個極小化問題以更簡單的形式有效解決，具體算法過程見算法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，若滿足

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

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

(5)

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

(6)

(7)

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

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

2 自適應(yīng)交替方向乘子法

交替方向乘子法對所有正的罰參數(shù)都收斂，通常取固定參數(shù)。然而，交替方向乘子法的收斂速度高度依賴于罰參數(shù)，而且在具體問題中很難選擇合適的罰參數(shù)。針對如何選擇合適罰參數(shù)的問題，提出一種改進交替方向乘子法，即利用自適應(yīng)法則和迭代結(jié)果近似選取合適罰參數(shù)來代替固定參數(shù)[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)||

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

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

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

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

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

算法2自適應(yīng)交替方向乘子法(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選擇罰參數(shù)ρk+1

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

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

3 收斂性分析

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

記

得到有關(guān)收斂性結(jié)果的定理1。

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

(11)

(12)

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

(13)

從而有

(14)

(15)

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

(16)

這表明，

(17)

由式(8)—(10)得到

(18)

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

(19)

這樣就有

由式(17)得到

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

4 算例分析

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

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

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

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

(20)

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

表1 2種算法的迭代次數(shù)

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

5 結(jié)論

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