ABSTRACT

In this paper, we mainly study the solution of sparsity-constrained split feasibility problem. Under some reasonable assumptions, we use IHT algorithm to get the stationary points of sparsity-constrained split feasibility problem and get a conclusion which plays an important role in local convergence analysis.

Keywords:Split Feasible Problem, Sparsity-Constrained, IHT Algorithm, Stationery

带稀疏约束的分裂可行问题的算法

畅含笑，孙军，屈彪

曲阜师范大学管理学院，山东 日照

收稿日期：2016年5月4日；录用日期：2016年5月23日；发布日期：2016年5月26日

摘 要

本文，我们主要研究带稀疏约束的分裂可行问题。在某些合理的假设下用IHT算法，得到了带稀疏约束的分裂可行问题的稳定点及给出在局部收敛性分析中起到了重要作用的结论。

关键词 :分裂可行问题，稀疏约束，IHT算法，稳定点

1. 引言

近几年来，带稀疏约束的最优化问题得到了学者们广泛的关注，这是因为它在信号处理、图像恢复等领域有着重要的应用 [1] - [4] 。不论是在理论、算法还是在应用方面，已经有了大量的研究。

大多数的理论研究都是关于带稀疏约束的一般连续可微函数，问题形式如下：

使得 (1.1)

其中，是一个连续可微的函数，是一个小于的整数。代表零范数(是向量中非零分量的个数)。目前，问题(1.1)已经引起了大量学者的研究，并提出了许多算法，但大多数的算法产生的点列都只是收敛到问题(1.1)的稳定点。在 [5] 中，作者引用了一种叫IHT的算法用来解问题(1.1)，并证明由该算法产生的点列的任意聚点都为问题(1.1)的L-稳定点。

关于问题(1.1)的特殊形式，其中，，也得到了广大学者的广泛关注 [6] - [8] 。

本文，我们主要研究的是带稀疏约束的分裂可行问题，分裂可行问题就是下述形式的问题，最早被Censor在 [9] 中提出：

找向量

, (1.2)

其中，分别为和中的非空闭凸集，为一个的实矩阵。

本文研究的是带稀疏约束的分裂可行问题，问题形式如下：

找向量

, , 使得 (1.3)

受到 [5] 的启发，我们通过求解下述最优问题得到(1.3)的近似解

(1.4)

注1：在本文中我们取。

2. 预备知识

2.1. 支撑映射

定义：对任意的非空闭集，称为到的投影。称由往稀疏集上的投影为支撑映射。

显然，往稀疏集上的投影的分量包括个绝对值最大的分量和个零。即：设为的指标集，且

,

则

。

因为非凸的，所以一般不是一个单点集。为使为单点集，我们这样定义：设代表的第大的分量，则有。记。当时，取，如果有多于一个的时，随机从中选一个；否则，取。即：

2.2. L-稳定点

定义：如果对任意的，，满足如下：

(2.1)

则称为(1.4)的稳定点.其中，为(1.4)的可行域，

。

2.3. 导集

定义：记集合的所有的聚点组成的集合为,称为的导集。

注2：导集的一些性质：1) 若为闭集，则；2) 记为的闭包，则。

引理2.1：对任意的，满足(2.1)当且仅当，且

引理2.2：(1.4)式中，目标函数的梯度函数在上是Lipschitz连续的，且Lipschitz常数为，即：

证明：对任意的，有

即：。

证毕。

引理2.3 (the descent lemma [10] )：假设是一个连续可微的函数，且其梯度函数是Lipschtz连续的，并记其Lipschtz常数为，则对任意，有

其中。

引理2.4：对于任意的，则对任意的，满足于

(2.2)

则有。

其中，，。

证明：我们知(2.2)式可以写成如下形式：

(2.3)

又因为。

又关于为常数，故(2.3)式等价于。

即：

(2.4)

由引理2.4可得。

即：

(2.5)

联立(2.4)，(2.5)可得。

证毕。

定理2.1：对于任意的，设为(1.4)式的最优解，则

(1)是一个-稳定点。

(2)为一个单点集。

证明：我们同时证明(a)和(b)，假设存在向量，且有

在引理2.4中取，有

这与为最优解矛盾。

证毕。

3. IHT算法

在本文我们引用求解带稀疏约束的一般连续可微函数的IHT算法来求解带稀疏约束的分裂可行问题。

算法过程如下：

步骤1：任取；

步骤2：；

步骤3：若有，则停止；否则令，转步骤2。

其中，，稀疏集。

引理3.1：设为由IHT算法产生的点列，则

(1)；

(2)是一个不增数列；

(3)。

证明：在引理2.4中，取，从而由(1)成立。又由(1)可直接得出(2)，(3)成立。

定理3.1：设为由IHT算法产生的点列，则的任一聚点都为L-稳定点。

证明：该证明与 [5] 中定理3.1类似，证明过程如下：

设为的任意聚点，则存在子列收敛到。由引理3.1的(1)可得：

(2.6)

因为为正数列，结合引理3.1中(2)，可以得出和收敛到同一极限。从而有时，，联立(2.6)式可以得出：

当时，。

又

。

取。因为和都收敛到，所以存在使得当时，有：

从而对所有的：

取可得。

再取。如果存在有限个且。则

取极限可得。特别地，。另一方面，如果存在，使得对所有的都有，则

再取，利用函数的连续性可得：

从而结论得证。

证毕。

引理3.2：设为由IHT算法产生的点列，且为包含的所有聚点的集合，，则①；或②，其中为的导集。

证明：假设①不成立，则证②成立。因为为闭集，所以我们只需要证明。

设，故存在的子列使得：

(2.7)

因为①不成立，故存在和的一个邻域，记作使得：

(2.8)

取，由引理3.1的(3)和(2.7)式知，使得：

(2.9)

(2.10)

不失一般性，对于我们可以假设对，使得且有对于，由(2.8)式和(2.9)式可得，，所以，存在使得：

(2.11)

(2.12)

由(2.10)和(2.11)式可得，当时有：

即点列，故存在聚点，设为，则，由(2.12)式可得，由的任意性，得。

证毕。

定理3.2：设为IHT算法产生的点列，若为(1.4)的严格局部最小解，则有。

证明：由于为的一个聚点，故(2.7)式成立，又，结合引理3.2的(2)知，由IHT算法产生的点列满足，所以

即：

(2.13)

由引理3.1的(3)知。

由引理3.2知，若，则对于任意的，存在，都有，而由(2.13)式知对所有成立。故与为(1.4)的严格局部最小解矛盾。

证毕。

4. 总结

本文在带稀疏约束的一般连续可微函数的已有结论的基础上，对带稀疏约束的分裂可行问题进行求解分析。由引理3.2我们可以得出，由IHT算法产生的点列，要么满足，此时，有收敛到(1.4)的一个-稳定点；要么有 (包含的所有聚点)。并且我们给出了在局部收敛性分析中起到了重要作用的结论。

文章引用

畅含笑,孙军,屈彪. 带稀疏约束的分裂可行问题的算法
The Solution of Sparsity-Constrained Split Feasibility Problem[J]. 应用数学进展, 2016, 05(02): 269-275. http://dx.doi.org/10.12677/AAM.2016.52034

参考文献 (References)