On sparsity of the solution to a random quadratic optimization problem

• 成果类型: Article
• 署名作者: Chen, Xin; Pittel, Boris
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University System of Ohio; Ohio State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01456-2
• 发表日期: 2021
• 页码: 309-336
• 关键词: algorithm

摘要

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), Q(i, j), (i <= j) being independent and identically concave-distributed, attains its minimum at a point x with support size vertical bar{j : x(j) > 0}vertical bar bounded in probability. Later Chen and Peng proved that for Q = ( M + M-T)/2, with M-i,M- j i.i.d. normal, the likely support size is at most 2. In this paper we show that the likely support size is polylogarithmic 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 -infinity, provided that the distribution of Q(i,) j, (i <= j) (of M-i,M- j, if Q = ( M + M-T)/2 resp.) has a (super/sub) exponentially narrow left tail.