求解凸極小化問題的一種部分并行的可分方法

李 小 容

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

求解凸極小化問題的一種部分并行的可分方法

李 小 容

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

針對(duì)具有可分結(jié)構(gòu)的凸極小化問題，提出了一種部分并行的可分方法.該方法是在預(yù)校正近似乘子法的基礎(chǔ)之上，在極小化時(shí)采取了不同的格式，去掉了二次鄰近項(xiàng)而直接用的增廣項(xiàng)；在算法的迭代部分，預(yù)校正近似乘子法先計(jì)算xk+1，再計(jì)算zk+1，在部分并行的可分方法中，xk+1，zk+1是并行計(jì)算的；通過數(shù)值算例得到的結(jié)果顯示，該方法具有可行性.

凸優(yōu)化問題；交替方向乘子法；預(yù)校正近似乘子法；部分并行的可分方法

本文針對(duì)兩個(gè)變量的可分離凸優(yōu)化問題進(jìn)行研究[1]，形式如下：

minf(x)+g(z)

s.t.Ax+Bz=b

(1)

其中：f:Rn→(-∞,+∞]和g:Rn→(-∞,+∞]是閉凸真函數(shù)，A是m×n矩陣，B是m×s矩陣，b是m維向量.問題(1)是一種經(jīng)典的凸規(guī)劃問題，它廣泛應(yīng)用于信號(hào)與圖像處理、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)等領(lǐng)域中[2].

問題(1)的拉格朗日函數(shù)L：Rn×Rs×Rm→(-∞,+∞]定義如下：

L(x,z,λ)=f(x)+g(z)+〈λ,Ax+Bz-b〉

(2)

問題(1)的增廣拉格朗日函數(shù)Ψ：Rn×Rs×Rm→(-∞,+∞]定義如下：

Ψc(x,z,λ)=f(x)+g(z)+〈λ,Ax+Bz-b〉+

(3)

其中，〈.,.〉表示內(nèi)積，λ是約束Ax+Bz=b的相應(yīng)拉格朗日乘子，c是罰因子.

針對(duì)兩個(gè)變量的可分離凸優(yōu)化問題，很早以前就有學(xué)者進(jìn)行了研究并取得了一定的成果.1975年，R.Glowinsk[3]和D.Gabay[4]等人針對(duì)兩個(gè)變量的可分離凸優(yōu)化問題，提出了一種算法，即交替方向乘子法(ADMM).

1994年，Chen和Teboulle[5]針對(duì)兩個(gè)變量的可分離凸優(yōu)化問題，提出了一種可分方法，即預(yù)校正近似乘子法(PCPMM).這種方法不同于交替方向乘子法，它充分利用了鄰近點(diǎn)乘子法較好的結(jié)構(gòu)特征，并且在較弱的假設(shè)條件下，它收斂到原對(duì)偶問題的最優(yōu)解.

預(yù)校正近似乘子法的主要算法如下：

在ADMM算法中，沒有對(duì)變量進(jìn)行校正，對(duì)于解決兩個(gè)變量的可分離凸優(yōu)化問題，這種方法的有效性得到了證實(shí).但是當(dāng)這種算法直接延伸到n個(gè)變量的情形時(shí)，其收斂性存在一些缺陷.為了達(dá)到算法收斂的目的，對(duì)目標(biāo)函數(shù)要求太高，條件太強(qiáng)，利用預(yù)校正步驟可以避免這一問題.在PCPMM算法中，采用了預(yù)校正步驟，使得在較弱的假設(shè)條件下可以滿足算法的收斂性.

在上述算法的基礎(chǔ)之上，提出了一種部分并行的可分方法(MPCPMM).對(duì)預(yù)校正近似乘子法做了一些改進(jìn)，在極小化時(shí)采取不同的格式，去掉了二次鄰近項(xiàng)而直接用增廣項(xiàng).在算法的迭代部分，ADMM算法與PCPMM算法都是先計(jì)算xk+1，再計(jì)算zk+1.在部分并行的可分方法(MPCPMM)中，xk+1，zk+1是并行計(jì)算的.在算法的證明部分，PCPMM算法采用了鞍點(diǎn)最優(yōu)性條件，文章用到的假設(shè)條件是約束條件，其系數(shù)矩陣是滿秩的.通過數(shù)值算例得到的結(jié)果顯示，與PCPMM算法相比，該方法具有可行性.

1 部分并行的可分方法(MPCPMM)

為了方便后面進(jìn)一步敘述，考慮如下凸規(guī)劃問題(帶線性約束、目標(biāo)函數(shù)可分)，形式如下：

minf1(x1)+f2(x2)

s.tA1x1+A2x2=b

(4)

其中，fi:Rn→(-∞,+∞]是閉凸真函數(shù)，Ai是m×n矩陣，b是m維向量.為了進(jìn)一步討論，做出如下假設(shè)：(i) 假設(shè)問題的解集是非空的；(ii) 矩陣A1，A2是滿秩的.

1.1 方法介紹

步驟2 計(jì)算

(5)

(6)

步驟3 乘子更新

(7)

1.2 收斂性證明[6]

〈w-w*,Q(w*)〉≥0,?w∈W

(8)

在這里，

(9)

?fi是凸函數(shù)fi的次微分算子，它是單調(diào)的，所以式(8)(9)是可解的.用w*表示式(8)(9)的解，在假設(shè)條件下，解集w*是非空的.

≥0

這等價(jià)于

(10)

又由MPCPMM算法的式(5)(7)，有λk+1=pk+1=λk.

(11)

(12)

λk-λ*)≥

(13)

(14)

(15)

將式(14)(15)加起來，得到

(16)

(17)

同理，可以得到

λk+1-λ*)≥

(18)

λk+1-λ*)≥

(19)

由λk+1-λ*=λk-λ*+λk+1-λk及式(7)λk+1的定義，將式(19)進(jìn)行整理，得到

這就完成了證明.

很容易可以看到式(20)(21)是成立的.

(20)

(21)

將式(20)(21)與式(13)相加，可以得到

(22)

(23)

證明 式(24)—(26)顯然成立:

(24)

(25)

(26)

由此，可以得到

(27)

式(27)可由式(5)(7)(22)得到.對(duì)于任意的向量a,b和任意的正參數(shù)l>0，有

(28)

將式(28)應(yīng)用到式(27)，就可以得到最后一個(gè)不等號(hào)成立.因此，引理3得證.

證明 由式(23)，可以推斷出：

對(duì)所有的k(k=0,1,…,∞)求和，可以得到

這意味著

(29)

(30)

(31)

對(duì)子序列，將式(11)求極限，可得到

這就完成了證明.

2 數(shù)值算例

例1[7]考慮下面的問題

minx2+z2s.t.x-10=-z

這個(gè)問題的最優(yōu)解為x*=5,z*=5,λ*=-10，f(x*，z*)=50，用ADMM，PCPMM，MPCPMM算法求解結(jié)果如表1：

表1 例1的數(shù)值結(jié)果

例2[7]考慮下面的問題：

s.t.

這個(gè)問題的最優(yōu)解為x*=[0.200 0,0.000 0]T，z*=[0.000 0,0.200 0]T，λ*=[-0.080 0,-0.080 0]T，f(x*,z*)=0.08，分別用ADMM，PCPMM，MPCPMM算法求解結(jié)果如表2：

表2 例2的數(shù)值結(jié)果

由以上數(shù)值結(jié)果顯示，MPCPMM算法具有可行性.與PCPMM算法相比，雖然迭代次數(shù)和迭代時(shí)間上沒有明顯的優(yōu)勢(shì)，但是數(shù)值結(jié)果相對(duì)較好,(x*,z*)和f(x*,z*)更接近最優(yōu)值.

[1] BOYD S,PARIKH N,CHU E,et al.Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[J].Foundations and Trends in Machine Learning,2011,3(1):1-122

[2] YANG J,ZHANG Y. Alternating Direction Algorithms for L1-Problems in Compressive Sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278

[3] GLOWINSKI R,LETALLEC P.Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics[M].Philadelphia:SIAM Studies in Applied Mathematics,1989

[4] GABAY D,MERCIAR B.A Dual Algorithm for the Solution of Nonlinear Variation Problems via Finite-element Approxi-mations[J].Computers and Mathematics with Application,1975(2):17-40

[5] GONG C,MARC T.A Proximal-based Decomposition Method for Convex Minimization Problems[J].Mathem-atical Programming,1994(64):81-101

[6] HAN D,YUAN X,ZHANG W,et al.An ADM-based Splitting Method for Separable Convex Programming[J].Computational Optimization and Applications,2013,54(2):343-369

[7] 張靜.用于預(yù)校正乘子法解擬可分多學(xué)科設(shè)計(jì)優(yōu)化問題[D].重慶:重慶師范大學(xué),2012

ZHANG J.Solve the Quasi-separable MDO Problems by the MPCPMM Method[D].Chongqing:Chongqing Normal University,2012

責(zé)任編輯：李翠薇

Partially Parallel of Separable Method to Solve Convex Minimization Problem

LI Xiao-rong

(School of Mathematical Science, Chongqing Normal University, Chongqing 401331, China)

In view of convex minimization problem with separable structure, this paper presents a separable method of partially parallel, and this method is evolved by the predictor-corrector proximal multiplier method. A different format is used in the process of minimization, the quadratic adjacent items are replaced but the augmented items are directly used in the method. Numerical example results show that this method is feasible.

convex optimization problem; alternating direction multiplier method; predictor-corrector proximal multiplier method; partially parallel of separable method

2016-03-15；

2016-04-22.

國(guó)家自然科學(xué)基金(61263020).

李小容(1991-)，女，重慶巫山人，碩士，從事計(jì)算數(shù)學(xué)研究.

10.16055/j.issn.1672-058X.2017.0002.004

O224

A

1672-058X(2017)02-0016-06