Competitive Online Convex Optimization With Switching Costs and Ramp Constraints
Competitive Online Convex Optimization With Switching Costs and Ramp Constraints
复制标题
DOI：
10.1109/tnet.2021.3053910
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ming Shi;Xiaojun Lin;S. Fahmy
中科院分区：
文献类型：
--
作者：
Ming Shi;Xiaojun Lin;S. Fahmy
研究了具有线性同级成本、切换成本和斜坡约束的在线凸优化(OCO)问题的竞争性在线算法。虽然OCO问题在文献中已经得到了广泛的研究，但关于能够获得较小竞争比的相应在线解决方案的结果有限。我们首先开发了一个强大的计算框架，它可以计算基于仿射策略类的最优竞争比。我们的计算框架可以处理相当一般的成本和约束类别。与文献中的其他竞争性结果相比，我们提出的方法的一个关键特征是它可以处理由于硬可行性约束而可能出现的不可行的场景。其次，我们设计了一个健壮化过程，以产生一个在线算法，该算法对于平均情况和最坏情况的输入都能获得良好的性能。我们对网络功能虚拟化(NFV)协调和扩展进行了案例研究，以演示我们所提出的方法的有效性。
We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared with other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods.