可分離二次規(guī)劃問題的自適應(yīng)交替方向乘子法

唐 瑜，張守貴

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

0 引言

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

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

1 交替方向乘子法

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

(1)

其中：A∈Rr×n，B∈Rr×m是行滿秩矩陣；b∈Rr是一個(gè)給定列向量；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ù)。

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

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

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

步驟2計(jì)算xk+1∈Rn，使得對(duì)?x∈Rn有

(2)

步驟3計(jì)算yk+1∈Rm，使得對(duì)?y∈Rm有

(3)

步驟4更新拉格朗日乘子

(4)

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

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

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

(5)

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

(6)

(7)

則當(dāng)k→∞時(shí)，右端收斂于0。

引理1和引理2的證明過程參見文獻(xiàn)[1]。

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

交替方向乘子法對(duì)所有正的罰參數(shù)都收斂，通常取固定參數(shù)。然而，交替方向乘子法的收斂速度高度依賴于罰參數(shù)，而且在具體問題中很難選擇合適的罰參數(shù)。針對(duì)如何選擇合適罰參數(shù)的問題，提出一種改進(jìn)交替方向乘子法，即利用自適應(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的基本思路。對(duì)于一個(gè)給定的正常數(shù)τ，如果

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

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

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

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

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

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

步驟2計(jì)算xk+1∈Rn，使得對(duì)?x∈Rn有

(8)

步驟3計(jì)算yk+1∈Rm，使得對(duì)?y∈Rm有

(9)

步驟4更新拉格朗日乘子

(10)

步驟5選擇罰參數(shù)ρk+1

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

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

3 收斂性分析

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

記

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

定理1當(dāng)k→∞時(shí)，由改進(jìn)交替方向乘子法得到的序列{xk,yk,λk}收斂于{x*,y*,λ*}。

(11)

(12)

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

(13)

從而有

(14)

(15)

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

(16)

這表明，

(17)

由式(8)—(10)得到

(18)

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

(19)

這樣就有

由式(17)得到

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

4 算例分析

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

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

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

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

(20)

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

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

表2 2種算法的CPU運(yùn)行時(shí)間

5 結(jié)論

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