求解非凸優化問題的近似交替方向乘子法①

譚秋芬， 羅洪林

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

本文考慮以下線性約束優化問題

minf(x)+g(y)

s． t．Ax+By=b，x∈P

(1)

P={x∈Rn1|li≤xi≤ui，i=1，2，…，n1}

當問題(1)的目標函數是凸可分時， 交替方向乘子法(ADMM)是解決這類問題較為有效的方法[5-8]． 若目標函數非凸， 則通過一些假設條件， ADMM仍然可以保持較好的適用性[9-14]． 其中， 文獻[10-11]針對非凸問題提出了Bregman ADMM并證明了其收斂性， 該算法在分別求解子問題時， 在原本的增廣拉格朗日函數上增加了一個Bregman距離函數， 通過將非凸子問題進行一個凸化處理來簡化原來的子問題， 進而對其進行求解． 文獻[13]提出了非凸Proximal ADMM， 該算法在子問題中引入了近端項， 將子問題進行凸化處理， 進而使用ADMM進行求解， 而文獻[15]在處理非凸問題上考慮的是近似二次項， 近似二次項在保證問題凸化的同時還能使得迭代點不會偏離穩定點太多， 這為凸化處理提供了更好的方向．

當考慮問題(1)中的有界約束時， 使用ADMM直接解決是比較困難的． 幸運的是， 文獻[15]在處理有界多面體上的非凸優化問題時引入了梯度投影算法， 對含有有界約束的單塊優化問題進行了求解并取得了較好的結果． 受以上文獻啟發， 在借鑒梯度投影和交替方向乘子法(ADMM)兩種經典方法思想的基礎上， 本文針對具有可分結構的非凸優化問題提出了一種新的近似交替方向乘子法(P-ADMM)， 基于ADMM的框架在解決有界多面體上的非凸子問題時， 采用梯度投影， 以此簡化非凸子問題的求解， 降低運算成本， 并且通過引入一個“平滑的”(即指數加權)原始迭代序列， 并在每次迭代時， 向增廣拉格朗日函數中增加一個以平滑的原始迭代為中心的近似二次項， 使所得到的近似增廣拉格朗日函數在每次迭代時被不精確地最小化， 在保證算法的收斂性的同時也能夠提升算法的收斂速度． 該算法可有效應用于求解一類非凸的船舶分布式能源管理問題．

1 預備知識

1.1 論文的符號定義

1) Rn1為n1維歐氏空間， Rn2為n2維歐氏空間．

2) Rm×n1是m×n1維實矩陣空間， Rm×n2是m×n2維實矩陣空間．

1.2 穩定解集合

原問題(1)的KKT條件如下

?f(x*)+ATλ*-μ*+ν*=0

?g(y*)+BTλ*=0

Ax*+By*=b

μ*0，ν*0

1.3 基本假設

(I)BBTμ0I， 其中μ0>0， 即B是列滿秩的．

(II)f(x)是可微的， 且滿足Lipschitz可微條件

‖?f(x1)-?f(x2)‖≤L1‖x1-x2‖，L1>0， ?x1，x2∈P

則可得， 存在γ<0， 使得

〈?f(x1)-?f(x2)，x1-x2〉≥γ‖x1-x2‖2

(III)g(y)是強凸的， 強凸系數為m， 即

(IV)g(y)是可微的， 且滿足Lipschitz可微條件

‖?g(y1)-?g(y2)‖≤L2‖y1-y2‖，L2>0， ?y1，y2∈Rn2

(VI) 函數g(y)是強制的， 即

1.4 一種近似的ADMM

接下來介紹近似的交替方向乘子法(P-ADMM)， 問題(1)的增廣拉格朗日函數為

其中常數α>0． 經典的ADMM算法處理以下兩個子問題： 對于固定的y，λ， 在有界約束P上極小化L(x，y，λ)； 對于固定的x，λ， 極小化L(x，y，λ)． 最后， 利用原始殘差Ax+By=b更新乘子λ． 由于有界約束的特殊性， 在求解有界非凸子問題上采用梯度投影， 且考慮到f(x)是非凸的， 通過引入一個指數平均(或平滑)方案來生成一個額外的序列{zt}， 并在增廣的拉格朗日函數中插入一個額外的以zt為中心的二次近似項， 在保證非凸子問題凸化的同時也能夠使得原始迭代點xt不會偏離穩定迭代點太多．

表1 近似交替方向乘子法

注1該算法與傳統的ADMM相比的優勢在于， 傳統的ADMM處理有界約束上的非凸子問題是十分困難的， 一方面是子問題的非凸性， 另一方面則是有界約束的限制， 而采用梯度投影、 引入近似二次項則可以簡化子問題的求解， 很好地處理了非凸性和有界約束， 使得算法更加簡便， 降低了運算成本．

注2與文獻[15]算法相比， P-ADMM是投影算法和ADMM的結合， 主要用于解決有界約束上的可分離的非凸優化問題， 而文獻[15]中的算法主要用于解決有界約束上的單塊非凸優化模型， 是本文模型的一種特殊情況， 因此P-ADMM的應用性更加廣泛．

注3與文獻[16]中算法APGMM相比， P-ADMM在解決有界約束上的非凸子問題時不是直接采用的梯度投影， 而是在原本的增廣拉格朗日函數上引入了近似二次項， 近似二次項的引入在保證非凸子問題凸化的同時也加快了算法收斂的速度(見數值實驗)．

2 收斂性分析

為了更加方便分析P-ADMM的收斂性， 首先給出一些關鍵的引理．

引理1若假設(I)，(IV)成立， 那么可得

證首先， 通過假設(I)可得

(2)

利用算法關于y在t+1步迭代式的一階最優性條件可得

?g(yt+1)+〈B，λt〉+α〈B，Axt+1+Byt+1-b〉=0

再通過算法關于λ在t+1步的迭代式可得?g(yt+1)=-〈B，λt+1〉， 同理可得

?g(yt)=-〈B，λt〉

通過假設(IV)可知， 函數g(x)是梯度Lipschitz連續的， 則

‖?g(yt+1)-?g(yt)‖=‖BT(λt+1-λt)‖≤L2‖yt+1-yt‖

(3)

引理2若假設(II)成立， 且p+γ>0， 令函數

則下列結論成立：

1) 函數K(x，y，z，λ)關于x是強凸的， 且強凸系數為γk=p+γ， 即

〈?Kx(x1，y，z，λ)-?Kx(x2，y，z，λ)，x1-x2〉≥(p+γ)‖x1-x2‖2

其中σ1為矩陣A的最大奇異值．

證對函數K(x，y，z，λ)關于x求梯度， 則

?Kx(x，y，z，λ)=?f(x)+ATλ+αAT(Ax+By-b)+p(x-z)

由假設(Ⅱ)知

同理可得

則引理2成立．

接下來， 構造輔助函數

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

證由算法關于x在t+1步的迭代式及投影定理， 可得

〈xt-c?xK(xt，yt，zt，λt)-xt+1，xt-xt+1〉≤0

則有

(4)

通過引理2的結論1)， 利用函數K(x，y，z，λ)關于x的凸性， 有

K(xt，yt，zt，λt)-K(xt+1，yt，zt，λt)≥〈?xK(xt+1，yt，zt，λt)，xt-xt+1〉

(5)

(6)

通過算法關于z在t+1步的迭代式得到

(7)

由假設(III)可知

(8)

利用算法關于y在t+1步迭代式的一階最優性條件得

?g(yt+1)+〈B，λt〉+α〈B，Axt+1+Byt+1-b〉=0

再利用算法關于λ在t+2步的迭代式可得

?g(yt+1)=-〈B，λt+1〉

(9)

結合(8)，(9)式可得

(10)

最后， 通過算法關于λ在t+1步的迭代式可得

M(xt+1，yt+1，yt，zt+1，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)=

再由引理1可得

(11)

將(6)，(7)，(10)，(11)式相加， 則有

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

故引理3成立．

證首先， 通過完全平方可得

(12)

再利用假設(I)和(IV)， 可得

因此

(13)

將(13)式代入(12)式可得

(14)

(15)

(16)

下面的引理說明， 若算法停止， 則可以找到一對原始對偶解．

引理5若

μ0，v0

進一步簡化得到

μ0，v0

我們可得

成立時， 即

則有

(17)

進而可以得到

則有

則有

(18)

通過(17)式可得

則有

這與(18)式矛盾， 則推論1成立．

定理1若假設(I)，(III)和(IV)成立， 序列{ωt}為P-ADMM所產生， 則下列結論成立

證1)由引理3可知

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

進而可得到

通過定理1可知

則可得

結論1)成立．

2) 由于

結合z的第t+1次迭代式zt+1=zt+β(xt+1-zt)可得

則結論2)成立．

3) 由1)， 2)兩個結論可得

結合推論1有

則結論3)成立．

3 數值實驗

本文考慮用P-ADMM解決一類非凸的船舶分布式能源管理問題， 在文獻[17]中， 考慮具有多個代理的船舶動力系統， 且各代理根據各自的需求、 供給相互協調． 首先將船舶能量管理問題以多智能體系統的形式重新制定， 然后利用交替方向乘子法(ADMM)尋找模型中滿足共識要求的最經濟的工作點， 本文考慮如下可分非凸光滑的能量成本函數

s． t．x∈M

(19)

其中

M： ={x∈RD|-5.12≤xi≤5.12，i=1，2，…，D}

F(x)為能量成本函數，xi為共識變量，D為該問題的維度， 問題(19)可等價轉化成如下問題

s． t．x=y，x∈M

(20)

問題(20)所對應的增廣拉格朗日函數為

利用P-ADMM求解問題(20)．

rError=max{‖xt-xt+1‖， ‖yt-yt+1‖， ‖λt-λt+1‖}≤10-8

圖1展示了在P-ADMM算法下船舶電力系統能量成本的走勢情況， 其中G(xt)+H(yt)為成本函數，t為迭代步． 通過圖1可以看出， 能量成本值從開始的下降逐漸趨于穩定， 最后達到收斂． 同時， 觀察發現選擇較大的β， 會使收斂速度加快， 即算法可以在更小的迭代步數下完成收斂， 減少了算法迭代的次數．

圖1 成本函數

圖2和圖3分別展示了在參數β=0.2的條件下‖xt-yt‖和‖xt+1-zt‖的下降情況， 進一步驗證了算法P-ADMM解決問題(20)的可行性． 從圖2，3中可知， ‖xt-yt‖和‖xt+1-zt‖一開始下降得非?？?， 再逐漸趨于平穩并達到收斂．

圖2 ‖xt-yt‖

圖3 ‖xt+1-zt‖

圖4是基于問題(20)將P-ADMM和APGMM[17]在參數β=0.8的條件下進行了比較． 從圖4中可以看到算法P-ADMM相對于算法APGMM在下降趨勢和收斂步數上都具有較大的優勢． APGMM算法開始迭代是波動的、 不穩定的． 考慮到目標函數的非凸性， 我們在運行算法時， 選取α=100， α=1 000兩種情況進行比較． 由圖4可知算法P-ADMM的下降速度快， 能夠在更小的迭代步達到收斂．

圖4 基于問題(20)的算法對比實驗

4 結論

本文在梯度投影算法和ADMM基礎上， 針對可分結構的非凸優化問題， 提出了一種新的P-ADMM， 該算法具有良好的收斂性， 簡化了子問題的求解， 降低了運算成本， 且近似二次項的引入在保證算法的收斂性的同時也能夠提升算法的收斂速度． 該算法在一類非凸的船舶能源管理問題中也得到了有效應用． P-ADMM在梯度投影時， 選取的步長是滿足條件的定值， 但如何優化梯度投影的步長以提高算法速率需要進一步的研究．