论文标题
安全的双重梯度方法用于网络实用性最大化问题
Safe Dual Gradient Method for Network Utility Maximization Problems
论文作者
论文摘要
在本文中，我们介绍了一种新型的一阶双梯度算法，用于解决具有安全至关重要约束的网络中的资源分配方案中出现的网络实用性最大化问题。受到应用程序的启发，只有客户的需求才能通过发布的价格和与客户的实时双向通信影响，我们需要算法来生成\ textit {安全价格}。这意味着，在任何迭代中，应响应张贴的价格违反网络的安全限制，因此无迭代。因此，与现有的一阶方法相反，我们的算法（称为安全双重梯度方法（SDGM））在所有迭代中都可以产生可行的原始迭代。我们通过1）确保原始可行性在约束中添加安全保证金，以及2）使用基于符号的双重更新方法，该方法具有不同的步骤尺寸，用于加上和减去方向。此外，我们证明了由SDGM生成的原始迭代实现了$ {\ cal o}（\ sqrt {t}）$的Sublinear静态遗憾。
In this paper, we introduce a novel first-order dual gradient algorithm for solving network utility maximization problems that arise in resource allocation schemes over networks with safety-critical constraints. Inspired by applications where customers' demand can only be affected through posted prices and real-time two-way communication with customers is not available, we require an algorithm to generate \textit{safe prices}. This means that at no iteration should the realized demand in response to the posted prices violate the safety constraints of the network. Thus, in contrast to existing first-order methods, our algorithm, called the safe dual gradient method (SDGM), is guaranteed to produce feasible primal iterates at all iterations. We ensure primal feasibility by 1) adding a diminishing safety margin to the constraints, and 2) using a sign-based dual update method with different step sizes for plus and minus directions. In addition, we prove that the primal iterates produced by the SDGM achieve a sublinear static regret of ${\cal O}(\sqrt{T})$.
