A Survey of the Trust Region Subproblem Within a Semidefinite Programming Framework

Charles Fortin
McGill University, Department of Mathematics and Statistics, Montr\'{e}al, Qu\'{e}bec, Canada, H3A 2T5.
Henry Wolkowicz
University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada, N2L 3G1.

The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it is used to determine the step in trust region algorithms for function minimization. Trust region algorithms are popular due to their strong convergence properties. However, one of the drawbacks has been the inability to exploit sparsity as well as the difficulty in dealing with the so-called hard case. These concerns have been addressed by recent advances in the theory and algorithmic development.

This talk provides an in depth study of TRS and its properties as well as a survey of recent advances. This is done using semidefinite programming (SDP) and the modern primal-dual approaches as a unifying framework. The SDP framework solves TRS efficiently and robustly; and it shows that TRS is always a well-posed problem, i.e. the optimal value and an optimum can be calculated to a given tolerance. This is contrary to statements in the literature which label TRS ill-posed or degenerate, if the so-called hard case holds. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights into handling the hard case.