A Novel Online Convex Optimization Algorithm Based on Virtual Queues

Xuanyu Cao, Junshan Zhang, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 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 cite yu2017simple, 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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Communications, ICC 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781538631805
DOIs
StatePublished - Jul 27 2018
Event2018 IEEE International Conference on Communications, ICC 2018 - Kansas City, United States
Duration: May 20 2018May 24 2018

Publication series

NameIEEE International Conference on Communications
Volume2018-May
ISSN (Print)1550-3607

Other

Other2018 IEEE International Conference on Communications, ICC 2018
CountryUnited States
CityKansas City
Period5/20/185/24/18

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A Novel Online Convex Optimization Algorithm Based on Virtual Queues'. Together they form a unique fingerprint.

Cite this