The generalized trust region subproblem: solution complexity and convex hull results
- PDF / 690,764 Bytes
- 42 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 170 Views
Series A
The generalized trust region subproblem: solution complexity and convex hull results Alex L. Wang1
· Fatma Kılınç-Karzan1
Received: 18 July 2019 / Accepted: 1 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We consider the generalized trust region subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building relaxations for nonconvex quadratic programs. Moreover, this result allows us to reformulate the GTRS as the minimization of two convex quadratic functions in the original space. Our next set of contributions is algorithmic: we present an algorithm for solving the GTRS up to an additive error based on this reformulation. We carefully handle numerical issues that arise from inexact generalized eigenvalue and eigenvector computations and establish explicit running time guarantees for these algorithms. Notably, our algorithms run in linear (in the size of the input) time. Furthermore, our algorithm for computing an -optimal solution has a slightly-improved running time dependence on over the state-of-the-art algorithm. Our analysis shows that the dominant cost in solving the GTRS lies in solving a generalized eigenvalue problem—establishing a natural connection between these problems. Finally, generalizations of our convex hull results allow us to apply our algorithms and their theoretical guarantees directly to equality-, interval-, and hollow-constrained variants of the GTRS. This gives the first linear-time algorithm in the literature for these variants of the GTRS. Keywords Generalized trust region subproblem · Convex hull · Linear time complexity
This research is supported in part by National Science Foundation Grant CMMI 1454548.
B
Fatma Kılınç-Karzan [email protected] Alex L. Wang [email protected]
1
Carnegie Mellon University, Pittsburgh, PA 15213, USA
123
A. L. Wang, F. Kılınç-Karzan
Mathematics Subject Classification 90C20 · 90C22 · 90C25 · 90C26 · 65F15
1 Introduction In this paper, we study the Generalized Trust-Region Subproblem (GTRS), which is defined as Opt := infn {q0 (x) : q1 (x) ≤ 0} , x∈R
(1)
where q0 : Rn → R and q1 : Rn → R are general quadratic functions of the form qi (x) = x Ai x + 2bi x + ci . Here, Ai ∈ Rn×n are symmetric matrices, bi ∈ Rn and ci ∈ R. We are interested, in particular, in the case where q0 and q1 are both nonconvex, i.e., Ai has at least one negative eigenvalue for both i = 0, 1. Problem (1), introduced and studied by Moré [25], Stern and Wolkowicz [33], generalizes the classical Trust-Region Subproblem (TRS) [6] in which one is asked to optimize a nonconvex quadratic ob
Data Loading...
