文摘
我们考虑一类线性约束可分凸规划问题的目标函数三个凸函数没有耦合变量的总和。对于那些问题,汉元(2012)表明,生成的序列交替方向法乘数(小组ADMM)与全球三个街区收敛他们的马在一些技术条件下点。在这篇文章中,一个新的证明,这个结果被发现在新的条件下远低于汉族和人民币的假设。此外,为了加快小组ADMM三个街区,我们还提出一个放松小组ADMM涉及额外计算最优步长和温和条件下建立其全局收敛性。
1。介绍
应用数学和工程各领域,许多问题可以等同于制定与两个街区作为一个可分凸优化问题;也就是说,两个封闭的凸函数对,找到一个解决方案下面的问题: 在哪里是一个矩阵 ,是一个向量。乘数的古典交替方向方法(小组ADMM) [1,2)应用于问题(1)收益率以下方案: 在哪里是拉格朗日乘数和是一个惩罚参数。可能由于其简单性和有效性,小组ADMM与两个街区在理论和应用领域都受到持续关注。我们指的是(3- - - - - -8小组ADMM]理论结果与两个街区(9- - - - - -13)为其有效的应用于高维数据,压缩传感、金融、图像处理、和工程,等等。
在本文中,我们专注于三个街区的线性约束凸规划问题: 在哪里是一个封闭的凸函数,是一个矩阵。为解决(3),一个自然的想法是用两个街区的小组ADMM扩展小组ADMM下一次迭代的三个街区更新的 在哪里 类似于小组ADMM两个街区,与三个街区找到了许多应用程序小组ADMM在广泛的领域,比如双非负锥编程(14),高维数据(15,16),成像科学(17),工程(18]。即使它的数值效率显然从这些应用程序,三个街区的理论治疗小组ADMM是具有挑战性的融合小组ADMM仍只开放给凸目标函数的假设。为了解决这个困难,作者的19,20.)提出了预示校正类型方法解决一般可分凸规划;然而,数值结果表明,直接大幅小组ADMM比它的变体。因此,研究具有重要意义的理论性能小组ADMM三个街区甚至只提供保证收敛的充分条件。我们所知,只存在两个工作目标攻击的收敛问题直接小组ADMM三个街区。通过使用一个错误分析方法,在香港和罗21线性收敛的小组ADMM]证明了块足够小一些技术条件。然而,足够小的要求使算法难以实现。在[22),汉族和人民币采用收缩分析方法建立小组ADMM强烈凸假设下的收敛性和参数小于一个阈值取决于强烈凸模。在本文中,我们首先证明了收敛的小组ADMM三个街区在两个条件下较弱的比(22]。在我们的条件下,阈值参数只依赖于强烈的凸模和,而且不一定是强凸在我们的一个条件。此外,限制范围本文显示至少三倍大的(22]。
为了加快小组ADMM三个街区,我们还提出一个放松小组ADMM三个街区包括额外计算最优步长。具体来说,三倍,我们首先生成一个预测根据(5),然后获得在下一次迭代中
在哪里和是特别的步长中定义(43)。轻松的融合小组ADMM也是建立在温和的条件下。我们应该提到它是可能的修改问题的分析给出超过三个街区的可分性。但这不是本文的重点。
本文的其余部分组织如下。节2,我们列举一些预赛强烈凸函数,次微分,小组ADMM三个街区。节3,我们首先显示的收缩性质之间的距离序列生成的小组ADMM三个街区与解集,然后证明小组ADMM在特定条件下的收敛性。节4与三个街区,我们扩展直接小组ADMM放松小组ADMM最优步长和在合适的条件下建立其收敛性。我们结束我们的论文5。
符号。对任何正整数,让是单位矩阵。我们使用和表示向量欧几里得范数和矩阵的谱范数(定义为矩阵的最大奇异值)。对于任何一个对称矩阵,我们写对于任何。和是两个矩阵定义为 分别。对于给定,,我们经常使用和的共同向量来表示和分别;也就是说, 而和联合向量对应吗和。
2。预赛
在这篇文章中,我们假设,是强凸函数与模量;这是 为每一个。请注意,是一种强凸函数与模量等效的凸性。让是一个点;的次微分在被定义为 从命题6 (23),我们知道,对于每个,和模量是强单调吗这意味着
下一个引理中引入[22)的收敛性分析中扮演着重要角色小组ADMM和放松小组ADMM三个街区。
3所示。小组ADMM三个街区
在本节中,我们首先调查的收缩性质之间的距离序列生成的小组ADMM三个街区和条件下的解集。
引理2。让是一个马的问题(3),让序列由小组ADMM生成三个街区。然后,它认为
证明。自最小化,我们推断的一阶最优性条件 由(14)的单调性(11),它很容易看到 然后为每个, 最后“≥”遵循的基本不平等吗 自 通过直接计算,我们进一步获得 一起,,意味着 请注意, 我们完成这个引理的证明。
使用上面的准备,我们已经准备好证明的小组ADMM三个街区的收敛解(3)下列条件。
定理3。让由小组ADMM序列生成三个街区。然后收敛于一个马的问题(3如果以下条件成立:(我) 和;(2) 满列秩,,。
证明。的不平等(13),它遵循的序列是有界的。回想一下,
因此也有界。此外,从(13)我们看到立即
根据条件,我们知道
因此认为,
因此,序列,,是有界的,一起的有界性,意味着是有界的,是有界的条件或满列秩。此外,由于
通过第一个平等(25)和第三平等(26),它认为
我们继续证明的融合小组ADMM通过考虑以下两种情况。
案例1(和)。在这种情况下,序列收敛于然后
通过第二个平等(26),我们推断(29日),
自是有界的,存在一个三和子序列这样
通过结合(25),(29日)与给定条件,暗示
请注意,
然后,通过双方的限制(33),使用(25)和(29日),并调用上断断续续的,,(24),一个可以立即写
这表明是一个马的问题(3)。因此,不平等(13)也是有效的取而代之的是。那么认为
的收益率
通过添加两个等式(26)(36),我们知道
因此,我们已经表明,整个序列收敛于条件下(我)定理3。
案例2(满列秩,,)。在这种情况下,序列收敛于和是有界的。从第二个平等(25)和(28),我们有
自满列秩,因此认为
让是一个序列的聚点。在案例1类似的证明之后,我们能够展示是一个马的问题(3)和整个序列收敛于这一点。
备注4(见[22])。作者小组ADMM条件下的收敛性证明,是强凸和。我们的结果提高了上限通过。此外,在我们的条件(2)中,只是对强烈凸性假设和而不一定是强凸与积极的模量。
4所示。三个街区的小组ADMM放松
你们的小组ADMM两个街区,和元25)开发了一种变体的交替方向方法和最优步长。数值结果表明,额外的计算最优步长将改善小组ADMM新变种的效率。在本节中,通过采用你们的基本想法和元25与三个街区),我们提出一个放松小组ADMM加速小组ADMM通过最优步长。对于简单符号,我们写 与,新的迭代扩展小组ADMM由 在哪里的解决方案(5),被定义为
引理5。让序列由放松小组ADMM生成三个街区。然后,如果下面的语句都是有效的:(我) 因此;(2) −−。
证明。通过直接计算,我们知道 第二个不平等是柯西不等式。因此认为, 完成第一部分的证明。由引理1和小学不平等(17),它可以很容易地证明 然后 加之这一事实,完成了证明。
基于上面的不平等,我们可以证明下面的收敛结果放松小组ADMM三个街区。自符合证明定理3,我们忽略它。
定理6。让是小组ADMM序列生成的放松。然后收敛于一个马的问题(3)的条件下和,满列秩。
5。结论的话
在本文中,我们调查小组ADMM一步可分凸规划问题的三个街区。基于收缩分析序列和的解集之间的距离,我们建立的理论结果保证小组ADMM三块的全局收敛性较弱的条件下比在(22]。采用的基本思想25),我们也提供一个放松小组ADMM最优步长加速小组ADMM和温和的假设下证明其收敛性。
承认
第一作者是江苏省自然科学基金和中国国家自然科学基金项目。71271112。第二作者支持下的江苏大学自然科学研究基金批准号13 kjd110002。