运筹与模糊学  >> Vol. 7 No. 3 (August 2017)

求解带有稀疏约束和闭凸集约束的优化问题的投影算法
A Projection Algorithm for Solving Optimization Problems with Sparsity Constraints and Closed Convex Set Constraints

DOI: 10.12677/ORF.2017.73009, PDF, HTML, XML, 下载: 953  浏览: 2,681  国家自然科学基金支持

作者: 孙 军*, 屈 彪:曲阜师范大学管理学院,山东 日照

关键词: 稀疏约束闭凸集约束收敛α-稳定点Sparsity-Constrained Closed Convex Set Constraints Convergenceα-Stationary Point

摘要: 本文中,我们考虑了带有稀疏约束和闭凸集约束的优化问题的求解。设计了一种带有Armijo步长规则的梯度投影算法,证明了此算法产生的迭代点列可以收敛到问题的一个α-稳定点上。最后给出了数值例子验证了算法的有效性。
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 α-stationary point of the problem. Finally, a numerical example is given to demonstrate the effec-tiveness of the algorithm.

文章引用: 孙军, 屈彪. 求解带有稀疏约束和闭凸集约束的优化问题的投影算法[J]. 运筹与模糊学, 2017, 7(3): 73-80. https://doi.org/10.12677/ORF.2017.73009

参考文献

[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] 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] 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] 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] 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] Yuan, X., Li, P. and Zhang, T. (2013) Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization. ICML, 127-135.
[7] Bahmani, S., Raj, B. and Boufounos, P. (2013) Greedy Sparsity-Constrained Optimization. Journal of Machine Learning Research, 14, 807-841.
[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] Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306.
https://doi.org/10.1109/TIT.2006.871582
[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] 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] 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.