Henry Wolkowicz
Department of Combinatorics and Optimization
University of Waterloo, Canada
Abstract:
The Trust Region Subproblem (TRS) is:
the minimization of a quadratic (possibly non-convex) function subject to a
norm constraint.
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.