Sum of Ratios Optimization using a New Variant of Dinkelbach's Algorithm

The sum of ratios optimization problem appears in many different communications applications and therefore is an important topic to study. The classic power control problem in a communication link is defined as maximizing the data rate in a scenario with multiple users that can be modeled as a sum of the ratios optimization problem. The Dinkelbach's method has been extensively used in optimizing single ratios, but for many years, it was believed that no generalization to Dinkelbach's algorithm for the sum of ratios problem was possible, and a few attempts were proven wrong later. In this research, we propose a new generalization to the Dinkelbach's technique tailored to the sum of functions of ratios problem along with developing a new way to update the auxiliary variable in the equivalent parametric program. The new variant of Dinkelbach's algorithm is proved to be a fast and accurate technique to solve the problem of the sum of non-decreasing functions of ratios with concave numerators and convex denominators.