Back to Search
Start Over
Time-Average Optimization With Nonconvex Decision Set and Its Convergence.
- Source :
-
IEEE Transactions on Automatic Control . Aug2017, Vol. 62 Issue 8, p4202-4208. 7p. - Publication Year :
- 2017
-
Abstract
- 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, multiagent systems, and operation 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 nonconvex 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. Furthermore, 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 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189286
- Volume :
- 62
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Automatic Control
- Publication Type :
- Periodical
- Accession number :
- 124331688
- Full Text :
- https://doi.org/10.1109/TAC.2017.2684459