科研之友
微信
新浪微博
Facebook
分享链接
摘要
Recent research has focused on the complexity of extensions of the classical trust-region subproblem, which addresses the minimization of a quadratic function over a unit ball in R-n, a problem of importance in many applications. Even though the trust-region subproblem can be considered well-solved (from the perspective of both theory and implementation), even minor extensions are NP-hard. The Celis-Dennis-Tapia (CDT) problem is an extension of the trust-region subproblem, involving the minimization of a quadratic function over the intersection of two ellipsoids in Rn. In this paper we show how to adapt a construction of Barvinok so as to obtain a polynomial-time algorithm for quadratic programming with a fixed number of quadratic constraints (one of which is ellipsoidal) under the bit model of computing.
- 出版日期2016
