曾 紅 秀

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

一個(gè)解可分凸優(yōu)化問題的部分預(yù)校正分裂法

曾 紅 秀

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

考慮線性約束的可分離凸優(yōu)化問題，其目標(biāo)函數(shù)可分為沒有耦合變量的3個(gè)獨(dú)立的凸函數(shù).基于擴(kuò)展的輪換方向乘子法，提出了一個(gè)新的解可分離凸優(yōu)化問題的部分預(yù)校正分裂法，此算法在校正步中考慮對(duì)第1個(gè)變量不進(jìn)行校正，對(duì)第2個(gè)和第3個(gè)變量進(jìn)行校正；并且在較弱的條件下，證明了此算法的收斂性.

凸優(yōu)化問題；輪換方向乘子法；部分預(yù)校正分裂法；罰參數(shù)

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

在本文中，主要考慮如下結(jié)構(gòu)型凸優(yōu)化問題：

(1)

令θ:Rn→(-∞,+∞)，如果θ的域記為domθ:={x∈Rn,θ(x)<+∞}是非空的，則稱θ是恰當(dāng)?shù)?如果對(duì)于任意的x∈Rn和y∈Rn，總有

則稱f是凸函數(shù).一個(gè)集值算子T在Rn中被稱為是單調(diào)的，如果滿足

記Γ0(Rn)為下半連續(xù)恰當(dāng)?shù)耐购瘮?shù)從Rn到(-∞,+∞)的集合，則對(duì)于任意的θ∈Γ0(Rn)，θ是集值算子的次微分被定義為

為了方便進(jìn)一步的分析，令

(2)

通過引用凸優(yōu)化問題的一階最優(yōu)性條件，式(1)可以很容易地被定性為下面的變分不等式問題[1]:找到一個(gè)向量u*∈U，使得

(3)

其中U:=X1×X2×X3×Rl,

因?yàn)棣萯(i=1,2,3)是閉凸函數(shù)，Ai(i=1,2,3)是列滿秩矩陣，則式(3)是有解的[2],記式(3)為MVI(F,U),也就是說，點(diǎn)u*的集合滿足式(3)，被記為U*,而且是非空的.

目前解決可分凸優(yōu)化問題有許多有效的方法，如輪換方向法、增廣拉格朗日法和預(yù)矯正鄰近點(diǎn)法等[3-5].為了充分利用目標(biāo)函數(shù)可分的特點(diǎn)，Gabay等[6-7]提出輪換方向乘子法,并且它在文獻(xiàn)中已經(jīng)被很廣泛地的研究.輪換方向乘子法起初用于求解兩個(gè)可分離變量的凸優(yōu)化問題而被發(fā)展，結(jié)構(gòu)如下：

x1∈X1,x2∈X2

迭代方案如下：

(4)

其中λ∈Rl是拉格朗日乘子，β>0是一個(gè)罰參數(shù).近年來，為了進(jìn)一步提高迭代步(4)的計(jì)算效率[8],研究者們將輪換方向乘子法運(yùn)用到帶有3個(gè)可分離變量的凸優(yōu)化問題中，得到擴(kuò)展的輪換方向乘子法，其迭代格式如下:

(5)

其中Lβ(x1,x2,x3,λ)是增廣拉格朗日函數(shù):

擴(kuò)展的輪換方向乘子法迭代方案式(5)的數(shù)值很有前途，因此一直在圖像處理和統(tǒng)計(jì)學(xué)習(xí)的混合正規(guī)化模型中處于中心地位[2-9].但是近幾年發(fā)現(xiàn)在較弱的條件下，此方法的收斂性仍然是一個(gè)開放性問題，因此本文將朝著這個(gè)目標(biāo)進(jìn)一步發(fā)展.

2 算 法

在這一部分中，提出一個(gè)新的求解問題(1)的可分凸優(yōu)化問題的部分預(yù)校正分裂法.

算法1：解可分凸優(yōu)化問題的部分預(yù)校正分裂法.

(6)

步2(收斂性分析) 如果

則算法終止；否則，轉(zhuǎn)步3.

(7)

令k:=k+1，返回步1.

3 收斂性分析

(8)

通過在式(6)中引用凸優(yōu)化問題的一階最優(yōu)性條件，可得

(9)

進(jìn)而可以得出結(jié)論:

(10)

(11)

(12)

式(11)與(12)相加，得

通過F的單調(diào)性并重新排列，得

(13)

同理，可得

(14)

(15)

故結(jié)論成立.

下面3個(gè)等式明顯成立：

(16)

(17)

(18)

上面3個(gè)等式(16)—(18)與式(10)相加，得

(19)

(20)

證明 由式(7)，得

(21)

以及

(22)

下面等式(23)與上述兩個(gè)等式(21)(22)相加，得

(23)

可得

(24)

(25)

將式(25)代入式(24)中，即結(jié)論成立.

令k=0,1,…,∞相加，得

即可得

(27)

(28)

(29)

由式(3)可得

4 結(jié) 論

主要提出了一種用新的部分預(yù)校正分裂法求解3個(gè)可分離變量的凸優(yōu)化問題.首先將此問題轉(zhuǎn)化為求解可分離結(jié)構(gòu)型變分不等式問題，基于擴(kuò)展的輪換方向乘子法，進(jìn)而提出了解可分離凸優(yōu)化問題的部分預(yù)校正分裂法.并且在較弱的條件下，證明了新算法的全局收斂性.

[1] FACCHINEI F,PANG J.Finite-Dimensional Variational Inequalities and Complementarity Problems[M].Springer,2003

[2]TAO M,YUAN X.Recovering Low-Rank and Sparse Components of Matrices From Incomplete and Noisy Observations[J].SIAM J: Optim,2011,21:57-81

[3]AUSLENDER A,HADDOU M.An Interior Proximal Point Method for Convex Linearly Constrained Problems and Its Extention to Variational Inequalities[J].Mathematical Programming,1995,71 : 77-100

[4]YUAN X M.An Improved Proximal Alternating Direction Method for Monotone Variational Inequalities with Separable Structure[J].Computational Optimization and Applications,2011,49: 17-29

[5] 羅立.推廣的預(yù)矯正鄰近點(diǎn)法求解可分凸優(yōu)化問題,重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,33(1):19-22

LUO L.Separable Convex Optimization Problem is Solved by Promoted Pre-correction Neighboring Point Method[J].Journal of Chongqing Technology and Business University (Naturnal Science Edition),2016，33(1)：19-22

[6] GABAY D,MERCIER B.A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximations[J].Comput Math Appl,1976(2):17-40

[7] FORTIN M,GLOWINSKI R.Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems[J].North-Holland,1983(1):299-331

[8] BOYD S,PARIKH N,CHU E,et al.Distributed Optimi-zation and Statistical Learning via the Alternating Direction Method of Multipliers[J].Found Trends Mach Learn,2010(3):120-122

[9] NG M,YUAN X,ZHANG W.A Coupled Variational Image Decomposition and Restoration Model for Blurred Cartoon-Plus-Texture Images with Missing Pixels[J].Image Process,2013,22:2233-2246

[10] CHEN G,TEBOULLE M.A Proximal-based Decomposition Method for Convex Minimization Problems[J].Math Program,1994, 64:81-101

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

A Partial Prediction-correction Splitting Method for Solving Separable Convex Optimization Problems

ZENG Hong-xiu

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

By considering the separable convex optimization problems with linear constraints, their objective function can be divided into three independent convex functions without coupling variables. Based on the extension of alternating direction of multipliers, this paper presents a new partial prediction-correction splitting method for solving separable convex optimization problems, this algorithm considers that the first variable is not corrected in correction step but the second variable and third variable are corrected. In addition, the convergence of this algorithm is proved under weaker condition.

convex optimization problem; alternating direction method of multipliers; partial prediction-correction splitting method; penalty parameter

2016-12-06；

2017-01-15.

曾紅秀(1992-)，女，重慶忠縣人，碩士研究生，從事最優(yōu)化理論與算法研究.

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

O221.1

A

1672-058X(2017)04-0010-06