DIMACS TR: 93-19

Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations

Authors: Ronald J. Stern and Henry Wolkowicz


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 constraint. Characterizations of optimality are presented, which have no gap between necessity and sufficiency. Conditions for the existence of solutions are given in terms of the definiteness of a matrix pencil. A simple dual program is introduced which involves the maximization of a strictly concave function on an interval. This dual program simplifies the theory and algorithms for trust region subproblems. It also illustrates that the trust region subproblems are implicit convex programming problems, and thus explains why they are so tractable.

The duality theory also provides connections to eigenvalue perturbation theory. Trust region subproblems with zero linear term in the objective function correspond to eigenvalue problems, and adding a linear term in the objective function is seen to correspond to a perturbed eigenvalue problem. Some eigenvalue interlacing results are presented. Henry Wolkowicz; Department of Combinatorics and Optimization; Faculty of Math.; Univ. of Waterloo; Waterloo, Ont., Canada N2L 3G1 (on sabbatical leave at Princeton University, Dept. of Civil Engineering and Operations Research, Princeton, NJ 08544, 609-258-3839) {hwolkowicz@orion.uwaterloo.ca; na.wolkowicz@na-net.ornl.gov}

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-19.ps

DIMACS Home Page