论文标题
在块中进行完全异步的原始偶发凸优化
Towards Totally Asynchronous Primal-Dual Convex Optimization in Blocks
论文作者
论文摘要
我们提出了一种平行的原始二算法，用于解决受约束的凸优化问题。该算法是“基于块”的，因为原始变量和双变量的向量被分配为块，每个块仅由单个处理器更新。我们考虑了异步的四种可能形式：在更新原始变量，对双变量的更新，原始变量的通信以及双重变量的通信。我们明确地构建了一个反例系列，以排除允许双重变量的异步通信，尽管允许其他形式的异步变量，而无需延迟时界限。制定了一阶更新法，并证明对异步方面具有鲁棒性。然后，我们将收敛速率得出，以执行操作的执行方式到Lagrangian鞍点，而无需指定必须执行的任何时间或模式。这些收敛速率包含同步算法作为特殊情况，并用于量化“异步惩罚”。数值结果说明了这些发展。
We present a parallelized primal-dual algorithm for solving constrained convex optimization problems. The algorithm is "block-based," in that vectors of primal and dual variables are partitioned into blocks, each of which is updated only by a single processor. We consider four possible forms of asynchrony: in updates to primal variables, updates to dual variables, communications of primal variables, and communications of dual variables. We explicitly construct a family of counterexamples to rule out permitting asynchronous communication of dual variables, though the other forms of asynchrony are permitted, all without requiring bounds on delays. A first-order update law is developed and shown to be robust to asynchrony. We then derive convergence rates to a Lagrangian saddle point in terms of the operations agents execute, without specifying any timing or pattern with which they must be executed. These convergence rates contain a synchronous algorithm as a special case and are used to quantify an "asynchrony penalty." Numerical results illustrate these developments.
