Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem

The trust region subproblem has at most one local nonglobal minimizer. In characterizing this local solution, there is a clear gap between necessary and sufficient conditions. In this paper, we surprisingly show that the sufficient second-order optimality condition remains necessary. As an application, we improve the state-of-the-art algorithm for computing a candidate of the local nonglobal minimizer and then show that finding the local nonglobal minimizer or proving the nonexistence can be done in polynomial time.