有限族非空闭凸集交上的投影算子迭代算法  

Iterative algorithms for solving projection operator onto the intersection of a finite family nonempty closed convex sets

作　　者：宗春香 蔡用[1] 唐玉超[1,2] ZONG Chunxiang;CAI Yong;TANG Yuchao(Department of Mathematics ,Nanchang University,Nanchang 330031,China;School of Management,Nanchang University,Nanchang 330031,China)

机构地区：[1]南昌大学数学系,江西南昌330031 [2]南昌大学管理学院,江西南昌330031

出　　处：《南昌大学学报（理科版）》2018年第4期327-338,共12页Journal of Nanchang University(Natural Science)

基　　金：国家自然科学基金资助项目(11661056;11401293);江西省自然科学基金资助项目(20151BAB211010;20142BAB211016);中国博士后科学基金资助项目(2015M571989);江西省博士后科学基金资助项目(2015KY51)

摘　　要：梯度投影算法在信号与图像处理、机器学习和数据挖掘等很多领域中有着广泛的应用,如何有效的计算投影算子是该算法的关键。对于单一闭凸集上的投影算子的计算,特别是具有稀疏约束的集合,已有很多的研究者给出了不同的优化算法。对于多个非空闭凸集合交上的投影,需要根据集合的性质设计算法。本文给出在一般Hilbert空间中有限族非空闭凸集合交上投影算子计算的统一方法。首先,我们定义笛卡尔乘积空间,将有限族非空闭凸集的交转化为两个非空闭凸集的交,然后将Dykstra算法推广到这类问题的求解。同时,我们将有限族非空闭凸集交上投影问题转化为无约束优化问题,并基于Douglas-Rachford算子分裂和三算子分裂方法思想,建立求解该无约束优化问题的迭代算法及证明算法的收敛性。最后,应用所提算法求解具有非负约束的l1范数单位球上的投影问题,通过数值实验,结果表明所提算法能快速和准确的收敛到真实解。Gradient projection algorithm has been widely used in many fields such as signal and image processing,machine learning and data mining.How to effectively calculate the projection operator is the key of this algorithm.For the computation of projection operators on a single closed convex set,especially those with sparse constraints,many researchers have given different optimization algorithms.With regard to the projection of the intersection of multiple nonempty closed convex sets,it is necessary to design the algorithm according to the nature of the set.In this paper,we present a unified method for the calculation of projection operators on a finite family of nonempty closed convex sets in a general Hilbert space.First,we define the Cartesian product space and transform the intersection of the finite family nonempty closed convex sets into the intersection of two nonempty closed convex sets.The Dykstra’s algorithm is then generalized to solve such problem.At the same time,we transform the projection problem of finite family nonempty closed convex sets into an unconstrained optimization problem.Based on the ideas of Douglas-Rachford and three-operator splitting methods,we establish several iterative algorithms to solve the unconstrained optimization problem and prove the convergence of these algorithms.Finally,we apply the proposed algorithms to solve the closed l1 norm ball problem with non-negative constraints.Numerical experiments show that the proposed algorithms can converge to the real solution quickly and accurately.

关 键 词：投影算子 Dykstra算法 Douglas-Rachford算法 三算子分裂算法 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]