具有可分離結構的線性約束凸優化問題的迫近正則收縮算法

沈 潔, 高亞麗， 趙 睿

(遼寧師范大學 數學學院,遼寧 大連 116029)

?

具有可分離結構的線性約束凸優化問題的迫近正則收縮算法

沈 潔, 高亞麗， 趙 睿

(遼寧師范大學 數學學院,遼寧 大連 116029)

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

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

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

1 預備知識

考慮具有可分離結構的線性約束凸優化問題[3]：

(1)

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

則上述最優性條件可以寫成下述單調變分不等式的形式：

(2)

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

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

(3)

全文假設式(3)定義的預解算子的求解相對于求解原問題(1)來說是簡單的.基于上述假設,擬應用鄰近點算法(PPA算法),通過選取合適的鄰近參數G,構造求解問題(1)的迫近子問題,進一步對問題(1)提出一種可實現的迫近正則收縮算法,它的收斂性分析基于單調變分不等式收縮算法的統一框架,因而能夠得以保證.

2 具體算法

對于問題(1),將通過與其等價的變分不等式作為研究框架，構造簡單易解的子問題生成新的迭代點.對于變分不等式(2),應用文獻[4-5]中提出的經典的PPA算法和技巧進行求解.

(i)給定當前點ωk,求解下述迫近子問題得到新的迭代點ωk+1∈Ω,

(4)

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

(5)

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

0∈‖‖

(6)

問題(6)相當于求解下述凸規劃

(7)

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

0∈‖‖

(8)

問題(8)相當于求解下述凸規劃

(9)

總的來說,通過適當選取矩陣G,利用變分不等式(4)產生新迭代點的想法是可實現的.在單調變分不等式框架下研究具有可分離結構的線性約束凸優化問題的求解方法,不管是在算法的設計中，還是在收斂性證明中,都會使問題變得簡單和容易執行.

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

(10)

(11)

(12)

則下一迭代點為

(13)

3 收斂性分析

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

由ω*∈Ω,得到

(14)

另一方面,又因為ωk+1∈Ω和ω*是單調變分不等式的解,故有

(15)

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

(16)

(17)

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

[1] 何炳生.凸優化和單調變分不等式的收縮算法[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個可分離算子的凸優化[J].運籌學學報,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

國家自然科學基金資助項目(11301246)

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

1000-1735(2017)02-0150-04

10.11679/lsxblk2017020150

O221.2

A