期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 64, 期 2, 页码 399-416出版社
SPRINGER
DOI: 10.1007/s10898-015-0315-2
关键词
Fractional programming; (Generalized) Rayleigh quotient; Quadratically constrained quadratic programming; S-Lemma; Semidefinite programming; Quadratic fit line search
资金
- Ministry of Science and Technology of Taiwan [MOST 103-2115-M-006-014-MY2]
- National Natural Science Foundation of China [11471325]
- Beijing Higher Education Young Elite Teacher Project [29201442]
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 subject to two quadratic constraints. Each , if the problem dimension , 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据