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, \ldots\}$. 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.

本文研究了具有时间变化的约束条件的在线凸优化问题，并提出了一种算法，其收敛性具有一定的时间复杂度，并且可以在没有先验知识的情况下达到无偏的最优解。