### 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 language | English (US) |
---|---|

Pages (from-to) | 273-293 |

Number of pages | 21 |

Journal | Mathematical Programming |

Volume | 141 |

Issue number | 1-2 |

DOIs | |

State | Published - 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

Chen, X., Peng, J., & Zhang, S. (2013). Sparse solutions to random standard quadratic optimization problems.

*Mathematical Programming*,*141*(1-2), 273-293. https://doi.org/10.1007/s10107-012-0519-x