具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題的迫近正則收縮算法

沈 潔, 高亞麗， 趙 睿

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)

?

具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題的迫近正則收縮算法

沈 潔, 高亞麗， 趙 睿

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)

對(duì)具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題(也就是目標(biāo)函數(shù)是有2個(gè)算子和形式的可分離凸優(yōu)化問(wèn)題)展開研究，考慮在一定的假設(shè)條件下，通過(guò)選取合適的迫近正則參數(shù)矩陣G,擬利用可實(shí)現(xiàn)的迫近正則收縮法求解具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題.將與原問(wèn)題等價(jià)的變分不等式作為理論研究框架,通過(guò)將原問(wèn)題轉(zhuǎn)化為一系列容易求解的子問(wèn)題,達(dá)到降低原問(wèn)題求解難度的目的，下一個(gè)迭代點(diǎn)的獲取通過(guò)求解子問(wèn)題生成.最后，提出一種新的迫近正則收縮算法,并且應(yīng)用變分不等式等相關(guān)理論對(duì)文中給出的迫近正則收縮算法進(jìn)行了收斂性分析.

凸優(yōu)化;線性約束;迫近正則收縮算法;變分不等式

隨著科學(xué)技術(shù)的發(fā)展及各學(xué)科之間的交叉融合,優(yōu)化問(wèn)題在生活中扮演著重要的角色,越來(lái)越多的問(wèn)題可以轉(zhuǎn)化成優(yōu)化問(wèn)題來(lái)解決.對(duì)于具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題,何炳生[1]給出了利用定制PPA算法(鄰近點(diǎn)算法)意義下的乘子交替方向法和線性化交替方向法的求解方法.本文利用文獻(xiàn)[2]中的解線性約束凸優(yōu)化問(wèn)題的思想,考慮具有2個(gè)算子和形式的可分離凸優(yōu)化問(wèn)題,擬利用可實(shí)現(xiàn)的迫近正則收縮算法進(jìn)行求解.這類方法的基本思路與交替方向法本質(zhì)相同,是將原問(wèn)題轉(zhuǎn)化為一系列近似子問(wèn)題,子問(wèn)題從形式到具體操作都比原問(wèn)題容易求解.

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

考慮具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題[3]：

(1)

其中，A∈m×n1,B∈m×n2,b∈m,X?n1和Y?n2是閉凸集,n1+n2=m，θ1:n1→,θ2:n2→和是可微凸函數(shù).假設(shè)問(wèn)題(1)的最優(yōu)解集非空.記λ∈m是Lagrange乘子,則問(wèn)題(1)的Lagrange函數(shù)為

則上述最優(yōu)性條件可以寫成下述單調(diào)變分不等式的形式：

(2)

記Ω*是單調(diào)變分不等式(2)的非空解集.

?a∈n及r>0，預(yù)解算子定義如下：

(3)

全文假設(shè)式(3)定義的預(yù)解算子的求解相對(duì)于求解原問(wèn)題(1)來(lái)說(shuō)是簡(jiǎn)單的.基于上述假設(shè),擬應(yīng)用鄰近點(diǎn)算法(PPA算法),通過(guò)選取合適的鄰近參數(shù)G,構(gòu)造求解問(wèn)題(1)的迫近子問(wèn)題,進(jìn)一步對(duì)問(wèn)題(1)提出一種可實(shí)現(xiàn)的迫近正則收縮算法,它的收斂性分析基于單調(diào)變分不等式收縮算法的統(tǒng)一框架,因而能夠得以保證.

2 具體算法

對(duì)于問(wèn)題(1),將通過(guò)與其等價(jià)的變分不等式作為研究框架，構(gòu)造簡(jiǎn)單易解的子問(wèn)題生成新的迭代點(diǎn).對(duì)于變分不等式(2),應(yīng)用文獻(xiàn)[4-5]中提出的經(jīng)典的PPA算法和技巧進(jìn)行求解.

(i)給定當(dāng)前點(diǎn)ωk,求解下述迫近子問(wèn)題得到新的迭代點(diǎn)ωk+1∈Ω,

(4)

其中,r>0,s>0,為了保證G的正定性,需要rs>‖BTB‖+‖ATA‖.

(5)

將式(5)中最后一行展開,得到

0∈‖‖

(6)

問(wèn)題(6)相當(dāng)于求解下述凸規(guī)劃

(7)

同理,將式(5)中第二行展開得到

0∈‖‖

(8)

問(wèn)題(8)相當(dāng)于求解下述凸規(guī)劃

(9)

總的來(lái)說(shuō),通過(guò)適當(dāng)選取矩陣G,利用變分不等式(4)產(chǎn)生新迭代點(diǎn)的想法是可實(shí)現(xiàn)的.在單調(diào)變分不等式框架下研究具有可分離結(jié)構(gòu)的線性約束凸優(yōu)化問(wèn)題的求解方法,不管是在算法的設(shè)計(jì)中，還是在收斂性證明中,都會(huì)使問(wèn)題變得簡(jiǎn)單和容易執(zhí)行.

基于前面的分析,現(xiàn)在對(duì)于問(wèn)題(1)提出一種新的迫近正則收縮算法.

(10)

(11)

(12)

則下一迭代點(diǎn)為

(13)

3 收斂性分析

其中，c>0是常數(shù),Ω是閉凸集,G是正定矩陣,ω*是式(2)的解,稱這個(gè)序列是收斂的.

由ω*∈Ω,得到

(14)

另一方面,又因?yàn)棣豮+1∈Ω和ω*是單調(diào)變分不等式的解,故有

(15)

將式(14)和式(15)兩式相加,再利用F的單調(diào)性,有

(16)

(17)

其中的不等式成立是依據(jù)式(17),定理得證.

[1] 何炳生.凸優(yōu)化和單調(diào)變分不等式的收縮算法[EB/OL].http://math.nju.edu.cn/～hebma.

[2] HE Bingsheng,YUAN Xiaoming.A contraction method with implementable proximal regularization for linearly constrained convex programming[J].Optimization Online,2011,2:1-6.

[3] 何炳生.修正乘子交替方向法求解3個(gè)可分離算子的凸優(yōu)化[J].運(yùn)籌學(xué)學(xué)報(bào),2015,19(3):57-70.

[4] MARTINET B.Regularization,equations variationelles par approximations succesives[J].Rev Francaise Informat Recherche Oper,1970,4(4):154-158.

[5] ROCKAFELLAR R T.Monotone operators and the proximal point algorithm[J].SIAM J Control Optim,1976,14:877-989.

A contraction method with proximal regularization for linearly constrained convex optimization problem with separable structures

SHENJie，GAOYali，ZHAORui

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

In this paper, we study the linearly constrained convex optimization problem with separable structures (i.e., the convex optimization problem whose objective function is the sum of two operators).By selecting the appropriate proximal regularization parameterG,we can imitate a contraction method with implementable proximal regularization to solve the linearly constrained convex optimization problem with separable structure,and we take variational inequality as theoretical framework which is equivalent to original problem,and transform the original problem into a series of easy subproblems to reduce the difficulty in solving original problem. The next iterate point is obtained by solving subproblems. Finally, a new proximal regularization algorithm is proposed and its convergence is analyzed by using relevant variational inequality theories.

convex optimization;linear constraint;proximal regularization contraction method;variational inequality

2017-01-20

國(guó)家自然科學(xué)基金資助項(xiàng)目(11301246)

沈潔(1973-),女,遼寧沈陽(yáng)人,遼寧師范大學(xué)副教授,博士.

1000-1735(2017)02-0150-04

10.11679/lsxblk2017020150

O221.2

A