A half thresholding projection algorithm for sparse solutions of LCPs

被引：3

作者：

Shang, Meijuan ^{[1
,2
]}

Zhang, Chao ^{[1
]}

Peng, Dingtao ^{[3
]}

Zhou, Shenglong ^{[4
]}

机构：

[1] Beijing Jiaotong Univ, Dept Appl Math, Beijing 100044, Peoples R China

[2] Shijiazhuang Univ, Dept Math, Shijiazhuang 050035, Peoples R China

[3] Guizhou Univ, Coll Sci, Guiyang 550025, Peoples R China

[4] Univ Southampton, Sch Math, Southampton SO17 1BJ, Hants, England

来源：

OPTIMIZATION LETTERS | 2015年 / 9卷 / 06期

基金：

中国国家自然科学基金;

关键词：

Linear complementarity problems; Sparse solutions; l(1/2) regularized minimization; Half thresholding projection algorithm; Convergence;

D O I：

10.1007/s11590-014-0834-7

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we aim to find sparse solutions of the linear complementarity problems (LCPs), which has many applications such as bimatrix games and portfolio selection. Mathematically, the underlying model is NP-hard in general. Thus, an regularized projection minimization model is proposed for relaxation. A half thresholding projection (HTP) algorithm is then designed for this regularization model, and the convergence of HTP algorithm is studied. Numerical results demonstrate that the HTP algorithm can effectively solve this regularization model and output very sparse solutions of LCPs with high quality.

引用

页码：1231 / 1245

页数：15

共 21 条

[1] [Anonymous], 1996, MATH PROGRAMS EQUILI, DOI DOI 10.1017/CBO9780511983658
[2] Highly robust error correction by convex programming
Candes, Emmanuel J.
Randall, Paige A.
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (07) : 2829 - 2840
[3] Stable signal recovery from incomplete and inaccurate measurements
Candes, Emmanuel J.
Romberg, Justin K.
Tao, Terence
[J]. COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) : 1207 - 1223
[4] Exact Matrix Completion via Convex Optimization
Candes, Emmanuel J.
Recht, Benjamin
[J]. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2009, 9 (06) : 717 - 772
[5] Cottle R.W., 1992, The Linear Complementarity Problem
[6] Compressed sensing
Donoho, DL
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) : 1289 - 1306
[7] Facchinei F., 2003, SPRINGER SERIES OPER, VII
[8] FACCHINEI F, 2003, SPRINGER SERIES OPER, V1
[9] Ferris M.C., 2001, Complementarity: Applications, Algorithms and Extensions
[10] Some feasibility issues in mathematical programs with equilibrium constraints
Fukushima, M
Pang, JS
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) : 673 - 681

← 1 2 3 →