Optimization Online


The Generalized Trust Region Subproblem

Ting Kei Pong(tkpong***at***gmail.com )
Henry Wolkowicz(hwolkowicz***at***uwaterloo.ca)

Abstract: The \emph{interval bounded generalized trust region subproblem} (GTRS) consists in minimizing a general quadratic objective, $q_0(x) \rightarrow \min$, subject to an upper and lower bounded general quadratic constraint, $\ell \leq q_1(x) \leq u$. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this \emph{implicitly} convex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in \cite{FortinWolk:03,ReWo:94} can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper.

Keywords: Trust region subproblems; indefinite quadratic; large scale

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Optimization Software and Modeling Systems

Citation: Department of Combinatorics and Optimization, University of Waterloo. Nov/2012

Download: [PDF]

Entry Submitted: 11/17/2012
Entry Accepted: 11/17/2012
Entry Last Modified: 11/17/2012

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 Optimization Society