Greedy Primal-Dual Algorithm >for Dynamic Resource Allocation in Complex Networks

In [12] a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which network generates several "commodities.") Underlying the control problem of [12] is a convex optimization problem subject to a set of 'linear' constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional 'convex' (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples.