Sparse solutions to random standard quadratic optimization problems
Sparse solutions to random standard quadratic optimization problems
复制标题
DOI：
10.1007/s10107-012-0519-x
复制
发表时间：
2013-10-01
影响因子：
2.7
通讯作者：
Zhang, Shuzhong
中科院分区：
文献类型：
--
作者：
Chen, Xin;Peng, Jiming;Zhang, Shuzhong
标准二次优化问题（StQP）是指在标准单纯形上最小化二次型的问题。这样的问题出现在许多应用中，并且已知是NP困难的。在本文中，我们专注于一个特殊的情况下，StQP的数据矩阵Q的所有元素是独立同分布，并遵循一定的分布，如均匀或指数分布。我们表明，这样一个随机StQP具有k个非零元素的全局最优解的概率在k中呈指数衰减。我们的理论发现的数值评估进行了讨论。
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.