DIMACS TR: 93-19
Indefinite Trust Region Subproblems and Nonsymmetric
Eigenvalue Perturbations
Authors: Ronald J. Stern and Henry Wolkowicz
ABSTRACT
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