A Probabilistic Sample Path Convergence Time Analysis of Drift-Plus-Penalty Algorithm for Stochastic Optimization

Abstract

This paper considers the problem of minimizing the time average of a controlled stochastic process subject to multiple time average constraints on other related processes. The probability distribution of the random events in the system is unknown to the controller. A typical application is time average power minimization subject to network throughput constraints for different users in a network with time varying channel conditions. We show that with probability at least $1-2\hat{I}´$, the classical drift-plus-penalty algorithm provides a sample path $\mathcal{O}(\epsilon )$ approximation to optimality with a convergence time $\mathcal{O}(\frac{1}{{\epsilon }^2}\max \left\{{\log }^2\frac{1}{\epsilon }\log \frac{2}{\hat{I}}´,{\log }^3\frac{2}{\hat{I}}´\right\})$, where $\epsilon >0$ is a parameter related to the algorithm. When there is only one constraint, we further show that the convergence time can be improved to $\mathcal{O}\left(\frac{1}{{\epsilon }^2}{\log }^2\frac{1}{\hat{I}}´\right)$.

This is an updated version for IEEE Transactions on Automatic Control with changes highlighted