A Generalized Water-Filling Algorithm with Linear Complexity and Finite Convergence Time

This letter presents an algorithm with linear complexity and finite convergence time for solving the generalized water-filling (WF) problem. The WF problem is generalized by using a weighted-sum-rate, weighted-sum-power, and peak power constraints. The proposed algorithm solves the optimization problems with concave (power and rate) or quasi-concave (energy-efficiency) objective functions. Additionally, it can simultaneously use maximum-power and minimum-rate constraints and give a priority to one of the constraints in the event they generate an infeasible region. Through this generalization, the algorithm can be applied to many WF-based methods proposed in the literature. Moreover, this letter shows multiple ways to further reduce the computational complexity and, via simulation, illustrates the effectiveness of the proposed algorithm.