Time-Average Optimization With Nonconvex Decision Set and Its Convergence

DOI10.1109/TAC.2017.2684459MaRDI QIDQ4589492zbMATH OpenOpenAlexFDO

Authors Sucha Supittayapornpong, Longbo Huang, Michael J. Neely

Publication date 10 November 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.02617

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: 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/epsilo{n}^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/epsilo{n}^{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.

Cited in

(1)

• A fast continuous time approach with time scaling for nonsmooth convex optimization

This page was built for publication: Time-Average Optimization With Nonconvex Decision Set and Its Convergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589492)