Time-average optimization with nonconvex decision set and its convergence

This paper considers time-average optimization, where a decision vector is chosen every time step within a (possibly nonconvex) set, and the goal is to minimize a convex function of the time averages subject to convex constraints on these averages. Such problems have applications in networking and operations research, where decisions can be constrained to discrete sets and time averages can represent bit rates, power expenditures, and so on. These problems can be solved by Lyapunov optimization. This paper shows that a simple drift-based algorithm, related to a classical dual subgradient algorithm, converges to an o-optimal solution within O(1/ε²) time steps. However, when the problem has a unique vector of Lagrange multipliers, the algorithm is shown to have a transient phase and a steady state phase. By restarting the time averages after the transient phase, the total convergence time is improved to O(1/ε) under a locally-polyhedral assumption, and to O(1/ε^1.5) under a locally-smooth assumption.