Parametric approach for solving quadratic fractional optimization with a linear and a quadratic constraint
- PDF / 219,051 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 220 Views
Parametric approach for solving quadratic fractional optimization with a linear and a quadratic constraint Maziar Salahi · Saeed Fallahi
Received: 13 May 2014 / Revised: 27 September 2014 / Accepted: 19 October 2014 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2014
Abstract This paper studies a class of nonconvex fractional minimization problem in which the feasible region is the intersection of the unit ball with a single linear inequality constraint. First, using Dinkelbach’s idea, it is shown that finding the global optimal solution of the underlying problem is equivalent to find the unique root of a function. Then using a diagonalization technique, we present an efficient method to solve the indefinite quadratic minimization problem with the original problem’s constraints within a generalized Newton-based iterative algorithm. Our preliminary numerical experiments on several randomly generated test problems show that the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large-scale problems. Keywords Fractional optimization · Extended trust region subproblems · Global optimization · Generalized Newton method · Semidefinite optimization relaxation Mathematics Subject Classification
90C32 · 90C26 · 90C22
1 Introduction Consider the following quadratic fractional problem (QFP) min
x T A1 x + b1T x + c1
(QFP)
x T A2 x + b2T x + c2
Communicated by Natasa Krejic. M. Salahi (B) · S. Fallahi Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran e-mail: [email protected]; [email protected] S. Fallahi e-mail: [email protected]
123
M. Salahi, S. Fallahi
x2 ≤ 1, a T x ≤ u. where AiT = Ai ∈ Rn×n , bi , a ∈ Rn and ci , u ∈ R for i = 1, 2. The main difficulty associated with this problem is its nonconvexity (Beck and Eldar 2006; Salahi 2009; Sima et al. 2004; Zhang and Hayashi 2011). The importance of nonconvex fractional optimization problems lies in their broad applications including signal processing, communications, financial analysis, location theory, portfolio selection problem, and stochastic decision-making problems (Lo and MacKinlay 1997; Ohlson and Ziemba 1976; Stancu-Minasian 1997). In general, these classes of problems are hard to solve, however, several among them have been successfully solved using semidefinite optimization (SDO) relaxation (Beck and Teboulle 2009, 2010; Fallahi and Salahi 2013). The purpose of this paper is to reduce QFP to a problem of finding the unique root of a single-variable equation, which itself involves an extended trust region subproblem (ETRS). We have applied the generalized Newton method to solve the univariate equation. The rest of the paper is organized as follows: In Sect. 2, we provide an algorithm for the solutions of QFP which consists of solving the univariate equation where ETRS is solved at each iteration. In Sect. 3, we derive an equivalent convex reformulation of ETRS. Computational results are reported in Sect. 4 and fi
Data Loading...
