Operations Research and Fuzziology
Vol.07 No.03(2017), Article ID:21721,8 pages
10.12677/ORF.2017.73009

A Projection Algorithm for Solving Optimization Problems with Sparsity Constraints and Closed Convex Set Constraints

Jun Sun, Biao Qu

School of Management, Qufu Normal University, Rizhao Shandong

Received: Jul. 25th, 2017; accepted: Aug. 8th, 2017; published: Aug. 16th, 2017

ABSTRACT

In this paper, we mainly consider the optimization problem with sparsity constraints and closed convex set constraints. We design a gradient projection algorithm with Armijo step size rule, and prove that the sequence of the iteration generated by this algorithm can converge to an a-stationary point of the problem. Finally, a numerical example is given to demonstrate the effectiveness of the algorithm.

Keywords:Sparsity-Constrained, Closed Convex Set Constraints, Convergence, a-Stationary Point

求解带有稀疏约束和闭凸集约束的优化问题的投影算法

孙军,屈彪

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

收稿日期:2017年7月25日;录用日期:2017年8月8日;发布日期:2017年8月16日

摘 要

本文中,我们考虑了带有稀疏约束和闭凸集约束的优化问题的求解。设计了一种带有Armijo步长规则的梯度投影算法,证明了此算法产生的迭代点列可以收敛到问题的一个a-稳定点上。最后给出了数值例子验证了算法的有效性。

关键词 :稀疏约束,闭凸集约束,收敛,a-稳定点

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

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):凸可行问题的松弛投影算法及其应用研究。

文章引用

孙 军,屈 彪. 求解带有稀疏约束和闭凸集约束的优化问题的投影算法
A Projection Algorithm for Solving Optimization Problems with Sparsity Constraints and Closed Convex Set Constraints[J]. 运筹与模糊学, 2017, 07(03): 73-80. http://dx.doi.org/10.12677/ORF.2017.73009

参考文献 (References)

  1. 1. Negahban, S., Ravikumar, P., Wainwright, M. and Yu, B. (2012) A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers. Statistical Science, 27, 538-557. https://doi.org/10.1214/12-STS400

  2. 2. Agarwal, A., Negahban, S. and Wainwright, M. (2010) Fast Global Con-vergence Rates of Gradient Methods for High-Dimensional Statistical Recovery. Advances in Neural Information Pro-cessing Systems, 23, 37-45.

  3. 3. Blumensath, T. (2013) Compressed Sensing with Nonlinear Observations and Related Nonlinear Optimization Problems. IEEE Transactions on Information Theory, 59, 3466-3474. https://doi.org/10.1109/TIT.2013.2245716

  4. 4. Jalali, A., Johnson, C.C. and Ravikumar, P.K. (2011) On Learning Discrete Graphical Models Using Greedy Methods. Advances in Neural Information Processing Systems, 24, 1935-1943.

  5. 5. Tewari, A., Ravikumar, P.K. and Dhillon, I.S. (2011) Greedy Algorithms for Structurally Constrained High Dimensional Problems. Advances in Neural Information Processing Systems, 24, 882-890.

  6. 6. Yuan, X., Li, P. and Zhang, T. (2013) Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization. ICML, 127-135.

  7. 7. Bahmani, S., Raj, B. and Boufounos, P. (2013) Greedy Sparsity-Constrained Optimization. Journal of Machine Learning Research, 14, 807-841.

  8. 8. Candès, E.J. and Tao, T. (2005) Decoding by Linear Programming. IEEE Transactions on Information Theory, 51, 4203-4215. https://doi.org/10.1109/TIT.2005.858979

  9. 9. Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. https://doi.org/10.1109/TIT.2006.871582

  10. 10. Bunea, F. (2008) Honest Variable Selection in Linear and Logistic Regression Models via and Penalization. Electronic Journal of Statistics, 2, 1153-1194. https://doi.org/10.1214/08-EJS287

  11. 11. Beck, A. and Hallak, N. (2015) On the Minimization over Sparse Symmet-ric Sets: Projections, Optimality Conditions, and Algorithms. Mathematics of Operations Research, 41, 604-605.

  12. 12. Pan, L.L., Xiu, N.H. and Zhou, S.L. (2014) Gradient Support Projection Algorithm for Affine Feasibility Problem with Sparsity and Nonnegativity. Mathematics, 42, 1439-1444.

期刊菜单