The generalized trust region subproblem

Ting Kei Pong, Henry Wolkowicz

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)

Abstract

The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective, q0(x)→min, subject to an upper and lower bounded general quadratic constraint, ℓq1(x) ≤ u. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this 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 Fortin and Wolkowicz (Optim. Methods Softw. 19(1):41-67, 2004) and Rendl and Wolkowicz (Math. Program. 77(2, Ser. B):273-299, 1997) 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.
Original languageEnglish
Pages (from-to)273-322
Number of pages50
JournalComputational Optimization and Applications
Volume58
Issue number2
DOIs
Publication statusPublished - 1 Jun 2014
Externally publishedYes

Keywords

  • Indefinite quadratic
  • Large scale
  • Trust region subproblems

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this