Abstract
The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter μ and generate a family of quadratic subproblems (Pμ)′s subject to two quadratic constraints. Each (Pμ), if the problem dimension n≥3, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters [μ̲,μ¯]. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find μ∗ numerically. Computational experiments show that our method solves the problem correctly and efficiently.
Original language | English |
---|---|
Pages (from-to) | 399-416 |
Number of pages | 18 |
Journal | Journal of Global Optimization |
Volume | 64 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2016 Feb 1 |
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Management Science and Operations Research
- Control and Optimization
- Applied Mathematics