Global optimization of nonlinear sum of ratios problem (Q702537)

The sum of ratios problem is a special class optimization between fractional programming. At present there exists a number of algorithms for globally solving the sum of ratios problem in which the numerators and denominators are affine functions and the feasible region is a polyhedron. In this paper the authors present a branch and bound algorithm for globally solving a nonlinear sum of ratios problem (P) in which the feasible region is a nonconvex set and the numerators and denominators are generalized multivariable polynomials whose form has many applications. The algorithm works by solving a sum of ratios problem (Q) that is equivalent to problem (P). The algorithm constructs the linear lower bounding functions of the objective function and the constraint functions of (Q) over the nonconvex feasible region. Then a linear relaxation programming is derived which provides the lower bound of the optimal value. The proposed branch and bound algorithm is convergent to the global minimum through the successive solving of linear programming subproblems that are solved by the simplex algorithm. These characteristics offer computational advantanges that can enhance the efficiencies of the proposed algorithm.