Solving the sum-of-ratios problem by an interior-point method

We consider the problem of minimizing the sum of a convex function and of p greater than or equal to 1 fractions subject to convex constraints. The nu merators of the fractions are positive convex functions, and the denominato rs are positive concave functions. Thus, each fraction is quasi-convex. We give a brief discussion of the problem and prove that in spite of its speci al structure, the problem is NP-complete even when only p = 1 fraction is i nvolved. We then show how the problem can be reduced to the minimization of a function of p variables where the function values are given by the solut ion of certain convex subproblems. Based on this reduction, we propose an a lgorithm for computing the global minimum of the problem by means of an int erior-point method for convex programs.