Solving the Sum-of-Ratios Problem by an Interior-Point Method

Roland W. Freund, Florian Jarre

We consider the problem of minimizing the sum of a convex function and of $p\ge 1$ fractions subject to convex constraints. The numerators of the fractions are positive convex functions, and the denominators 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 special structure, the problem is ${\cal NP}$-complete even when only $p=1$ fraction is involved. 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 solution of certain convex subproblems. Based on this reduction, we propose an algorithm for computing the global minimum of the problem by means of an interior-point method for convex programs.

Numerical Analysis Manuscript 99 3 13, Bell Laboratories, Murray Hill, New Jersey, June 1999.