Sparse solutions to random standard quadratic optimization problems

Xin Chen, Jiming Peng, Shuzhong Zhang

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 this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.

Original languageEnglish (US)
Pages (from-to)273-293
Number of pages21
JournalMathematical Programming
Volume141
Issue number1-2
DOIs
StatePublished - Oct 1 2013

Keywords

  • Computational complexity
  • Order statistics
  • Probability analysis
  • Quadratic optimization
  • Relaxation
  • Semidefinite optimization

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Sparse solutions to random standard quadratic optimization problems'. Together they form a unique fingerprint.

  • Cite this