In this letter, we address the problem of ergodic sum-rate maximization under proportional rate constraints for the uplink of single-carrier frequency-division multiple-access (SC-FDMA) systems. Finding optimal solution generally requires high computational complexity, because SC-FDMA imposes the contiguous allocation of the available frequency resources. To reduce complexity, we propose a novel suboptimal algorithmic solution, based on Lagrangian relaxation of the rate constraints, which exploits a simple but effective estimation of the average number of the resources to allocate in order to reduce the search space. The complexity of the resulting algorithm increases only linearly with the number of users and the number of resources, whereas the performance gap to optimal solution is limited to the 10% of the sum-rate.