Optimization Online


The Trust Region Subproblem and Semidefinite Programming

Charles Fortin (fortin***at***math.mcgill.ca)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

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 determines the step in trust region 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. This paper 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 {\em large} test problems.

Keywords: Trust Regions, Semidefinite programming, Duality, Unconstrained

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada Research Report CORR 2002-22

Download: [Postscript][PDF]

Entry Submitted: 09/07/2002
Entry Accepted: 09/08/2002
Entry Last Modified: 03/09/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society