### Abstract

The standard quadratic optimization problem (StQP), i.e. the problem of minimizing a quadratic form x^{T}Qx on the standard simplex { x≥ 0: x^{T}e= 1 } , is studied. The StQP arises in numerous applications, and it is known to be NP-hard. Chen, Peng and Zhang showed that almost certainly the StQP with a large random matrix Q= Q^{T}, Qi,j,(i≤j) being independent and identically concave-distributed, attains its minimum at a point x with support size | { j: x_{j}> 0 } | bounded in probability. Later Chen and Peng proved that for Q= (M+ M^{T}) / 2 , with M_{i} _{,} _{j} i.i.d. normal, the likely support size is at most 2. In this paper we show that the likely support size is poly-logarithmic in n, the problem size, for a considerably broader class of the distributions. Unlike the cited papers, the mild constraints are put on the asymptotic behavior of the distribution at a single left endpoint of its support, rather than on the distribution’s shape elsewhere. It also covers the distributions with the left endpoint - ∞, provided that the distribution of Qi,j,(i≤j) (of M_{i} _{,} _{j}, if Q= (M+ M^{T}) / 2 resp.) has a (super/sub) exponentially narrow left tail.

Original language | English (US) |
---|---|

Journal | Mathematical Programming |

DOIs | |

State | Accepted/In press - Jan 1 2019 |

### Keywords

- Probability analysis
- Random matrices
- Sparse solutions
- Standard quadratic programming

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'On sparsity of the solution to a random quadratic optimization problem'. Together they form a unique fingerprint.

## Cite this

*Mathematical Programming*. https://doi.org/10.1007/s10107-019-01456-2