Efficient Solutions for the Large Scale Trust Region Subproblem (pdf file)

Henry Wolkowicz

Department of Combinatorics and Optimization University of Waterloo, Canada

Abstract: The Trust Region Subproblem (TRS) is:

This seemingly nonconvex problem is implicitly convex in that strong duality holds with its Lagrangian dual; and, it is equivalent to a linear semidefinite program. The TRS has a long history and has many applications in e.g., Tikhonov regularization (or ridge regression in statistics), and to a class of ``Trust Region'' algorithms for optimization. Efficient algorithms for moderate size TRS problems have been available since the early 80s. In particular, special techniques have been developed for the so called hard case problems. We show how to efficiently solve large scale sparse problems using a parametric eigenvalue algorithm. In addition, we use a shift and deflate approach and show that the we can exploit the structure of the problem to turn the hard case into a trivial case. We also look at the generalized TRS where the constraint is also a general (possibly non-convex) quadratic.