An efficient algorithm for solving the generalized trust region subproblem
- PDF / 624,939 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 300 Views
An efficient algorithm for solving the generalized trust region subproblem M. Salahi1 · A. Taati1
Received: 25 November 2015 / Revised: 16 March 2016 / Accepted: 29 April 2016 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2016
Abstract In this paper, we consider the interval bounded generalized trust region subproblem (GTRS) which is the problem of minimizing a general quadratic function subject to an upper and lower bounded general quadratic constraint. Under the assumption that two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence, a diagonalization-based algorithm is introduced to solve it by showing that GTRS is indeed equivalent to a linearly constrained convex univariate problem. Some numerical experiments are given to show the effectiveness of the proposed method and to compare it with the extended Rendl–Wolkowicz algorithm due to Pong and Wolkowicz. Keywords Generalized trust region subproblem · Global optimization · Diagonalization Mathematics Subject Classification 90C26 · 90C20
1 Introduction We are concerned with the following quadratic optimization problem, called the interval bounded generalized trust region subproblem (GTRS): p ∗ := inf
x T Ax − 2a T x
s.t. ≤ x T Bx − 2b T x ≤ u,
(GTRS)
where A, B ∈ are symmetric matrices with no definiteness assumed, a, b ∈ Rn and −∞ < ≤ u < ∞. When B = I, b = 0 and ≤ 0, GTRS reduces to the classical trust region subproblem (TRS). TRS plays a cardinal role in trust-region methods for both unconstrained and constrained nonlinear optimization (Conn et al. 2000; Celis et al. 1985) and even Rn×n
Communicated by Natasa Krejic.
B 1
M. Salahi [email protected] Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran
123
M. Salahi, A. Taati
though it is nonconvex, it can be solved efficiently in practice (Fortin and Wolkowicz 2004; Gould et al. 1999, 2010; Moré and Sorensen 1983; Rendl et al. 1997; Stern and Wolkowicz 1995). GTRS has recently been studied by Pong and Wolkowicz (2014) as a natural extension of the quadratic model TRS. The use of scaled trust regions with a positive definite scaling matrix B (Gould et al. 1999; Ben-Tal and Teboulle 1996) motivated studying GTRS. The choice of the scaling matrix B can be very important. Positive definite scaling matrix maintains tractability of the subproblem, but it would be useful and important to allow a larger class of matrices in order to obtain scale invariance (Fletcher 1987). Moreover, GTRS with the two-sided constraints model permits minimum as well as maximum step lengths. In addition, the possibly nonzero b accounts for a shift of the center of the trust region, which allows trust regions to be constructed around previous iterates. In Pong and Wolkowicz (2014), the authors obtained necessary and sufficient optimality conditions for GTRS under a constraint qualification which has been shown that it can be assumed without loss of generality. In particular, after classifying GTRS into easy and hard case
Data Loading...
