The trust region subproblem and semidefinite programming*

Abstract

The trust region (TR) 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 determines the step in TR algorithms for function minimization. Trust region algorithms are popular for their strong convergence properties. However, a drawback 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. In particular, this has allowed Lanczos techniques to replace Cholesky factorizations. This article provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite programming (SDP) and the modern primal–dual approaches as a unifying framework. The SDP framework arises naturally and solves TRS efficiently. In addition, 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. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case, as well as numerical results on large test problems.