  This paper considers time-average optimization, where a decision vector is
chosen every time step within a (possibly non-convex) 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, multi-agent
systems, and operations research, where decisions are constrained to a discrete
set and the decision average can represent average bit rates or average agent
actions. This time-average optimization extends traditional convex formulations
to allow a non-convex decision set. This class of problems can be solved by
Lyapunov optimization. A simple drift-based algorithm, related to a classical
dual subgradient algorithm, converges to an $\epsilon$-optimal solution within
$O(1/\epsilon^2)$ time steps. Further, the algorithm is shown to have a
transient phase and a steady state phase which can be exploited to improve
convergence rates to $O(1/\epsilon)$ and $O(1/{\epsilon^{1.5}})$ when vectors
of Lagrange multipliers satisfy locally-polyhedral and locally-smooth
assumptions respectively. Practically, this improved convergence suggests that
decisions should be implemented after the transient period.
