Branch And Bound Algorithms For Two Types Of Fractional Programming Problems

The fractional programming problem is a very important class of non-convex opti-mization problems.It is widely used in fields such as transportation planning,financial investment,cluster analysis,government planning and so on.There are many special forms of such problems.In general,they have multiple local solutions rather than global optimal solutions,which increase the difficulty of solving the problems.In recent years,many algorithms have been proposed to solve special models of such problems.This pa-per proposes branch and bound algorithms for maximizing the sum of linear ratios,and minimizing quadratically constrained sum of quadratic ratios respectively.First of all,the model to be studied in this paper,the application background and theoretical significance are given.Otherwise,the research status of this model and the main work of this paper are briefly introduced.Secondly,a branch-and-bound algorit,hm is proposed for a class of the sum of lin-ear ratios.On the basis of the equivalent transformation of the model,the equivalence problem is linearized by the convex envelope of the bilinear function and the concave envelope of the ratio function,and then the optimal solution of the original problem is obtained by solving a series of linear programming problems.The convergence of the branch-and-bound algorithm is proved theoretically and the computational complexity of the algorithm is analyzed.Numerical experiments show that the algorithm is effective and feasible.Finally,we consider a class of the sum of quadratic ratios problem with quadratic constraints.We first use equivalence techniques to transform the original problem into its equivalence problem.Then,we relax the equivalence problem to get its linear pro-gramming problem by utilizing the matrix decomposition theory.On the basis of solving a series of linear programming problems,the optimal solution to the original problem is obtained.At last,the convergence of the algorithm is given.Numerical experiments illustrate the feasibility efficiency of the proposed algorithm for solving the quadratic ratio problem.