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

曾 琴

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

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

曾 琴

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

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

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

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

1 預(yù)備知識

1.1 方法回顧

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

(1)

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

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

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

(2)

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

(3)

(4)

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

1.1.2 交替方向乘子法(ADMM)

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

(5)

(7)

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

1.1.3 交替方向法(ADM)

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

(8)

(10)

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

1.1.4 線性近端的ADM法

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

(11)

(12)

?

(13)

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

1) Algorithm1

第一種版本的線性近端點ADM法，具體步驟：

① 給出已知條件為：

(14)

(15)

?

(16)

③ 終止條件：若滿足

(17)

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

2) Algorithm2

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

① 給出已知條件為

(18)

(19)

?

(20)

③ 終止條件：若滿足

(21)

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

3) Algorithm3

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

① 給出已知條件為

(22)

(23)

?

(24)

③ 終止條件：若滿足

(25)

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

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

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

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

讓β>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ù)值性比較好，但其收斂性目前還沒有得到證明，正因為如此，可以通過適當?shù)男Ｕ襟E來校正ADME法的輸出，從而產(chǎn)生新的迭代方法。在進行校正步驟時，根據(jù)其簡易程度又可分為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方法的全局收斂性能得到證明，且可以看到該方法在每次迭代時通過輕微的校正計算就能產(chǎn)生一個新的迭代，從而校正了交替方向法(ADM)的輸出結(jié)果。由文獻[5]知ADM-based splitting method也是一種很好的處理方法。

1.1.9 HTY法

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

其中η>2。

1.2 變分不等式

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

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

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

2 基于分離法的新ADMM法

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

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

s.tA1x1+A2x2+A3x3=b

x1∈X1,x2∈X2,x3∈X3

具體迭代步驟如下：

① 初始點的選擇：

(52)

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

(53)

3 結(jié)束語

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

[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.

(責任編輯 劉 舸)

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 基金項目：國家自然科學基金資助項目(11501070)；重慶市自然科學基金資助項目(cstc2015jcyjA00011)

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

曾琴.目標函數(shù)帶線性約束塊可分的凸優(yōu)化方法[J].重慶理工大學學報(自然科學)，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