三分塊凸優化問題的改進Peaceman-Rachford分裂法

劉學念,黃 甜

(1.湖北師范大學 數學與統計學院,湖北 黃石 43500;2.山東外事職業大學 教育學院,山東 威海 264500)

0 引言

考慮如下帶有線性約束的兩分塊可分凸優化問題的數學模型:

(1)

其中θi∶ni→∪(+∞)(i=1,2)是閉正常函數(不一定光滑),Ai∈m×ni(i=1,2),b∈m是給定的矩陣和向量,χi∈ni(i=1,2)是非空閉凸集。假設此問題的解集非空,則問題(1)的增廣拉格朗日函數為:

(2)

其中λ∈m是拉格朗日乘子,β>0是罰參數。

(3)

Gabay在文獻[6]中指出,較ADMM相比,PR分裂法的魯棒性較差,即需要在更嚴格的條件下才能收斂。但在確保收斂前提下,它的收斂速度更快。很多學者對此加以研究,He等人[7]于2014年提出對兩個乘子迭代中加入相同的松弛因子以保證其迭代序列的嚴格收縮。于2016年,He等[8]又采取不同的步長來更新拉格朗日乘數,減少了算法中的迭代次數。Gu等[9]在子問題中加入半鄰近項,提出半鄰近PR分裂法,使該方法更加靈活。Du等人[10]于2020年通過變分不等式研究證明了帶有Bregman距離的對稱ADMM的全局收斂性,該算法的迭代形式為:

(4)

本文主要考慮三分塊凸優化問題:

(5)

其中θi∶ni→∪(+∞)(i=1,2,3)是閉正常函數(不一定光滑),Ai∈m×ni(i=1,2,3),b∈m是列滿秩的矩陣和向量,Xi∈ni(i=1,2,3)是非空閉凸集。假設此問題的解集非空。提出帶有Bregman距離的PR分裂法的改進迭代形式為:

(6)

其中β>0,α和γ是松弛因子且α∈(0,1),γ∈(0,1-α),引入的Bregman距離函數為δ-強凸。本文從變分不等式的角度去研究算法(6)的全局收斂性,以及該算法在遍歷意義O(1/t)下的最壞收斂速率。

1 預備知識

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w*)≥0,?w∈Ω

(7)

根據上述定義,很容易得知映射F是單調的,也就是F滿足:

所以公式(7)可以改寫為:

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w)≥0,?w∈Ω

(8)

設定義變分不等式(7)的解集是Ω*,并且在問題(5)的解集非空的情況下Ω*非空。

為了后面的分析更加方便,在此說明幾個用到的理論。

引理1[12]設集合X∈n是一個閉凸集,θ(x)為凸函數,f(x)為可微凸函數,假設min{θ(x)+f(x)|x∈X}的解集非空,則:

x*∈arg min{θ(x)+f(x)|x∈X}

成立當且僅當

命題1[11]設ρ(x)是可微凸函數,Bρ(x,y)是Bregman距離,對任意x,y∈dom(ρ)有:

1) 一般情況下,Bρ(x,y)=Bρ(y,x)是不成立的;

2)Bρ(x,y)≥0,Bρ(x,x)=0;

3)y固定時,Bρ(x,y)關于x時凸的;

命題2[10]如果ρA,對于任意x,y∈dom(ρ),則有

引理2[14]對于可微凸函數σ,給定向量a,b,c,d,有:

命題3[10]對于可微凸函數ρ,ψ,φ,以下式子成立:

2 收斂性檢驗

(9)

并定義下列矩陣:

(10)

(11)

則能得到以下結論。

(12)

(13)

(14)

(15)

(16)

聯立(13)至(16)可得引理(3)成立。

引理4 設{wk}是由算法(6)產生的序列,則有:

(17)

接著,我們定義如下矩陣:

(18)

根據式(10)和式(11)中Q,M的定義可以得到H=QM-1.因為α∈(0,1),γ∈(0,1-α),對稱矩陣H的所有順序主子式均大于零,所以H為正定矩陣。

接著定義G=QT+Q-MTHM,其中:

在松弛因子α∈(0,1)范圍下,矩陣QT+Q為對稱正定陣。

則:

(19)

由簡單分析可得上述對稱矩陣G是不定的,所以此時算法(6)的收斂結果不能由文獻[14]中的結果來保證,需要對矩陣G進一步計算,矩陣G可改寫為:

當α∈(0,1),γ∈(0,1-α),把矩陣G分成兩部分G=G1+G2,其中

其中A2,A3是列滿秩的矩陣,則矩陣G20.再假設ψ,φ是δ-強凸的,并滿足δI+G1? 0,則有

(20)

定理1 設{wk}是由算法(6)產生的序列,由(9)定義,則:

(21)

(22)

(23)

聯立(22)(23)兩式,定理(1)得證。

證明 對(20)式按k=0,1,…,n累加可得:

(24)

將上式代入式(24)就可以得到

(25)

θ(u)-θ(u∞)+(w-w∞)TF(w∞)≥0,?w∈Ω

(26)

對于{wk}的其他任意聚點wρ,則

所以wρ=w∞,即w∞是唯一的聚點。

3 數值實驗

本節所有的測試代碼都在MATLAB-R2020a進行編寫,運行環境為惠普筆記本電腦(Intel(R) Core(TM) i5-1135G7,16.0 GB)。在數值實驗中,我們把記迭代次數記為“Ite.”,把運行時間記為“CPU(s)”。

我們針對以下模型進行數值實驗:

(27)

很明顯,上述最小化問題是問題(5)的標準表述,其中

把我們的算法應用于(27)時,產生的子問題求解如下:

上述問題可等價于

其中軟閾值shrink、算子D由下式定義

shrink(N,c)∶=sign(N)max{|N|-c,0},N∈s×n

Dc(N)∶=Udiag(shrink(∑,c))VT,N∈s×n

并且U∑VT是矩陣N的奇異值分解。

我們用所提出的改進帶有Bregman距離的PR分裂法,即算法(6)與He等人在文獻[17]中提出的分裂增廣拉格朗日算法(以下簡稱SPALM)和文獻[18]中針對多塊的廣義Peaceman-Rachford(以下簡稱GPRSM)m取3時進行比較,且終止條件為

其中fk表示問題(27)第k步目標函數的函數值。

能得到以下結果,如表1所示。

表1 算法SPALM和GPRSM的數值結果比較

從表1中可以看出,本文提出的算法在迭代步數和時間上優于 SPALM 和GPRSM.我們在圖1中繪制了目標函數值、X的秩、Y的稀疏度和誤差相對于迭代次數的演變。與帶有近端項的PRSM相比有更好的恢復效果:目標函數值較低,X秩較低,Y稀疏度較高。這些現象可能表明,在追求更好的結果質量時,本文的算法比GPRSM更為可靠。此外算法和SPALM相比,目標函數值較低,Y稀疏度偏低,X秩和誤差結果相近,但不難看出在迭代次數和時間方面,本文的算法更具有競爭力?？傮w來說,本文提出的算法效果較好,因此是有意義的。

圖1 m=1 000,n=800時目標函數值、X的低秩、Y的稀疏度和誤差與迭代步數的關系圖

4 結論

本文針對帶有線性約束的三塊可分凸優化問題,提出了帶有Bregman距離的Peaceman-Rachford分裂法的改進算法,在對稱Bregman ADMM的基礎上選擇不同的松弛因子更新拉格朗日乘子。當Bregman距離函數為δ-強凸時,從變分不等式的角度證明了該算法的全局收斂性和在遍歷情形下O(1/t)的最壞收斂速率。最后用數值實驗初步驗證了本文所提的算法在迭代步數和迭代時間上具有一定的優勢。

5 致謝

感謝編輯和審稿人提供的意見以提高論文的質量,特別感謝湖北師范大學數學與統計學院的王陽老師在后期工作中提供的幫助。