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

曾 紅 秀

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

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

曾 紅 秀

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

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

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

1 預備知識

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

(1)

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

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

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

為了方便進一步的分析，令

(2)

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

(3)

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

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

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

x1∈X1,x2∈X2

迭代方案如下：

(4)

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

(5)

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

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

2 算 法

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

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

(6)

步2(收斂性分析) 如果

則算法終止；否則，轉步3.

(7)

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

3 收斂性分析

(8)

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

(9)

進而可以得出結論:

(10)

(11)

(12)

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

通過F的單調性并重新排列，得

(13)

同理，可得

(14)

(15)

故結論成立.

下面3個等式明顯成立：

(16)

(17)

(18)

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

(19)

(20)

證明 由式(7)，得

(21)

以及

(22)

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

(23)

可得

(24)

(25)

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

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

即可得

(27)

(28)

(29)

由式(3)可得

4 結 論

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

[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ōu)化問題,重慶工商大學學報(自然科學版),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

責任編輯：李翠薇

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