Journal
OPTIMIZATION METHODS & SOFTWARE
Volume 19, Issue 1, Pages 41-67Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/10556780410001647186
Keywords
trust regions; semidefinite programming; duality; unconstrained minimization
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available