双重稀疏约束优化问题的一种贪婪单纯形算法

数学物理学报 ›› 2022, Vol. 42 ›› Issue (3): 920-933.

双重稀疏约束优化问题的一种贪婪单纯形算法

潘庭葳(),贺素香*()

^{武汉理工大学理学院数学系武汉 430070}

收稿日期:2021-07-05 出版日期:2022-06-26 发布日期:2022-05-09
通讯作者: 贺素香 E-mail:3305467528@qq.com;hesux@whut.edu.cn
作者简介:潘庭葳, E-mail: 3305467528@qq.com
基金资助:
国家自然科学基金(11871153)

The Greedy Simplex Algorithm for Double Sparsity Constrained Optimization Problems

Tingwei Pan(),Suxiang He*()

^{Department of Mathematics, School of Science, Wuhan University of Technology, Wuhan 430070}

Received:2021-07-05 Online:2022-06-26 Published:2022-05-09
Contact: Suxiang He E-mail:3305467528@qq.com;hesux@whut.edu.cn
Supported by:
the NSFC(11871153)

摘要/Abstract

摘要：

鉴于交替最小化方法在求解双重稀疏约束优化问题时需要计算目标函数梯度的Lipschitz常数和构建该问题的L-稳定点时需要借助于Lipschitz条件等方面的不足，该文提出了一种求解该问题的贪婪单纯形算法.刻画了双重稀疏约束优化问题的CW最优性条件.基于CW最优性条件，具体设计了该算法的迭代步骤，并在较弱的假设条件下，证明了由算法产生的迭代点列全局收敛到问题的CW最优解.

关键词: 双重稀疏约束优化问题, CW最优性条件, 贪婪单纯形算法, 全局收敛性

Abstract:

In view of the shortcomings of the alternating minimization method in which it needs to calculate the Lipschitz constant of the objective function gradient and the Lipschitz condition is needed to construct the L-stable point of the problem, this paper proposes a greedy simplex algorithm to solve the optimization problems with double sparse constraints. The CW optimality condition for double sparse constrained optimization problems is described. Based on the CW optimality condition, the iterative steps of the algorithm are designed, and the global convergence of the sequence of iterative points generated by the algorithm to the optimal solution of the problem is proved under the weaker assumptions.

Key words: Dual sparse constrained optimization problems, CW optimality condition, Greedy simplex algorithm, Global convergence

中图分类号:

O224

潘庭葳,贺素香. 双重稀疏约束优化问题的一种贪婪单纯形算法[J]. 数学物理学报, 2022, 42(3): 920-933.

Tingwei Pan,Suxiang He. The Greedy Simplex Algorithm for Double Sparsity Constrained Optimization Problems[J]. Acta mathematica scientia,Series A, 2022, 42(3): 920-933.

参考文献 17

1	Elad M , Figueiredo M A T , Ma Y . On the role of sparse, redundant representations in image processing. Proceedings of the IEEE, 2010, 98 (6): 972- 982 doi: 10.1109/JPROC.2009.2037655
2	Fletcher R , Matthews S P J . Stable modification of explicit LU factors for simplex updates. Mathematical Programming, 1984, 30 (3): 267- 284 doi: 10.1007/BF02591933
3	Wang R , Xiu N , Zhang C . Greedy projected gradient-newton method for sparse logistic regression. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31 (2): 527- 538
4	Goodfellow I , Bengio Y , Courville A . Machine learning basics. Deep Learning, 2016, 1, 98- 164
5	Jordan M I , Mitchell T M . Machine learning: trends, perspectives, and prospects. Science, 2015, 349 (6245): 255- 260 doi: 10.1126/science.aaa8415
6	Wright J , Ma Y , Mairal J , et al. Sparse representation for computer vision and pattern recognition. Proceedings of the IEEE, 2010, 98 (6): 1031- 1044 doi: 10.1109/JPROC.2010.2044470
7	Bienstock D . Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming, 1996, 74 (2): 121- 140 doi: 10.1007/BF02592208
8	Misra J , Schmitt W , Hwang D , et al. Interactive exploration of microarray gene expression patterns in a reduced dimensional space. Genome Research, 2002, 12 (7): 1112- 1120 doi: 10.1101/gr.225302
9	Zou H , Hastie T , Tibshirani R . Sparse principal component analysis. Journal of Computational and Graphical Statistics, 2006, 15 (2): 265- 286 doi: 10.1198/106186006X113430
10	Bertsimas D , Shioda R . Algorithm for cardinality-constrained quadratic optimization. Computational Optimization and Applications, 2009, 43 (1): 1- 22 doi: 10.1007/s10589-007-9126-9
11	Nikolova M . Description of the minimizers of least squares regularized with l₀-norm uniqueness of the global minimizer. SIAM Journal on Imaging Sciences, 2013, 6 (2): 904- 937 doi: 10.1137/11085476X
12	Pan L L , Xiu N H , Fan J . Optimality conditions for sparse nonlinear programming. Science China Mathematics, 2017, 60 (5): 759- 776 doi: 10.1007/s11425-016-9010-x
13	Beck A , Eldar Y C . Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM Journal on Optimization, 2013, 23 (3): 1480- 1509 doi: 10.1137/120869778
14	Beck A , Hallak N . On the minimization over sparse symmetric sets: projections, optimality conditions and algorithms. Mathematics of Operations Research, 2016, 41 (1): 196- 223 doi: 10.1287/moor.2015.0722
15	Beck A , Vaisbourd Y . The sparse principal component analysis problem: optimality conditions and algorithms. Journal of Optimization Theory and Applications, 2016, 170 (1): 119- 143 doi: 10.1007/s10957-016-0934-x
16	Beck A , Hallak N . Optimization problems involving group sparsity terms. Mathematical Programming, 2019, 178 (1): 39- 67
17	Gao H , Li Y , Zhang H . The analysis of alternating minimization method for double sparsity constrained optimization problem. Asia-Pacific Journal of Operational Research, 2020, 37 (4): 2- 13

[1]	刘鹏杰,吴彦强,邵枫,张艳,邵虎. 两个带重启方向的改进 HS 型共轭梯度法[J]. 数学物理学报, 2023, 43(2): 570-580.
[2]	袁功林,吴宇伦,PhamHongtruong. 基于非单调线搜索的HS-DY形共轭梯度方法及在图像恢复中的应用[J]. 数学物理学报, 2022, 42(2): 605-620.
[3]	马国栋. 强Wolfe线搜索下的修正PRP和HS共轭梯度法[J]. 数学物理学报, 2021, 41(3): 837-847.
[4]	马国栋. 一般约束极大极小优化问题一个强收敛的广义梯度投影算法[J]. 数学物理学报, 2020, 40(3): 641-649.
[5]	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法[J]. 数学物理学报, 2013, 33(1): 78-88.
[6]	周长银; 贺国平; 王永丽. 基于有效约束识别技术的一个SSLE算法及其收敛性分析[J]. 数学物理学报, 2007, 27(3): 535-540.
[7]	高自友, 任华玲, 贺国平. 无严格互补松驰条件的序列线性方程组新算法[J]. 数学物理学报, 2004, 24(3): 275-284.
[8]	施保昌, 陈珽, 祝世京. 多目标决策的中心方法之统一探讨[J]. 数学物理学报, 1997, 17(S1): 15-22.