Online Long-run Constrained Optimization

arXiv:2311.02426v2 Announce Type: replace-cross
Abstract: 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 arbitrarily generated and 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 the solution. Based on a proposed expected static cumulative regret, we derive the first …

abstract algorithm arxiv constraints cs.lg general generated leader linear long-term math.oc novel optimization primal random type