INDEFINITE TRUST REGION SUBPROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS

This paper extends the theory of trust region subproblems in two ways: (i) it allows indefinite inner products in the quadratic constraint, and (ii) it uses a two-sided (upper and lower bound) quadratic constra int. Characterizations of optimality are presented that have no gap be tween necessity and sufficiency. Conditions for the existence of solut ions are given in terms of the definiteness of a matrix pencil. A simp le dual program is introduced that involves the maximization of a stri ctly concave function on an interval. This dual program simplifies the theory and algorithms for trust region subproblems. It also illustrat es that the trust region subproblems are implicit convex programming p roblems, and thus explains why they are so tractable. The duality theo ry also provides connections to eigenvalue perturbation theory. Trust region subproblems with zero linear term in the objective function cor respond to eigenvalue problems, and adding a linear term in the object ive function is seen to correspond to a perturbed eigenvalue problem. Some eigenvalue interlacing results are presented.