A virtual-queue-based algorithm for constrained online convex optimization with applications to data center resource allocation

Xuanyu Cao, Junshan Zhang, H. Vincent Poor

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

In this paper, online convex optimization (OCO) problems with time-varying objective and constraint functions are studied from the perspective of an agent who takes actions in real time. Information about the current objective and constraint functions is revealed only after the corresponding action is already chosen. Inspired by a fast converging algorithm for time-invariant optimization in the very recent work [1], we develop a novel online algorithm based on virtual queues for constrained OCO. Optimal points of the dynamic optimization problems with full knowledge of the current objective and constraint functions are used as a dynamic benchmark sequence. Upper bounds on the regrets with respect to the dynamic benchmark and the constraint violations are derived for the presented algorithm in terms of the temporal variations of the underlying dynamic optimization problems. It is observed that the proposed algorithm possesses sublinear regret and sublinear constraint violations, as long as the temporal variations of the optimization problems are sublinear, i.e., the objective and constraint functions do not vary too drastically across time. The performance bounds of the proposed algorithm are superior to those of the state-of-the-art OCO method in most scenarios. Besides, different from the saddle point methods widely used in constrained OCO, the stepsize of the proposed algorithm does not rely on the total time horizon, which may be unknown in practice. Finally, the algorithm is applied to a dynamic resource allocation problem in data center networks. Numerical experiments are conducted to corroborate the merit of the developed algorithm and its advantage over the state-of-the-art.

Original languageEnglish (US)
Article number8338087
Pages (from-to)703-716
Number of pages14
JournalIEEE Journal on Selected Topics in Signal Processing
Volume12
Issue number4
DOIs
StatePublished - Aug 2018

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Online convex optimization
  • constrained optimization
  • data centers
  • dynamic resource allocation
  • sequential decision making
  • virtual queues

Fingerprint Dive into the research topics of 'A virtual-queue-based algorithm for constrained online convex optimization with applications to data center resource allocation'. Together they form a unique fingerprint.

  • Cite this