Separable standard quadratic optimization problems

A standard quadratic optimization problems (StQP) asks for the minimal value of a quadratic form over the standard simplex. StQPs form a central NP-hard class in quadratic optimization and have numerous practical applications. In this note we study the case of a separable objective function and propose an algorithm of worst-case complexity O(nlogn){mathcal{O}(nlog n)} . Some extensions to multi-StQPs and ℓ ¹−ball constrained problems are also addressed briefly.