具有可分离结构的线性约束凸优化问题的迫近正则收缩算法

沈 洁, 高亚丽， 赵 睿

(辽宁师范大学 数学学院,辽宁 大连 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