An Efficient Algorithm for Solving Convex–Convex Quadratic Fractional Programs
An Efficient Algorithm for Solving Convex–Convex Quadratic Fractional Programs
复制标题
DOI：
10.1007/s10957-007-9188-y
复制
发表时间：
2007-04
影响因子：
1.9
通讯作者：
R. Yamamoto;H. Konno
中科院分区：
文献类型：
--
作者：
R. Yamamoto;H. Konno
本文研究了一类目标函数定义为两个凸二次函数之比且约束条件为线性的凸凸型二次分数型规划的有效求解算法。这是一个典型的具有多个局部极大值的非凹最大化问题。这里提出的算法是(i)经典Dinkelbach方法，（ii）解决非凸二次规划问题的整数规划方法和（iii）标准非线性规划算法的组合。本文将证明，结合上述(i)和（ii）的精确算法可以解决比先前基于分支定界算法的算法所解决的问题大得多的问题。此外，(i)和（iii）的结合可以在实际的时间内解决更大的问题。
This paper is concerned with an efficient algorithm for solving a convex-convex type quadratic fractional program whose objective function is defined as the ratio of two convex quadratic functions and whose constraints are linear. This is a typical nonconcave maximization problem with multiple local maxima.The algorithm to be proposed here is a combination of (i) the classical Dinkelbach approach, (ii) the integer programming approach for solving nonconvex quadratic programming problems and (iii) the standard nonlinear programming algorithm.It will be shown that an exact algorithm which is a combination of (i) and (ii) above can solve problems much larger than those solved by an earlier algorithm based on a branch and bound algorithm. It addition, the combination of (i)–(iii) can solve much larger problems within a practical amount of time.