Sparse solutions of linear complementarity problems

Xiaojun Chen, Shuhuang Xiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

This paper considers the characterization and computation of sparse solutions and least-p-norm (0 < p< 1) solutions of the linear complementarity problem LCP (q, M). We show that the number of non-zero entries of any least-p-norm solution of the LCP (q, M) is less than or equal to the rank of M for any arbitrary matrix M and any number p∈ (0 , 1) , and there is p¯ ∈ (0 , 1) such that all least-p-norm solutions for p∈ (0 , p¯) 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.
Original languageEnglish
Pages (from-to)539-556
Number of pages18
JournalMathematical Programming
Volume159
Issue number1-2
DOIs
Publication statusPublished - 1 Sep 2016

Keywords

  • Linear complementarity problem
  • Nonconvex optimization
  • Restricted isometry property
  • Sparse solution

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this