























The standard quadratic optimization problem (StQP), i.e. the problem of minimizing a quadratic form $\bold x^TQ\bold x$ on the standard simplex $\{\bold x\ge\bold 0: \bold x^T\bold e=1\}$, is studied. The StQP arises in numerous applications, and it is known to be NP-hard. The first author, Peng and Zhang~\cite{int:Peng-StQP} showed that almost certainly the StQP with a large random matrix $Q=Q^T$, whose upper-triangular entries are i. i. concave-distributed, attains its minimum at a point with few positive components. In this paper we establish sparsity of the solution for a considerably broader class of the distributions, including those supported by $(-\infty,\infty)$, provided that the distribution tail is (super/sub)-exponentially narrow, and also for the matrices $Q=(M+M^T)/2$, when $M$ is not symmetric. {The likely support size in those cases is shown to be polylogarithmic in $n$, the problem dimension.} Following~\cite{int:Peng-StQP} and Chen and Peng ~\cite{ChenPeng2015}, the key ingredients are the first and second order optimality conditions, and the integral bound for the tail distribution of the solution support size. To make these results work for our goal, we obtain a series of estimates involving, in particular, the random interval partitions induced by the order statistics of the elements $Q_{i,j}$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。