Online Convex Optimization with Time-Varying Constraints

Abstract

This paper considers online convex optimization with time-varying constraint functions. Specifically, we have a sequence of convex objective functions $\{f_t(x){\}}_{t=0}^{\infty }$ and convex constraint functions $\{g_{t,i}(x){\}}_{t=0}^{\infty }$ for $i\in \{1,...,k\}$. The functions are gradually revealed over time. For a given $\epsilon >0$, the goal is to choose points $x_t$ every step $t$, without knowing the $f_t$ and $g_{t,i}$ functions on that step, to achieve a time average at most $\epsilon$ worse than the best fixed-decision that could be chosen with hindsight, subject to the time average of the constraint functions being nonpositive. It is known that this goal is generally impossible. This paper develops an online algorithm that solves the problem with $O(1/{\epsilon }^2)$ convergence time in the special case when all constraint functions are nonpositive over a common subset of ${\mathbb{R}}^n$. Similar performance is shown in an expected sense when the common subset assumption is removed but the constraint functions are assumed to vary according to a random process that is independent and identically distributed (i.i.d.) over time slots $t\in \{0,1,2,\dots \}$. Finally, in the special case when both the constraint and objective functions are i.i.d. over time slots $t$, the algorithm is shown to come within $\epsilon$ of optimality with respect to the best (possibly time-varying) causal policy that knows the full probability distribution.

18 pages, no figures

References in corpus (1)

• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints

Cited by in corpus (22)

• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization
• Second-order Online Nonconvex Optimization
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Online Convex Optimization with Stochastic Constraints
• Decentralized Online Learning for Noncooperative Games in Dynamic Environments
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
• An Online Newton's Method for Time-varying Linear Equality Constraints
• Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
• Online DR-Submodular Maximization with Stochastic Cumulative Constraints
• Learning Aided Optimization for Energy Harvesting Devices with Outdated State Information
• An Iterative Riccati Algorithm for Online Linear Quadratic Control
• Asynchronous Optimization over Weakly Coupled Renewal Systems
• Online Convex Optimization with Continuous Switching Constraint
• Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study
• Optimizing Adaptive Video Streaming in Mobile Networks via Online Learning
• Online Proximal-ADMM For Time-varying Constrained Convex Optimization
• Online Convex Optimization with Perturbed Constraints