两个可分离目标函数的线性约束凸优化问题

两个可分离目标函数的线性约束凸优化问题

1结构的凸优化问题的求解本文讨论了两个分离对象函数的线性约束凸优化问题。它的数学形式是。其中A∈增广Lagrange函数则是在Lagrange函数的基础上加上线性约束的二次罚函数,数学表达式是乘子交替方向法(AlternatingDirectionsMethodofMultipliers),简称ADMM,通常也称之为交替方向法,是以分离形式极小化增广Lagrange函数的方法具体说来,经典的乘子交替方向法求解可分离结构的凸优化问题(1.1),它的第k-次迭代从给定的(y完成一次迭代,为下一次迭代提供了一个新的(y交换顺序的乘子交替方向法提供新的(y加快收敛速度.实际操作中,往往取α∈[1.2,1.8].这两类ADMM方法中,迭代都从(y优化问题中,变动目标函数中的常数项,对问题的解不会产生任何影响.因此,对乘子交替方向法的x-子问题(1.4a),我们有也就是说,若记同理,若记在一些实际应用中,由于矩阵A和B的具体形式,有时子问题(1.6a)和(1.6b)中有一个(也往往至多一个)不容易求解,人们进而考虑“线性化”的求解方法.为了使线性化方法中,x仍然是中间变量,我们把不容易求解的问题安排成第二个子问题,即y子问题.例如,对于可以归结为求解min{f(By)+g(y)|y∈y}的问题,转化成等价的用交替方向法求解的时候,就只需要线性化y子问题.对(1.4b)目标函数中二次函数部分做Taylor展开,有由于优化问题的解并不因为目标函数中的常数项改变而改变,我们有人们说的“线性化”,就是把目标函数中的二次项线性化以后的y-子问题就变成其中通过线性化加正则化,ADMM的子问题得到简化.这样的方法在科学计算中得到广泛采用本文在子问题有解析解,或者容易求得高精度解的假设下,总结两类“线性化”加“正则化”的求解方法.在变分不等式的视角下,统一给出这些算法的收敛性质,同时分别证明了遍历意义和点列意义下的迭代复杂性.2预备知识我们把凸优化的最优性条件以及线性约束凸优化和单调变分不等式的关系作为预备知识介绍,同时介绍遍历意义下近似解的定义.2.1子问题的求解交替方向法的迭代过程要求解的x和y子问题,往往是一个简单的凸优化.子问题的目标函数是两个凸函数的和,其中一个(例如,θ引理2.1设的充分必要条件是2.2变分正则下的线性约束凸优化如果一对(x则称(x利用(1.2)和引理2.1,上述优化问题的最优性条件是写成更紧凑的形式,鞍点(u的解,其中我们将变分不等式(2.12)的解集记为Ω称v为核心变量(essentialvariables).注意到,仿射算子F中的矩阵是斜对称(skewsymmetric)的,总有对线性约束的凸优化问题,我们一直主张在变分不等式框架下考虑问题,这会给收敛性分析带来极大的方便,此举也得到了中外学者们的积极响应2.3变分正则/变分式线性化乘子更新这一小节介绍一下o(1/k)收敛性和变分不等式遍历意义下的近似解的概念和意义.0(1/k)收敛性为说明序列的o(1/k)收敛性,变分不等式遍历意义下的近似解根据(2.12),如果就是变分不等式(2.12)的解.利用(因此,可以利用上式来刻画变分不等式(2.12)的近似解.具体说来,对任给的其中那么后面的两节我们分别讨论两种不同类型的线性化乘子交替方向法.前一节的算法以(1.4)为基础,后一节的算法以(1.5)为基础,根据大多数实际问题的要求,只假设ADMM中只有一个子问题需要线性化加正则化处理.并且,为了尽可能与(1.4)和(1.5)保持一致,我们仍然假设迭代从(y3线性化类专业问题的引理线性化乘子交替方向法-A(L-ADMM-A)以ADMM(1.4)为基础.求解问题(1.1),这个方法的k-步迭代以v产生新的迭代点w引理3.1设{w证明对线性化算法(3.1)的x-子问题(3.1a)中用引理2.1,有利用(3.1)中的乘子校正公式λ对线性化算法(3.1)的y-子问题(3.1b)中用引理2.1,有y利用乘子校正公式λ注意到乘子校正公式λ将(3.3),(3.4)和(3.5)加在一起,并利用(2.12)中的记号,我们得到对(3.6)式左端中的(w-w这就证明了该引理的结论(3.2).这个基本引理,是我们证明线性化方法(3.1)收敛性质的重要基础.3.1、u3000文书类型化和同型学证明这一节利用基本引理3.1证明算法产生的迭代序列{w引理3.2设{w其中证明对引理3.1中(3.2)的两端加上(y-y注意到,由矩阵D正定就能保证矩阵G正定.引理3.3设{w证明将(3.7)的w∈Ω设为任意的w根据最优性条件,上式右端中的利用Ax将这些结果代入(3.10)的右端,引理得证.引理3.4设{w证明首先,(3.4)式表示以k-1置换(3.12)中的k,就有将(3.12)和(3.13)中的任意的y∈y分别设成y由上式得到再对上式右端使用Cauchy-Schwarz不等式就得到(3.11).根据引理3.3和引理3.4我们可以直接证明下面的定理.定理3.1设{w其中G由(3.8)给出.证明由引理3.3和引理3.4,有利用上式,对任意的w这就证明了定理3.1的结论.3.2中矩阵的2和3.2+k-1的转化根据定理3.1中的(3.14),我们有§2.3中的说明告诉我们,只要再加上定理3.2设{w证明先将引理3.1中(3.2)的右端写成等价的把上式右端的最后一项β(Ax将此代入(3.17)的右端,并利用引理3.2中矩阵G(见(3.8))的记号,就有在上式中取w=w就有将(3.18)中的k置换成k-1,有在上式中取w=w将(3.20)和(3.22)相加,并利用(w在恒等式中置a=(v将(3.23)代入(3.24)的交叉项,我们得到注意到,根据G的结构(见(3.8)),(3.25)式的右端等于而非负,因此定理的结论得证.根据(3.15)和(3.16),我们有就像可微无约束凸优化问题min3.3线性化乘子交替方向法3.1线性化乘子交替方向法(3.1)经过t次迭代,由(3.33)定义的w其中是初始迭代点.这就说明算法具有遍历意义下的O(1/t)迭代复杂性.为了证明线性化ADMM-A遍历意义下的迭代复杂性,我们先利用引理3.1和两个初等恒等式证明下面的引理:引理3.5设{w证明首先,由引理3.1中的(3.2),我们有对(3.28)右端的第一部分,β(Ax中置就得到对(3.28)右端的第二和第三部分,在恒等式分别设和将(3.29),(3.30)和(3.31)代入(3.28)的右端,并利用(见(3.1c))就得到该引理的结论.对ADMM(1.4)和(3.1),相关的O(1/t)迭代复杂性在[13]通过引进辅助变量已经得到证明.这里我们不用任何辅助变量,直接用引理3.5加以证明.定理3.3设{w其中证明首先,由(3.27),对任意的k>0,上式可以改写成上面的不等式对k=0,1,2,…,t连加,我们得到因此就有由于θ(u)是凸函数并且代入(3.35)的左端,就完成了定理的证明.我们完整地证明了线性化乘子交替方向法(3.1)收敛性质的定理3.1,3.2和3.3.4算法1:v为核心变量线性化乘子交替方向法-B是以ADMM(1.5)为基础.求解问题(1.1),它的k-步迭代以v产生新的预测点产生新的迭代点,我们建议取α∈[1.2,1.8].这个算法中,仍然是v=(y,λ)为核心变量.由于D由(1.7)给出,类似于(1.8),求子问题(4.1c)中的其中4.1线性化交替方向法-d的迭代序列我们先根据凸优化的最优性条件,给出下面的基本引理.引理4.1为求解(1.1),设其中证明对线性化算法(4.1)的x-子问题(4.1a)用引理2.1,有利用(4.1)的对线性化算法(4.1)的y-子问题(4.1c)中用引理2.1,有利用(4.1)的注意到(4.1)本身,并表示成将(4.4),(4.5)和(4.6)加在一起,并利用(2.12)中的记号,我们得到对上式左端中的由矩阵D正定就能保证矩阵H正定.下面我们利用这个引理,分别证明线性化交替方向法-D产生的迭代序列{w4.2迭代序列{v定理4.1设{v证明将(4.3)的w∈Ω设为任意的因为利用(4.9),得到这就证明了定理的结论.4.3定理4.2证明为了证明用线性化乘子交替方向法(4.1)求解(1.1)所产生的序列的迭代复杂性,我们先利用引理4.1证明下面的引理.引理4.2设{w证明首先,对(4.3)的右端,利用对上式的右端利用恒等式并令对(4.12)式右端的最后一项,利用校正公式(4.2),就有将上式代入(4.12)的右端,然后再代入(4.11),定理的结论就得到证明.定理4.2设{w其中证明首先,由(4.10),对任意的k>0,有上式可以改写成上面的不等式对k=0,1,2,…,t连加,我们得到因此就有由于θ(u)是凸函数并且代入(4.16)的左端,就完成了定理的证明.4.4线性化乘子交替方法在定理4.1中,我们证明了交替方向法(4.1)所产生的序列满足在恒等式中置将(4.25)代入(4.26)的交叉项,我们得到上式右端因α∈(0,2)而非负,因此定理的结论得证.我们完整地证明了线性化乘子交替方法(4.1)收敛性质的定理4.1,4.2和4.3.5收敛性证明的简介交替方向法(ADMM)的应用范围越来越广,人们对ADMM的主要性质也愈感兴趣.这篇文章证明了线性化ADMM迭代复杂性方面主要收敛性质,所用的工具非常初等,证明也特别简单.虽然交替方向法有许多进展,变分不等式总是分析的有力工具[3],收