1. 引言
我们主要研究带有稀疏约束和闭凸集约束的优化问题。随着实际问题的发展需要,稀疏优化问题的约束条件进一步加强,除了对于自变量的稀疏约束外,还有一些其他的约束条件,如在像素强度,频率计数等中要求。因此,对于稀疏约束和闭凸集约束最优化问题的研究还是有很大的理论意义和实际价值。
本文所研究的问题形式如下:
, (1)
这里是一个闭凸的对称集合。
用表示所有最多有s个非零元素的向量全体:
,
这里,,表示范数,称集合为稀疏集合。
对于稀疏约束优化问题,已经有了一些研究,Negahban [1] 在凸优化问题中提出了一种严格强凸性(RSC)性质并且证明了这是问题唯一解存在的充分条件。Agarwal [2] 改进了RSC并且定义了严格强光滑性(RSS)来保证一阶方法的线性收敛性。后来,陆续有些学者 [3] [4] [5] [6] 对RSC和RSS性质进行了改进来保证唯一解的存在性。Bahmani [7] 对于二阶连续可微的目标函数提出了严格稳定Hessian性(SRH)性质,对于非光滑的目标函数提出了严格稳定线性(SRL)性质,并且证明了这些是稀疏约束优化问题可以得到唯一解的充分条件。以上的所有这些性质都可以看作Candes和Tao [8] [9] 在压缩传感中提出的严格等距性(RIP)的扩展或者松弛。这里RIP保证了压缩传感中带有线性目标函数的优化问题有唯一解。2008年,Bunea [10] 中提出了凸松弛算法,在一些适当的假设下,能够通过凸松弛的方法来解决稀疏约束优化问题,准确的来说,就是用范数来近似范数。
Amir Beck和Nadav Hallak [11] 在2014年提出了一些稀疏约束和闭凸集约束优化问题的一些最优性条件,并给出了收敛到不同稳定点的一些算法。Pan和Xiu [12] 中对于的情况下,提出了支撑投影算法(GSP)。
本文具体组织如下,在第2部分先回顾了一些预备知识,给出了稀疏约束和闭凸集约束优化问题解存在的必要条件,然后在第3部分设计了一种投影算法,证明了算法可以收敛到问题(1)的一个a-稳定点。最后,第4部分给出了数值例子验证了我们算法的可行性和有效性。
2. 预备知识
假设 1是有下界的。即存在,使得对于所有的,都有。
假设2是二阶连续可微的且其梯度是Lipschitz连续的,即:
对于一个稀疏向量,如果,则称向量有完全支撑集。对于一个指标集合,对于,且,则称是的一个超级支撑集。
首先,我们将所有的排列记为。对于一个给定的向量和一个排列,向量定义为:
即向量是根据的一个重新排列。如,是一个排列:,那么。
对于给定的指标集,称
为在下的限制。这里表示单位矩阵在指标集下所对应的列所组成的子矩阵。定义是向量在标集下的一个子向量。
举个例子:,则。
定义1 [11] (排序排列)对于向量,如果一个排列使得向量的元素为一个非增序列,那么称这个排列为排序排列。向量的所有排序排列记为。
定义2 [11] (类型1的对称集合)设集合,如果对于任意的向量和,我们有,则称为类型1的对称集合。
定义3 [11] (类型2的对称集合)设为类型1的对称集合,如果对于,和,向量仍属于集合,那么称为类型2对称的集合。
定义4 [11] (非负集合)对于,如果对于任意的,都有,则称集合为非负集合。
定义5 [11] 定义下面的函数:
则称此函数为对称函数。
给定一个闭凸集和一个向量,记在上的投影为:
.
引理1 [11] 设,假设,则对于的任意超级支撑集,都有:
定义6 [11] (基本可行点)如果一个向量,对于的任意一个超级支撑集和,都有:
则称向量为问题(1)的一个基本可行点。
定理1 [11] 如果是问题(1)的一个最优解,那么是一个基本可行点。
定义7 [11] (a-稳定点)取,对于,如果有
我们称为问题(1)的一个a-稳定点。
引理2 [11] 若是问题(1)的一个a-稳定点,那么是一个基本可行点。
定理2 [11] 若是问题(1)一个最优解,假设2.1成立,对于,是一个a-稳定点。
引理3 [11] (下降性引理)假设2成立,,有,其中
(2)
3. 算法及收敛性分析
下面给出我们的算法:
算法1:
步骤0. 初始点,,,,,令。
步骤1. 计算,并且是使得
(3)
成立的最小正整数。这里。
步骤2. 若,则停止,否则令,转步骤1。
引理4对于任意的,则对任意满足下式的,,
有:
(4)
证明:因为,所以
(5)
又
(6)
又关于为常数,故(6)式等价于,即。
通过引理3,我们有
,
即
。
有
引理5假设是由算法产生的迭代点列,则,且
证明:根据步骤1,我们有,根据引理3和引理4,由简单计算,我们可以得出
并且根据(3),我们有
。 (7)
引理得证。
定理3设是由算法1产生的点列,则
1.;
2.的任何一个聚点都是a-稳定点。
证明:1.根据算法,有,可得是单调非增的,故是收敛的。所以有:
所以。根据引理5,知是有界的。所以。
2.假设是点列的一个聚点。则存在一个子列收敛到。通过结论1,可知当时,。又因为
故对于任意的,我们有
。 (8)
根据引理5,知有界,所以存在收敛子列,不妨假设当,有。
对不等式(8)两边同时取极限得
又因为和都是闭集,,所以,可以得出
所以是问题(1)的一个a-稳定点。
注:对于往一般稀疏集合和闭凸集的交上投影比较难以获得,但是对于我们前面提到的类型1或者类型2的对称集合上的投影现在已经可以得到,见文献 [11] 。
4. 数值实验
在本节中,我们给出数值例子验证了我们算法的有效性。所有的程序是在LENONVE ideapad,Windows 10 Inter(R) Core(TM)i5-6200U CPU @2.30 GHz 2.40 GHz and 4 GB内存的电脑上运行。
我们考虑下面这个例子:
在试验中,取,,。
在表1中,我们取,,取。在表中,表示迭代步数,CPU time表示迭代时间。
在表2中,我们取,,,表示迭代步数,CPU time表示迭代时间。
我们从上面两个表格中可以看到,对于矩阵的不同维数和不同的稀疏度,我们的算法都有不错的效果。
在表3中,我们取,,,,表示初始点,表示迭代步数,CPU time表示迭代时间。
从表3中,我们可以得出,从不同的初始点开始,都有较快的收敛速度。
Table 1. Numerical result
表1. 数值结果
Table 2. Numerical result
表2. 数值结果
Table 3. Numerical result
表3. 数值结果
5. 总结
本文主要研究了带有稀疏约束和闭凸集约束的优化问题。我们对文献 [12] 所提出的支撑投影算法(GSP)进行了推广,来求解本文所研究的优化问题。我们证明了由此算法产生的点列可以收敛到问题的一个a-稳定点,并且用数值例子说明了算法的有效性。
基金项目
国家自然科学基金(11271226):凸可行问题的松弛投影算法及其应用研究。
参考文献