Greedy Primal-Dual Algorithm for Convex Optimization Problems in Dynamic Resource Allocation

In [6] 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 [6] 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. The algorithm can be viewed as a dynamic mechanism for solving rather general convex optimization problems, in particular those arizing in resource allocation in networks. We illustrate key features and applications of the algorithm on a simple example.