1. 引言
本文考虑如下具有线性约束的可分凸优化问题:
(1)
其中
和
是凸函数(但不一定光滑),
和
是闭凸集。
众所周知,交替方向乘子法是求解(1)的有效方法,该方法最早由Gabay和Mercier,Glowinski [1] 以及Marrocco [2] 提出,该方法是一种求解具有可分离的凸优化问题的重要方法,由于其收敛速度快、收敛性能好,在求解可分离凸优化问题上具有简单、灵活、实用性强的特点,可以将大规模问题拆分成两个甚至多个小规模的子问题,随后交替求解各个小规模子问题,从而提高了求解的速率,其优势在于利用对偶上升算法的可分离性,后来被广泛研究与应用。
为了提高ADMM的适用性,一些学者提出了许多改进的ADMM方法。He等人在文献 [3] 中提出了不定临近线性化ADMM。Gao [4] 提出了如下一个带不定临近正则项的线性化ADMM。Fang [5] 将增广Lagrange函数中的惩罚项采用M-范数,M是一个是对称正定矩阵。将2-范数形式改进为M-范数形式,弱化了惩罚项的条件。因为2-范数形式的惩罚项是矩阵范数M-范数的一种特殊形式,所以M-范数的使用范围更广。
基于上述讨论,本文结合半正定临近项和基于M-范数的惩罚项,提出了一种求解可分凸优化问题(1)的基于M-范数惩罚项的带半正定临近项的线性化ADMM算法。新方法在y-子问题中引入了一个半正定临近项,进而将M-范数惩罚项转化为2范数惩罚项。该方法同时具备弱化的惩罚项的条件和半正定临近项的优势,具有更广的适用性和更高的求解效率。针对所提出的算法,本文基于变分不等式和最优化理论给出了严格的收敛性分析以及收敛速率分析,并通过数值实验验证了算法的有效性。
2. 一种基于M范数惩罚项的ADMM算法
假设
和
是合适的、闭的、凸函数。
本文提出的算法如下:
算法1. 一种基于M范数惩罚项的ADMM算法
输入:
计算:
若满足停止准则,则输出:
,其中
,M是一个正定矩阵,
是一个半正定矩阵。
3. 收敛性分析
引理3.1. 设序列
由算法1迭代产生,令
,
。
那么有
,
(2)
其中
。
引理3.2. 设序列
由算法1迭代产生,则
,
(3)
其中
。
证明:因为
,所以F是单调算子。
由(2)可得,(3)成立。
引理3.3. 设序列
由算法1迭代产生,其中
为变分不等式的解集,那么有
(4)
证明:
引理3.4. 设序列
由算法1迭代产生,那么有:
(5)
证明:对于算法1,由变分不等式可得:
两式相加可得:
,所以
。
由柯西不等式可得:
故(5)得证。
引理3.5. 设序列
由算法1迭代产生,那么有:
(6)
证明:
显然,(6)式成立。
定理3.1.对于任意的
,序列
是单调递减的。
证明:由引理3.5可得:
因为
,所以
。
故序列
是单调递减的。
定理3.2. 设序列
由算法1迭代产生,那么序列
收敛到
。
证明:因为
。
对上式求和可得:
。
因为G是正定的,所以
是正项级数。
由正项级数收敛的必要条件可知:
。
因为
。
所以
。
所以序列
是有界的并且至少存在一个聚点
,存在一个子列
收敛到
。
即
,其中
。
定理3.3.
是(1)的一个解。
证明:因为
,所以
和
。
由变分不等式可知:
令上式中
,可得:
,故
是(1)的解。
4. 数值实验
统计中的LASSO问题如下:
(7)
其中
。
使用算法1求解(7)得到
子问题:
。
并且y子问题的闭式解是:
。
子问题的解为:
,其中
。
本文通过数值实验比较了算法1和线性化DMM算法的迭代次数。
将每个算法的参数设置如下:
算法1:
。
Linearized ADMM:
,
。
停止准则是:
,其中
。
和
被设置为
和
。
对于给定的维度
,我们随机生成数据,如下所示:
二种算法的实验结果如表1所示:
Table 1. Comparison of the number of iterations between Algorithm 1 and Linearized ADMM
表1. 算法1和Linearized ADMM的迭代次数比较
实验结果表明,算法1的迭代次数少。因此,算法1是有可比较性的。
5. 结论
在本文中,我们提出了一种基于M范数罚项的具有半正定邻近项的广义线性化ADMM算法,对其进行了全局收敛性分析。最后,通过数值实验验证了算法的有效性。