譚秋芬， 羅洪林

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

本文考慮以下線性約束優(yōu)化問題

minf(x)+g(y)

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

(1)

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

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

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

1 預(yù)備知識(shí)

1.1 論文的符號(hào)定義

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

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

1.2 穩(wěn)定解集合

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

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

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

Ax*+By*=b

μ*0，ν*0

1.3 基本假設(shè)

(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)是強(qiáng)凸的， 強(qiáng)凸系數(shù)為m， 即

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

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

(VI) 函數(shù)g(y)是強(qiáng)制的， 即

1.4 一種近似的ADMM

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

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

表1 近似交替方向乘子法

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

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

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

2 收斂性分析

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

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

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

(2)

利用算法關(guān)于y在t+1步迭代式的一階最優(yōu)性條件可得

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

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

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

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

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

(3)

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

則下列結(jié)論成立：

1) 函數(shù)K(x，y，z，λ)關(guān)于x是強(qiáng)凸的， 且強(qiáng)凸系數(shù)為γk=p+γ， 即

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

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

證對(duì)函數(shù)K(x，y，z，λ)關(guān)于x求梯度， 則

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

由假設(shè)(Ⅱ)知

同理可得

則引理2成立．

接下來， 構(gòu)造輔助函數(shù)

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

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

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

則有

(4)

通過引理2的結(jié)論1)， 利用函數(shù)K(x，y，z，λ)關(guān)于x的凸性， 有

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

(5)

(6)

通過算法關(guān)于z在t+1步的迭代式得到

(7)

由假設(shè)(III)可知

(8)

利用算法關(guān)于y在t+1步迭代式的一階最優(yōu)性條件得

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

再利用算法關(guān)于λ在t+2步的迭代式可得

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

(9)

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

(10)

最后， 通過算法關(guān)于λ在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)

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

因此

(13)

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

(14)

(15)

(16)

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

引理5若

μ0，v0

進(jìn)一步簡(jiǎn)化得到

μ0，v0

我們可得

成立時(shí)， 即

則有

(17)

進(jìn)而可以得到

則有

則有

(18)

通過(17)式可得

則有

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

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

證1)由引理3可知

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

進(jìn)而可得到

通過定理1可知

則可得

結(jié)論1)成立．

2) 由于

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

則結(jié)論2)成立．

3) 由1)， 2)兩個(gè)結(jié)論可得

結(jié)合推論1有

則結(jié)論3)成立．

3 數(shù)值實(shí)驗(yàn)

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

s． t．x∈M

(19)

其中

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

F(x)為能量成本函數(shù)，xi為共識(shí)變量，D為該問題的維度， 問題(19)可等價(jià)轉(zhuǎn)化成如下問題

s． t．x=y，x∈M

(20)

問題(20)所對(duì)應(yīng)的增廣拉格朗日函數(shù)為

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

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

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

圖1 成本函數(shù)

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

圖2 ‖xt-yt‖

圖3 ‖xt+1-zt‖

圖4是基于問題(20)將P-ADMM和APGMM[17]在參數(shù)β=0.8的條件下進(jìn)行了比較． 從圖4中可以看到算法P-ADMM相對(duì)于算法APGMM在下降趨勢(shì)和收斂步數(shù)上都具有較大的優(yōu)勢(shì)． APGMM算法開始迭代是波動(dòng)的、 不穩(wěn)定的． 考慮到目標(biāo)函數(shù)的非凸性， 我們?cè)谶\(yùn)行算法時(shí)， 選取α=100， α=1 000兩種情況進(jìn)行比較． 由圖4可知算法P-ADMM的下降速度快， 能夠在更小的迭代步達(dá)到收斂．

圖4 基于問題(20)的算法對(duì)比實(shí)驗(yàn)

4 結(jié)論

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