Online Long-run Constrained Optimization
Shijie Pan Wenjie Huang
In this paper, a novel Follow-the-Perturbed-Leader type algorithm is proposed
and analyzed for solving general long-term constrained optimization problems in
online manner, where the objective and constraints are not necessarily convex.
In each period, random linear perturbation and strongly concave perturbation
are incorporated in primal and dual directions, respectively, to the offline
oracle, and a global minimax point is searched as solution. Based on two
particular definitions of expected static cumulative regret, we derive the
first sublinear $O(T^{8/9})$ regret complexity for this class of problems. The
proposed algorithm is applied to tackle a long-term (risk) constrained river
pollutant source identification problem, demonstrating the validity of the
theoretical results and exhibiting superior performance compared to existing
method.