追逐长期约束的凸函数
内容提要
该文综述约束在线凸优化研究进展，提出在线凸-凹转化框架与自适应梯度下降算法以改进遗憾界，并研究时变约束、非凸优化、切换成本、DR-submodular最大化及长期约束等问题，给出次线性遗憾与约束违规界，应用于电动汽车充电和河流污染源辨识等场景。
延伸解读
长期约束在线凸优化的算法演进
文章梳理了长期约束在线凸优化的算法发展。2011年提出的自适应在线梯度下降算法，在损失和约束违规上分别达到O(T^max{β,1−β})和O(T^(1−β/2))的累积遗憾界，优于Mahdavi等（2012）的已知结果。后续研究进一步处理时变约束、非凸优化、切换成本等挑战，并给出次线性遗憾与约束违规界，推动了该领域的理论进展。
从理论到应用：电动汽车充电与污染源辨识
文章展示了长期约束在线凸优化在能源与可持续发展领域的应用。针对碳感知电动汽车充电问题，提出了基于阈值的竞争算法和学习增强算法，利用不可信黑盒建议提升平均性能并保证最坏情况竞争性，实证显示优于基准方法。此外，该框架还应用于长期风险约束的河流污染源辨识，验证了理论结果的有效性。
非凸与DR-submodular扩展的挑战
文章探讨了在线非凸优化和DR-submodular最大化等扩展问题。针对在线非凸优化与运动成本，提出了两个充分条件并得出算法SFHC的竞争比率；针对在线连续DR-submodular最大化，在随机线性长期约束下提出OLFW算法，得到次线性后悔和约束违规上限。这些工作表明，长期约束框架正逐步覆盖更复杂的非凸场景。
Q&A
约束在线凸优化主要研究什么问题？
约束在线凸优化研究在长期约束下进行在线决策的问题，目标是在最小化累积损失的同时满足约束条件，并控制遗憾界和约束违规界。
有哪些算法可以解决具有长期约束的在线凸优化问题？
文章提到了适应性在线梯度下降算法、在线Lagrangian Frank-Wolfe（OLFW）算法、Follow-the-Perturbed-Leader类型算法等，这些算法能处理长期约束并给出次线性遗憾和约束违规界。
在线凸优化中如何处理时变约束？
文章研究了具有时间变化约束的在线凸优化问题，提出了一种算法，其收敛性具有时间复杂度，并且可以在没有先验知识的情况下达到无偏的最优解。
在线凸优化在电动汽车充电中有哪些应用？
文章通过碳感知的电动汽车充电案例研究，对所提出的基于阈值的竞争算法进行了实证评估，结果显示相对基准方法，该算法显著改进了问题的解决方法。
在线非凸优化和运动成本问题有哪些研究成果？
文章提出了两个有效的充分条件来解决在线非凸优化和运动成本问题，并得出了算法SFHC的竞争比率，还为运动和击打成本提供了竞争比率结果。
在线DR-submodular最大化问题中如何保证约束满足？
文章采用随机线性长期约束，并提出在线Lagrangian Frank-Wolfe（OLFW）算法，得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。
