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.
Contact: [email protected]
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)