求解凸極小化問題的一種帶預校正步的分解方法

李小蓉

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

求解凸極小化問題的一種帶預校正步的分解方法

李小蓉

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

針對三個變量的可分離凸優(yōu)化問題，提出了一種帶預校正步的交替方向分解方法.與交替方向乘子法和預校正近似乘子法相比，該算法同樣使用了增廣拉格朗日函數(shù)，并且對偶變量進行了兩次迭代.不同于之處在于，這種算法推廣到了三個變量的情況.在系數(shù)矩陣是列滿秩及拉格朗日函數(shù)有鞍點的假設(shè)下，該算法是收斂的.

凸優(yōu)化問題；交替方向乘子法；預校正步

分解方法對于解決凸優(yōu)化問題是有效可行的方法.通過分解，將原問題分解為多個子問題進行求解.在多區(qū)域電力系統(tǒng)分析、網(wǎng)絡(luò)設(shè)計、多原則設(shè)計優(yōu)化模型等領(lǐng)域中，經(jīng)常遇到各種問題，使得提出一個比較好實施的分布式計算框架顯得尤為重要.本文針對三個變量的可分離凸優(yōu)化問題進行研究[1]，形式如下:

問題(1)的增廣拉格朗日函數(shù)Ψ:Rn×Rs×Rm→(－∞，＋∞]定義如下:

其中:〈·，·?表示內(nèi)積，λ是約束A1x1＋A2x2＋A3x3＝b相應的拉格朗日乘子，c是罰因子.

問題(1)的對偶問題為:

其中:θ(λ)＝inf{L(x1，x2，x3，λ):x1∈χ1，x2∈χ2，x3∈χ3}，分別為原問題和對偶問題的最優(yōu)

解，鞍點最優(yōu)性條件為:

針對兩個變量的可分離凸優(yōu)化問題，在1975年，R.Glowinsk[2]和D.Gabay[3]等人提出了一種算法，即交替方向乘子法(alternating direction method of multiplier，ADMM).這種算法的主要迭代格式如下:

在矩陣A1，A2滿足列滿秩及拉格朗日函數(shù)L(x1，x2，λ)有鞍點的假設(shè)下，ADMM算法是收斂的.交替方向乘子法是一種簡單但功能強大的算法，所以被廣泛應用于各個領(lǐng)域，詳情可見文獻[4－11].

針對三個變量的可分離凸優(yōu)化問題，在2012年，D.Han，X.Yuan，W.Zhang[12]針對三個變量的可分離凸優(yōu)化問題，提出了一種基于ADM的分裂法，將其轉(zhuǎn)化成一個等價的具有可分離結(jié)構(gòu)變分不等式問題.假設(shè)凸優(yōu)化問題的解集是非空的，且約束條件的系數(shù)矩陣是滿秩的，在這種假設(shè)條件下，證明了算法的全局收斂性.基于ADM的分裂法主要迭代格式如下:

通過計算:

1994年，Chen和Teboulle[13]針對兩個變量的可分離凸優(yōu)化問題，提出了一種可分方法，即預校正近似乘子法(predictor－corrector proximal multiplier method，PCPMM).預校正近似乘子法的主要算法如下:

在拉格朗日函數(shù)有鞍點的情況下，PCPMM算法是收斂的.與交替方向乘子法的不同之處在于，PCPMM算法用鄰近項替代了增廣項，關(guān)于對偶變量進行了兩次迭代.從迭代過程可以看出的計算是并行的.在上述兩種算法的基礎(chǔ)之上做出了一些改進，提出了一種預測校正交替方向乘子法(predictor－corrector alternating direction method of multiplier，PCADMM).

與預校正近似乘子法相比，在極小化時采取不同的格式，去掉了二次鄰近項而直接用的增廣項.算法的主要迭代格式如下:

在矩陣A1，A2滿足列滿秩及拉格朗日函數(shù)L(x1，x2，λ)有鞍點的假設(shè)下，ADMM算法是收斂的.為了使得算法的應用更加廣泛，將上述算法推廣到了三個變量的可分離凸優(yōu)化問題，即EPCADMM.該算法的證明與PCADMM算法的證明相似，但是終止準則發(fā)生了變化.在PCADMM中，終止準則為但是在EPCADMM算法中，若則算法停止.

1 推廣的預測校正交替方向乘子法

步驟2 計算:

步驟3 乘子更新:

2 收斂性證明

對于問題(1)，通過引用一階最優(yōu)性條件和鞍點最優(yōu)性條件[4，14－16]，我們很容易可以看到，求解問題(1)等價于求解變分不等式的一個解.

在這里，

1)該鐵礦石為低硅低硫磷的酸性富鐵礦，礦石氧化嚴重，有用礦物以磁鐵礦為主，次為褐鐵礦、假象赤鐵礦，礦物組成較復雜。磁性分析表明，該礦磁性良好，可通過弱磁選實現(xiàn)去雜提純的目的。

用VI(U，Q)表示VI(8)～(9).用u?表示VI(8)～(9)的解，在假設(shè)條件下，解集u?是非空的.在這一部分，對推廣的預測校正交替方向乘子法的收斂性進行了證明.

證明 假設(shè)蘊含著:

由EPCADMM算法的式(5)和式(7)兩個式子，可以得到λk＋1＝pk＋1＝λk.

另一方面，在式(12)中，將xi′置為，得到:

同理，可以得到:

將式(16)～(18)加起來，可以得到:

因為λk＋1－λ?＝λk－λ?＋λk＋1－λk，對上式進行整理，得到:

這就完成了證明.

以下的等式顯然是成立的.

將以上三個式子加到式(13)中，可以得到:

證明 下面的等式顯然成立，

由此，可以得到:

通過式(18)、式(5)、式(7)可以得到上述不等式.對于任意的向量u、v和任意的正參數(shù)l>0，有:2uTv≤l因此，引理3得證.

證明 由式(20)，可以推出:

對所有的k(k＝0，1，…)求和，可以得到:

從上式，可得出:

因為A1、A2、A3滿秩，所以序列僅有一個聚點.因為序列收斂到為VI(8)～(9)的一個解，引理4得證.

[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，2010，3(1):1－122.

[2] GLOWINSKI R，LETALLEC P.Augmented lagrangian and operator splitting methods in nonlinear mechanics[M].Philadelphia:SIAM Studies in Applied Mathematics，SIAM，PA，1989.

[3] GABAY D，MERCIAR B.A Dual Algorithm for the solution of Nonlinear Variation Problems via Finite－element Approximations[J].Computers and Mathematics with Application，1976，2(1):17－40.

[4] CHEN C H，HE B S，YUAN X M.Matrix completion via alternating direction method[J].IMA J Numer Analysis，2012，32(1):227－245.

[5] ECKSTEIN J，BERTSEKAS D P.On the Douglas－Rachord splitting method and the proximalpoint algorithm for maximal monotone operators[J]. Math Program，1992，55(3):293－381.

[6] ESSER E.Applications of Lagrangian－Based alternating direction methods and connections to split Bregman[J].Cam Report，2009，9:31－36.

[7] HE B S，XU M H，YUAN X M.Solving large－scale least squares covariance matrix problems by alternating direction methods[J].SIAM J Matrix Analy Appli，2011，32(1):136－152.

[8] SETZER S，STEIDL G，TEBUBER T.Deblurring Poissonian images by split Bregman techniques[J].J Visual Commun Image Repres，2010，21 (3):193－199.

[9] SUN J，ZHANG S.A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs[J].European J Oper Res，2010，207:1210－1220.

[10] TAO M，YUAN X M.Recovering low－rank and sparse components of matrices from incom－plete and noisy observations[J].SIAM J Optim，2011，21(1):57－81.

[11] 李慧.解凸優(yōu)化問題的一類修正線性近似交替方向法[J].重慶工商大學學報(自然科學版)，2015，32(4):23－27.

[12] HAN D，YUAN X，ZHANG W.An ADM－based splitting method for separable convex programming[J].Computational optimization and applications，2013，54(2):343－369.

[13] CHEN G，TEBOULLE M.A proximal－based decomposition method for convex minimization problems[J].Mathematical Programming，1994，64 (1/3):81－101.

[14] BAZARAA M S，SHERALI H D，SHETTY C M.Nonlinear programming[M].Belmunt:Athena Scientific，2006，163－235.

[15] HAN D，KONG W，ZHANG W.A Partial Splitting Augmented Lagrangian Method for Low Patch－Rank Image Decomposition[J].Journal of Mathematical Imaging and Vision，2014，51(1):145－160.

[16] HAN D，YUAN X.A Note on the Alternating Direction Method of Multipliers[J].Journal of Optimization Theory and Applications，2012，155(1): 227－238.

責任編輯:時 凌

A Decomposition Method with Predictor－corrector for Solving Convex Minimization Problems

LI Xiaorong
(School of Mathematical Sciences，Chongqing Normal University，Chongqing 401331，China)

For the block－separable convex optimization problem of three variables，we proposed a decomposition method with a predictor－correction step.Compared with the alternating direction method of multiplier and the predictor－corrector proximal multiplier method，the algorithm also uses the augmented Lagrangian function and two iterations are made for the dual variables.The difference is that this algorithm is extended to three variables.Under the assumptions that the matricesare full－column－rank and the Lagrangian function has a saddle point，the algorithm converges.

convex programming problem；alternating direction method of multiplier；predictor－corrector

O224

A

2016－12－06.

國家自然科學基金項目(61263020).

李小容(1990－)，女，碩士生，主要從事計算數(shù)學的研究.