A Combined Algorithm for Fractional Programming

In this paper, we present an outer approximation algorithm for solving the following problem: max_xS{f(x)/g(x)}, where f(x)0 and g(x)>0 are d.c. (difference of convex) functions over a convex compact subset S of Rⁿ. Let ()=max_xS(f(x)–g(x)), then the problem is equivalent to finding out a solution of the equation ()=0. Though the monotonicity of () is well known, it is very time-consuming to solve the previous equation, because that maximizing (f(x)–g(x)) is very hard due to that maximizing a convex function over a convex set is NP-hard. To avoid such tactics, we give a transformation under which both the objective and the feasible region turn to be d.c. After discussing some properties, we propose a global optimization approach to find an optimal solution for the encountered problem.