目標(biāo)函數(shù)帶線性約束塊可分的凸優(yōu)化方法

曾 琴

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

目標(biāo)函數(shù)帶線性約束塊可分的凸優(yōu)化方法

曾 琴

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

帶有線性約束條件且目標(biāo)函數(shù)是塊可分的凸性最小問(wèn)題一直是研究的重點(diǎn)。該問(wèn)題是經(jīng)過(guò)研究目標(biāo)函數(shù)由2個(gè)不是充分光滑的凸函數(shù)組成或是由3個(gè)不是充分光滑的凸函數(shù)組成，從而推廣到目標(biāo)函數(shù)由n個(gè)不是充分光滑的凸函數(shù)組成的情況。問(wèn)題的解決是以經(jīng)典的交替方向法為基礎(chǔ)，延伸出多種方法來(lái)建立該模型?？偨Y(jié)了幾種常見(jiàn)方法,同時(shí)提出了新方法——基于分離法的新ADMM法，并證明該方法的可行性。

塊可分；凸優(yōu)化；線性約束條件；新ADMM法

本文研究的僅僅是一種帶有線性約束條件且目標(biāo)函數(shù)是塊可分的凸性最小問(wèn)題。該模型表明：在凸性假設(shè)和約束品性為線性條件的情況下，序列的每一個(gè)聚點(diǎn)才是它的最優(yōu)解。本文主要總結(jié)常見(jiàn)的、較成熟的幾種方法，并在此基礎(chǔ)上提出新方法。文獻(xiàn)[1]采用增廣拉格朗日法，簡(jiǎn)稱ALM，該方法具有不可分離的缺點(diǎn)，但其收斂速度和數(shù)值優(yōu)勢(shì)卻提供了強(qiáng)有力的分離項(xiàng)，因此根據(jù)該優(yōu)勢(shì)可通過(guò)增加1個(gè)二次項(xiàng)，利用交替的線性技術(shù)來(lái)進(jìn)行改進(jìn)。另外，還可采用交替方向乘子法(ADMM)，但在該方法的迭代過(guò)程中為解決產(chǎn)生的子問(wèn)題可能存在一些困難，故可針對(duì)此改進(jìn)該方法。與交替方向乘子法(ADMM)類似的便是交替方向法(ADM)，它是由Peaceman和Mercier首次提出，由Glowinski和Marrocco進(jìn)行發(fā)展。文獻(xiàn)[2]采用線性近端的ADM法，其主要貢獻(xiàn)在于簡(jiǎn)化子問(wèn)題。目前有3種版本：第1種和第2種都是分別進(jìn)行線性化二次項(xiàng)，增加鄰近項(xiàng)；第3種版本是第1、2兩種版本的結(jié)合，同時(shí)進(jìn)行線性化二次項(xiàng)，增加鄰近項(xiàng)。本文還介紹了高斯向后替換的線性ADM法。值得說(shuō)明的是：盡管ADME法的數(shù)值性很好，但其收斂性還有待證明。其他方法如：ADBC法、ADM-based splitting method與ADME法類似，都要用校正步驟，而HTY法雖然無(wú)需校正步驟，但它需要一個(gè)更新的乘子λ。除了這些方法，還有加速分離的增廣拉格朗日法(ADAL)、對(duì)偶法(dual methods)、對(duì)角二次逼近法(DQA)、交替步法(ASM)等。

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

1.1 方法回顧

讓Xi?Rni,i∈φ={1,2,…,N} 分別是ni維歐式空間中的非空閉凸子集，而θi:Rni→R,i∈φ是凸函數(shù)，是m×ni的矩陣，其中i=1,2,…,N.。本文所考慮的模型可用下式表示：

(1)

通過(guò)閱讀大量的文獻(xiàn)以及對(duì)資料的查找，對(duì)于式(1)這種帶有線性約束條件、目標(biāo)函數(shù)又是塊可分的凸性最小問(wèn)題，常見(jiàn)處理方法如下：解決這種模型的本質(zhì)就是把帶有約束條件的優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束條件的優(yōu)化問(wèn)題，這樣相當(dāng)于解一個(gè)無(wú)約束條件的優(yōu)化問(wèn)題。解無(wú)約束條件優(yōu)化問(wèn)題的方法很多，如一致收縮法、對(duì)分法、黃金分割法、斐波拉切法、牛頓法等，這樣問(wèn)題(1)就得以解決。因此，現(xiàn)在問(wèn)題是：怎樣把帶有約束條件的優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束條件的優(yōu)化問(wèn)題？怎樣解帶有線性約束條件、目標(biāo)函數(shù)又是塊可分的凸性最小問(wèn)題？

1.1.1 增廣拉格朗日方法(ALM)

經(jīng)典的增廣拉格朗日方法(ALM)是通過(guò)引入1個(gè)拉格朗日乘子λ和1個(gè)罰參數(shù)β,將有約束條件的優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束條件的優(yōu)化問(wèn)題，即將原問(wèn)題從數(shù)學(xué)式轉(zhuǎn)換為如下的代數(shù)形式：

(2)

其中：λ∈Rn是拉格朗日乘子；β>0是一個(gè)罰參數(shù)。該方法的迭代形式如下：

(3)

(4)

由于增廣的拉格朗日法(ALM)破壞了xi的分離性，導(dǎo)致計(jì)算較復(fù)雜，但其收斂速度和數(shù)值優(yōu)勢(shì)卻提供了強(qiáng)有力的分離項(xiàng)，因此利用該優(yōu)勢(shì)通過(guò)增加一個(gè)二次項(xiàng)，利用交替的線性技術(shù)做改進(jìn)，有利于產(chǎn)生新思考和新方法。

1.1.2 交替方向乘子法(ADMM)

第2種是交替方向乘子法(ADMM)，具體迭代形式如下：

(5)

(7)

其中：λ∈Rn是拉格朗日乘子；β>0是罰參數(shù)。該方法必須先算出一個(gè)值，然后再算下一個(gè)值，不能并行計(jì)算(并行計(jì)算可減少計(jì)算時(shí)間，提高計(jì)算速度)。由于該方法在迭代中解決產(chǎn)生的子問(wèn)題可能存在一些困難，可改進(jìn)該方法以克服這個(gè)困難。與該方法類似的是交替方向法(ADM)。

1.1.3 交替方向法(ADM)

第3種是交替方向法(ADM)，其迭代形式如下：

(8)

(10)

從迭代式中可以看到：用交替方向法(ADM)計(jì)算模型(1)，經(jīng)驗(yàn)上能起作用，但其收斂性在理論上目前還沒(méi)有得到證明，因此可向該方向努力。那什么時(shí)候它的收斂性就能得到保證？研究表明：當(dāng)所涉及的塊可分的目標(biāo)函數(shù)是強(qiáng)凸時(shí)，交替方向法(ADM)就是全局收斂的，這時(shí)其收斂性就能得到保證。

1.1.4 線性近端的ADM法

第4種是線性近端的ADM法。該方法引入了一個(gè)放縮因子，且該方法同ADM法以及近端的ADM法有相同的限制域。線性近端的ADM法是在ADMM法的基礎(chǔ)上加以改進(jìn)，思想最初源于ADMM法。迭代形式如下：

(11)

(12)

?

(13)

在解決其子問(wèn)題時(shí)，線性近端的ADM法通常有3種處理方式，這3種處理方式的目的都是為了簡(jiǎn)化子問(wèn)題，具體處理方式如下：

1) Algorithm1

第一種版本的線性近端點(diǎn)ADM法，具體步驟：

① 給出已知條件為：

(14)

(15)

?

(16)

③ 終止條件：若滿足

(17)

則停止計(jì)算得到wk+1,此時(shí)wk+1就是該問(wèn)題的最優(yōu)解；否則k=k+1,回到第②步重新計(jì)算，直到滿足終止條件為止。

2) Algorithm2

第2種版本的線性近端點(diǎn)ADM法，具體步驟如下：

① 給出已知條件為

(18)

(19)

?

(20)

③ 終止條件：若滿足

(21)

則停止計(jì)算得到wk+1,此時(shí)wk+1就是該問(wèn)題的最優(yōu)解；否則k=k+1,回到第②步重新計(jì)算，直到滿足終止條件為止。

3) Algorithm3

第3種版本的線性近端點(diǎn)ADM法，具體步驟如下：

① 給出已知條件為

(22)

(23)

?

(24)

③ 終止條件：若滿足

(25)

則停止計(jì)算得到wk+1,此時(shí)wk+1就是該問(wèn)題的最優(yōu)解；否則k=k+1,回到第②步重新計(jì)算，直到滿足終止條件為止。

可以看出這3種處理方式的共同特點(diǎn)都是進(jìn)行線性化二次項(xiàng)，增加鄰近項(xiàng)。線性近端點(diǎn)的ADM法的收斂性和數(shù)值性都比較好，是一種較流行的方法。

1.1.5 高斯向后替換的線性ADM法

第5種方法見(jiàn)文獻(xiàn)[3]，是高斯向后替換的線性ADM法。

讓?duì)?0,α∈(0,1)

(26)

(27)

(28)

(29)

(30)

其中有：

(31)

② 高斯向后替換步(校正步驟)：

(32)

該方法的第②步至關(guān)重要，也可轉(zhuǎn)換為如下形式：

(33)

1.1.6 ADME法

第6種是ADME法。該方法是基于ADM法的思想，只是在迭代形式上有變化，其迭代形式為：

(34)

(35)

?

(36)

從其迭代式可以看出：雖然ADME法的數(shù)值性比較好，但其收斂性目前還沒(méi)有得到證明，正因?yàn)槿绱?，可以通過(guò)適當(dāng)?shù)男Ｕ襟E來(lái)校正ADME法的輸出，從而產(chǎn)生新的迭代方法。在進(jìn)行校正步驟時(shí)，根據(jù)其簡(jiǎn)易程度又可分為ADBC法與ADM-basedsplittingmethod法。

1.1.7ADBC法

(37)

(38)

d(u,v)=M(u-v)

(39)

① ADM迭代步驟:

(40)

(41)

(42)

(43)

② 收縮步驟:

(44)

其中

*

(45)

(46)

1.1.8ADM-basedsplittingmethod

第8種是ADM-basedsplittingmethod，以三維為例，具體步驟如下：

① 給出下面的已知條件為：

(47)

(48)

(49)

(50)

(51)

以上敘述的交替方向法(ADM)、ADM-based splitting method方法的全局收斂性能得到證明，且可以看到該方法在每次迭代時(shí)通過(guò)輕微的校正計(jì)算就能產(chǎn)生一個(gè)新的迭代，從而校正了交替方向法(ADM)的輸出結(jié)果。由文獻(xiàn)[5]知ADM-based splitting method也是一種很好的處理方法。

1.1.9 HTY法

第9種是HTY法，以三維為例，該方法不像第7種與第8種方法對(duì)校正步驟要求較嚴(yán)，即HTY法不需要校正步驟而是需要有一個(gè)更新的乘子。具體迭代步驟為：

其中η>2。

1.2 變分不等式

讓W(xué)=X1×X2×…×Xm×Rl,對(duì)問(wèn)題(1)而言，通常是在它的最優(yōu)性條件下,將問(wèn)題(1)等價(jià)轉(zhuǎn)換，目的是找一個(gè)滿足下列不等式的點(diǎn)w*,見(jiàn)文獻(xiàn)[6-7]，具體的不等式為：

VI(W,F,θ):θ(x)-θ(x*)+(w-w*)TF(w*)≥0, ?w∈W,

通過(guò)對(duì)以上9種方法的敘述以及對(duì)變分不等式的回顧，可知處理問(wèn)題(1)還有其他的方法，這里不再一一敘述。通過(guò)對(duì)這些經(jīng)典方法的回顧，本文在第2部分提出基于分離法的新ADMM法。

2 基于分離法的新ADMM法

在交替方向法(ADM)、ADBC法以及通常的ADMM法的基礎(chǔ)上，本文描述了一種新的ADMM法。該方在文獻(xiàn)[8]的啟發(fā)下，可以看到在每次迭代中，新方法通過(guò)輕微的校正計(jì)算就能產(chǎn)生一個(gè)新的迭代，以三維為例。

minθ1(x1)+θ2(x2)+θ3(x3)

s.tA1x1+A2x2+A3x3=b

x1∈X1,x2∈X2,x3∈X3

具體迭代步驟如下：

① 初始點(diǎn)的選擇：

(52)

④ 收斂準(zhǔn)則(終止條件)：

(53)

3 結(jié)束語(yǔ)

本文研究了一種帶線性約束條件且目標(biāo)函數(shù)是塊可分的凸性最小問(wèn)題，即形如問(wèn)題(1)。該問(wèn)題一般需要用變量分離的方法來(lái)解決。對(duì)于式(1)這樣的問(wèn)題，建議充分利用問(wèn)題本身的結(jié)構(gòu)，如問(wèn)題(1)具有很好的分離性，然后結(jié)合研究產(chǎn)生新ADMM法。從本文的研究結(jié)果可以看出：基于分離法的新ADMM法的校正步驟比較簡(jiǎn)單，減少了計(jì)算量，輸出結(jié)果效果較好?？偟膩?lái)說(shuō)，新方法表明這種分離方法具有吸引性和可行性。

[1] CHATZIPANAGIOTIS N,DENTCHEVA D,ZAVLANOS M M.An augmented lagrangian method for distributed optimization[J].Mathematical Programming,2015,152(1/2):405.

[2] XU M H,WU T.A class of linearized proximal alternating direction methods[J].Optim Theory Appl,2011(151):321-337.

[3] HE BH,TAO M,YUAN X M.Alternating direction method with gaussian back substitution for separable convex programming.SIAM[J].Optim,2012(22):313-340.

[4] HE B,YUAN X.Linearized alternating direction method with gaussian back substitution for separable convex programming[J].Numerical Algebra,Control and Optimization,2013,3(2):247-260.

[5] HE B,XU M,Yuan X.Solving large-scale least squares semidefinite programming by alternating direction methods[J].SIAM Journal on Matrix Analysis and Applications,2011,32(1):136-152.

[6] TAO M,YUAN X.On theO(1/t) convergence rate of alternating direction method with logarithmic-quadratic proximal regularization[J].SIAM Journal on optimization,2012,22(4):1431-1448.

[7] HE B S,TAO M,YUAN XM.A splitting method for separable convex programming[J].IMA Journal of Numerical Analysis,2015(35):394-426.

[8] HAN D,KONG W W,ZHANG W X.A partial splitting augmented lagrangian method for low patch-rank image decomposition[J].Math Imaging Vis,2015,(51):145-160.

(責(zé)任編輯 劉 舸)

Summary of the Method of Convex Optimization Problem on the Objective Function with the Linear Constraints Block Divided

ZENG Qin

(School of Mathematics, Chongqing Normal University, Chongqing 401331, China)

The convexity minimum problem with a linear constraints and a block separable objective function is always studied. As you can see from this article, the objective function which is composed of two or three insufficiently smooth convex functions is firstly studied to promote the objective function composed ofninsufficientlysmoothconvexfunctions.Thesolutiontothemodelisbasedontheclassicalternatingdirectionmethod.Therefore,itstretchesoutalotofkindsofmethodstosolvethemodel.Thearticlesummarizesthecommonmethods,andthenitputsforwardanewmethod:anewADMMmethodbasedonseparationprocess,anditsimultaneouslyindicatesthemethod’sfeasibility.

block of dividing；convex optimization； linear constraint condition;a new method of ADMM

2016-11-09 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11501070)；重慶市自然科學(xué)基金資助項(xiàng)目(cstc2015jcyjA00011)

曾琴(1991—)，女，重慶人，碩士研究生，主要從事運(yùn)籌學(xué)理論和算法研究，E-mail:823235519@qq.com。

曾琴.目標(biāo)函數(shù)帶線性約束塊可分的凸優(yōu)化方法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(8):182-191.

format：ZENG Qin.Summary of the Method of Convex Optimization Problem on the Objective Function with the Linear Constraints Block Divided[J].Journal of Chongqing University of Technology(Natural Science)，2017(8):182-191.

10.3969/j.issn.1674-8425(z).2017.08.030

O224

A

1674-8425(2017)08-0182-10