We consider online optimization with binary decision variables and convex loss functions. We design a new algorithm, binary online gradient descent (bOGD), and bound its expected dynamic regret. We provide a regret bound that holds for any time horizon and a specialized bound for finite time horizons. First, we present the regret as the sum of the relaxed, continuous round optimum tracking error and the rounding error of our update in which the former asymptomatically decreases with time under certain conditions. Then, we derive a finite-time bound that is sublinear in time and linear in the cumulative variation of the relaxed, continuous round optima. We apply bOGD to demand response with thermostatically controlled loads, in which binary constraints model discrete on/off settings. We also model uncertainty and varying load availability, which depend on temperature deadbands, lockout of cooling units and manual overrides. We test the performance of bOGD in several simulations based on demand response.
翻译:我们考虑以二进制决定变量和 convex 损失函数实现在线优化。 我们设计了一种新的算法, 二进制在线梯度下行( BOGD), 并约束了它预期的动态后悔感。 我们提供了在任何时间跨度和有限时间跨度上都保持的遗憾感。 首先, 我们将遗憾感应作为放松、 连续循环最佳跟踪错误和我们更新时的圆形错误的总和来表示, 因为在特定条件下, 以前的无症状会随着时间的减少而减少。 然后, 我们得出一个有限时间约束, 在放松、 连续环曲的累积变异中, 是一个子线性和线性线性。 我们应用 bOGD 来要求以恒温控制的负负负载作出反应, 在这种负载中, 双进制约束模式在/ 关闭 。 我们还将不确定性和不同负负负载能力作为模型, 取决于温度断带, 冷却器和手控装置的关闭。 我们根据需求在数个模拟中测试bOGD的性表现。