The generalized trust region subproblem

Ting Pong () and Henry Wolkowicz ()

Computational Optimization and Applications, 2014, vol. 58, issue 2, 273-322

Abstract: The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective, q 0 (x)→min, subject to an upper and lower bounded general quadratic constraint, ℓ≤q 1 (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. Copyright Springer Science+Business Media New York 2014

Keywords: Trust region subproblems; Indefinite quadratic; Large scale (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9635-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:58:y:2014:i:2:p:273-322

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9635-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().