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.

arXiv comment10 pages

References in corpus (3)

• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Distributed stochastic optimization via correlated scheduling
• Energy-Aware Wireless Scheduling with Near Optimal Backlog and Convergence Time Tradeoffs

Cited by in corpus (5)

• Optimal Resource Allocation in IEEE 802.11ax Uplink OFDMA with Scheduled Access
• A Primal-Dual Type Algorithm with the $O(1/t)$ Convergence Rate for Large Scale Constrained Convex Programs
• On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs
• Time-Average Stochastic Optimization with Non-convex Decision Set and its Convergence
• Optimal Dynamic Cloud Network Control