New analysis on sparse solutions to random standard quadratic optimization problems and extensions

Xin Chen, Jiming Peng

Research output: Contribution to journalArticle

Abstract

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In a recent paper [Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1-2):273-293], Chen, et al. showed that with a high probability close to 1, StQPs with random data have sparse optimal solutions when the associated data matrix is randomly generated from a certain distribution such as uniform and exponential distributions. In this paper, we present a new analysis for random StQPs combining probability inequalities derived from the first-order and second-order optimality conditions. The new analysis allows us to significantly improve the probability bounds. More important, it allows us to handle normal distributions, which is left open in Chen et al. (2013). The existence of sparse approximate solutions to convex StQPs and extensions to other classes of QPs are discussed as well.

Original languageEnglish (US)
Pages (from-to)725-738
Number of pages14
JournalMathematics of Operations Research
Volume40
Issue number3
DOIs
StatePublished - Aug 1 2015

    Fingerprint

Keywords

  • Copositive definite matrix
  • Probability analysis
  • Random matrices
  • Sparse solutions
  • Standard quadratic optimization

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Cite this