A Simple Convergence Time Analysis of Drift-Plus-Penalty for Stochastic Optimization and Convex Programs

Abstract

This paper considers the problem of minimizing the time average of a stochastic process subject to time average constraints on other processes. A canonical example is minimizing average power in a data network subject to multi-user throughput constraints. Another example is a (static) convex program. Under a Slater condition, the drift-plus-penalty algorithm is known to provide an $O(\epsilon )$ approximation to optimality with a convergence time of $O(1/{\epsilon }^2)$. This paper proves the same result with a simpler technique and in a more general context that does not require the Slater condition. This paper also emphasizes application to basic convex programs, linear programs, and distributed optimization problems.

10 pages

References in corpus (1)

• Energy-Aware Wireless Scheduling with Near Optimal Backlog and Convergence Time Tradeoffs

Cited by in corpus (2)

• Time-Average Stochastic Optimization with Non-convex Decision Set and its Convergence
• Optimal Dynamic Cloud Network Control