论文标题
增强拉格朗日的方法，用于时变限制的在线凸优化
Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization
论文作者
论文摘要
在本文中，我们考虑了在线凸优化（OCO），具有随着时变的损失和约束功能。具体而言，决策者仅基于过去的信息选择顺序决策，同时，随着时间的推移，损失和约束功能被揭示。我们首先为时变功能约束的OCO（无反馈延迟）开发了基于模型的增强拉格朗日方法（MALM）。在标准假设下，我们建立了均匀的遗憾和均匀的限制违反马尔姆的行为。此外，我们扩展了Malm，以处理延迟的反馈，以处理时间变化的功能约束OCO，其中损失和约束功能的反馈信息会透露给有延迟的决策者。没有其他假设，我们还为延迟版本的Malm建立了额定的遗憾和均匀的约束违反。最后，提供了一些约束OCO的示例的数值结果，包括在线网络资源分配，在线逻辑回归和在线二次约束四个程序，以证明所提出的算法的效率。
In this paper, we consider online convex optimization (OCO) with time-varying loss and constraint functions. Specifically, the decision maker chooses sequential decisions based only on past information, meantime the loss and constraint functions are revealed over time. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO (without feedback delay). Under standard assumptions, we establish sublinear regret and sublinear constraint violation of MALM. Furthermore, we extend MALM to deal with time-varying functional constrained OCO with delayed feedback, in which the feedback information of loss and constraint functions is revealed to decision maker with delays. Without additional assumptions, we also establish sublinear regret and sublinear constraint violation for the delayed version of MALM. Finally, numerical results for several examples of constrained OCO including online network resource allocation, online logistic regression and online quadratically constrained quadratical program are presented to demonstrate the efficiency of the proposed algorithms.
