abstract:
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.