Abstract:
This paper examines a linear programming (LP) formulation of the network utility maximization problem. Such an LP formulation is inspired by a convex relaxation technique in the study of nonconvex polynomial optimization. In contrast to much of the prior works where the concavity of the network’s utility function is often assumed, the proposed method is capable of solving NUM problems with either concave or nonconcave utility function. Although the presented LP approach is originally formulated to compute upper bounds for the global optima of the NUM problem, we illustrate through several simulation examples that the obtained bounds often correspond to the problems’ exact global optima.
