Sparse solutions to random standard quadratic optimization problems |
| |
Authors: | Xin Chen Jiming Peng Shuzhong Zhang |
| |
Institution: | 1. Department of Industrial and Enterprise System Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA 2. Industrial and Systems Engineering Program, University of Minnesota, Minneapolis, MN, 55455, USA
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|