Journal of Nonlinear and Variational Analysis

Full Text: PDF
DOI: 10.23952/jnva.8.2024.6.04

Volume 8, Issue 6, 1 December 2024, Pages 883-907

 

Abstract. Fair resource allocation, which is vital in various fields, including advertising, cloud computing, and loan management, requires a delicate balance between maximizing revenue and ensuring fairness. This problem is commonly defined as constrained and regularized convex programming, where the objective function consists of a linear allocation cost and a nonseparable and nonlinear fairness regularizer. However, solving this problem for large cases, such as those with millions of variables, can be challenging and requires advanced computational methods and expertise. To address this issue, this paper proposes a distributed primal-dual hybrid gradient algorithm by using a tailored Bregman distance to solve a saddle point reformulation of the problem. Our algorithm allows for closed-form solutions to all subproblems and primarily employs matrix-vector multiplications, which can be efficiently executed via distributed parallel computations. Theoretical results demonstrate global iterate convergence and ergodic sublinear convergence rate under a practical stepsize condition. Furthermore, the proposed algorithm is shown to be more efficient and superior to off-the-shelf solvers such as the IPOPT and Gurobi, as evidenced by experimental results on synthetic and real-world industrial datasets.

 

How to Cite this Article:
H. Chen, X. Lu, Z. Shan, J. Yang, J. Zhou, A distributed primal-dual hybrid gradient algorithm for fair resource allocation, J. Nonlinear Var. Anal. 8 (2024), 883-907.