The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the problem that can be solved in polynomial time.
Citation
unpublished
Article
View Polynomial solvability of variants of the trust-region subproblem