The trust region subproblem with non-intersecting linear constraints (Q2515041)

The authors consider an extended trust region subproblem (eTRS) in which the trust region is formed by the intersection of the unit ball and the solution set of \(m\) linear inequality constraints, and they study the relation of the optimal value of the eTRS to that of a particular convex relaxation of this problem which is solvable in polynomial time. As was shown earlier, both optimal values are identical for \(m\leq 2\) when the linear constraints are parallel and the optimal value of the relaxation problem is strictly smaller than that of the eTRS for \(m\geq 2\) when at least two of the linear constraints intersect within the unit ball, i.e., are satisfied with equality for some feasible point of the eTRS. In this paper it is proved that in fact for each \(m\) there is no gap between both optimal values as long as the \(m\) linear constraints do not intersect or, more generally, as long as they do not intersect in the interior of the unit ball.