凸优化和单调变分不等式收缩算法的统一框架  

A uniform framework of contraction methods for convex optimization and monotone variational inequality

作　　者：何炳生 Bingsheng He

机构地区：[1]南方科技大学数学系,深圳518055 [2]南京大学数学系,南京210093

出　　处：《中国科学：数学》2018年第2期255-272,共18页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11471156)资助项目

摘　　要：线性约束的凸优化问题可以转化成一个形式更一般的单调变分不等式.在变分不等式的框架下研究最优化问题的求解方法,就像微积分中利用导数求函数的极值,常常会带来很大的方便.求解单调变分不等式的投影收缩算法有一个预测-校正的统一框架,基于"孪生方向和相同步长"有两类花费几乎相当的算法,计算实践证明第二类算法效率往往更高.近年发展起来并被广泛采用的凸规划的分裂收缩算法属于一个更一般的框架,这个框架中的预测同样提供了一对孪生方向.迄今为止的凸规划的分裂收缩算法,都相当于变分不等式投影收缩算法中的第一类算法.本文指出,利用现有的步长法则,配上孪生方向中的另一个方向,同样可以构造相应的第二类算法.本文在统一框架下证明了两类算法的O(1/t)迭代复杂性.Linearly constrained convex optimization problems can be reformulated as monotone variational inequalities, which include linearly constrained convex optimization problems as special cases. Usually, deriving and studying optimization methods in the framework of variational inequalities are often more convenient. Based on the twin directions and identical step size, there exists a unified predictor-corrector framework for projectioncontraction methods solving monotone variational inequalities. According to the twin directions, the unified framework falls into two classes with similar computational cost in each iteration, while totally the second class outperforms the first as confirmed in numerical experiments. Most recently developed splitting contraction methods belong to a more general framework, in which similar twin directions can be generated. However, until now,all splitting contraction methods can be seen as generalizations of the methods in the first class of the unified predictor-corrector framework. In this paper, the generalization of methods in the second class is derived using existing step size and the other generalized direction. The O（1/t） iteration complexity is proved in the generalized unified framework.

关 键 词：凸优化 单调变分不等式 投影收缩算法 分裂收缩算法 统一框架 孪生方向和相同步长 

分 类 号：O224[理学—运筹学与控制论]