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

Abstract

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

CLC Number:

O224

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.

Trendmd

References 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]	Pengjie Liu,Yanqiang Wu,Feng Shao,Yan Zhang,Hu Shao. Two Extended HS-type Conjugate Gradient Methods with Restart Directions [J]. Acta mathematica scientia,Series A, 2023, 43(2): 570-580.
[2]	Ning Zhang,Jinkui Liu. Spectral LS-type Projection Algorithm for Solving Nonlinear Pseudo-Monotone Equations [J]. Acta mathematica scientia,Series A, 2022, 42(6): 1886-1897.
[3]	Gonglin Yuan,Yulun Wu,Hongtruong Pham. A Modified HS-DY-Type Method with Nonmonotone Line Search for Image Restoration and Unconstrained Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(2): 605-620.
[4]	Zhibin Zhu,Yuanhang Geng. A Modified Three-Term WYL Conjugate Gradient Method [J]. Acta mathematica scientia,Series A, 2021, 41(6): 1871-1879.
[5]	Guodong Ma. Improved PRP and HS Conjugate Gradient Methods with the Strong Wolfe Line Search [J]. Acta mathematica scientia,Series A, 2021, 41(3): 837-847.
[6]	Xiaoni Chi,Rong Zeng,Sanyang Liu,Zhibin Zhu. A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems [J]. Acta mathematica scientia,Series A, 2021, 41(2): 507-522.
[7]	Guodong Ma. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints [J]. Acta mathematica scientia,Series A, 2020, 40(3): 641-649.
[8]	HU Chao-Ming, WAN Zhong, WANG Xu. A New Nonmonotone Spectral Conjugate Gradient Algorithm [J]. Acta mathematica scientia,Series A, 2013, 33(1): 78-88.
[9]	TANG Jing-Yong, HE Guo-Ping. A One-step Smoothing Newton Method for Second-order Cone Programming [J]. Acta mathematica scientia,Series A, 2012, 32(4): 768-778.
[10]	Zhang Li; Zhou Weijun. On the Global Convergence of the Hager-Zhang Conjugate Gradient Method with Armijo Line Search [J]. Acta mathematica scientia,Series A, 2008, 28(5): 840-845.
[11]	Tong Xiaojiao ;He Wei. Lagrangian Globalization Projection Methods for Nonlinear Constrained Equations [J]. Acta mathematica scientia,Series A, 2008, 28(1): 96-108.
[12]	Zhou Changyin; He Guoping; Wang Yongli. An Active Constraints Identification Technique-based SSLE Algorithm and Its Convergence Analysis [J]. Acta mathematica scientia,Series A, 2007, 27(3): 535-540.
[13]	GAO Zi-You, Ren Hua-Ling, HE Guo-Ping. A New Sequential Systems of Linear Equations Algorithm Without Strict Complementary Slackness [J]. Acta mathematica scientia,Series A, 2004, 24(3): 275-284.
[14]	Shi Baochang, Chen Ting, Zhu Shijing. A Unified Approach to Method of Centers for Multiobjective Decision Making [J]. Acta mathematica scientia,Series A, 1997, 17(S1): 15-22.

The Greedy Simplex Algorithm for Double Sparsity Constrained Optimization Problems

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

References 17

Related Articles 14

Metrics

Comments

Recommended 10