Sparse solutions of linear complementarity problems

被引:26
作者
Chen, Xiaojun [1 ]
Xiang, Shuhuang [2 ]
机构
[1] Hong Kong Polytech Univ, Dept Appl Math, Hong Kong, Hong Kong, Peoples R China
[2] Cent S Univ, Dept Appl Math & Software, Changsha 410083, Hunan, Peoples R China
关键词
Linear complementarity problem; Sparse solution; Nonconvex optimization; Restricted isometry property;
D O I
10.1007/s10107-015-0950-x
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
This paper considers the characterization and computation of sparse solutions and least-p-norm solutions of the linear complementarity problem . We show that the number of non-zero entries of any least-p-norm solution of the is less than or equal to the rank of M for any arbitrary matrix M and any number , and there is such that all least-p-norm solutions for are sparse solutions. Moreover, we provide conditions on M such that a sparse solution can be found by solving convex minimization. Applications to the problem of portfolio selection within the Markowitz mean-variance framework are discussed.
引用
收藏
页码:539 / 556
页数:18
相关论文
共 22 条
[1]  
ADLER I., 2011, The linear complementarity problem, Lemke algorithm, perturbation, and the complexity class PPAD
[2]  
[Anonymous], 1959, Efficient Diversification of Investments
[3]   Sparse and stable Markowitz portfolios [J].
Brodie, Joshua ;
Daubechies, Ingrid ;
De Mol, Christine ;
Giannone, Domenico ;
Loris, Ignace .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2009, 106 (30) :12267-12272
[4]   From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images [J].
Bruckstein, Alfred M. ;
Donoho, David L. ;
Elad, Michael .
SIAM REVIEW, 2009, 51 (01) :34-81
[5]   Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].
Candès, EJ ;
Romberg, J ;
Tao, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509
[6]   Decoding by linear programming [J].
Candes, EJ ;
Tao, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (12) :4203-4215
[7]  
Cesarone F., 2009, 18 AFIR C FIN RISK C, P37
[8]  
Chen XJ, 2014, MATH PROGRAM, V143, P371, DOI 10.1007/s10107-012-0613-0
[9]   Newton iterations in implicit time-stepping scheme for differential linear complementarity systems [J].
Chen, Xiaojun ;
Xiang, Shuhuang .
MATHEMATICAL PROGRAMMING, 2013, 138 (1-2) :579-606
[10]   LOWER BOUND THEORY OF NONZERO ENTRIES IN SOLUTIONS OF l2-lp MINIMIZATION [J].
Chen, Xiaojun ;
Xu, Fengmin ;
Ye, Yinyu .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2010, 32 (05) :2832-2852