An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint (Q1069860)

A problem of the maximization of the ratio of a concave function to a convex function is considered, subject to an upper bound on a single convex constraint function; all these functions are assumed to be differentiable. An incremental algorithm is defined, which solves the problem parametrically for different values of the constraint function by the solution of a set of ordinary first order differential equations. If K is the number of variables in the problem and B(K) is an upper bound - dependent of K - of the time needed to evaluate any function value or any first or second order derivative, the complexity of the algorithm is of the order \(O[(B(K)K+K)a]\), where a is the number of integration steps applied in the solution of the differential equations. In particular, a cost-effectiveness resource allocation problem with separable functions is solved numerically in a time of the order O[Ka] if B(K) is independent of K; an example of such a problem is given with analytically solvable differential equations.