Variable Partitioning for Distributed Optimization
Variable Partitioning for Distributed Optimization
复制标题
用于分布式优化的变量分区
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Serban
中科院分区：
文献类型：
--
作者：
Yuchen Zheng;Ilbin Lee;N. Serban
本文讨论了如何在大规模优化问题分解时对决策变量进行划分，以获得分布式求解方法的最佳性能。顺序地解决大规模优化问题可能在计算上具有挑战性。一个经典的方法是将问题分解为更小的子问题，并以分布式方式解决它们。然而，在文献中很少有讨论的变量应分组在一起，形成的子问题，特别是当优化配方涉及复杂的约束。我们专注于最流行的分布式方法之一，对偶分解和分布式次梯度方法。基于其收敛速度的理论保证，我们解释说，分区的变量可以严重影响收敛速度和突出的重要性，对偶约束的数量。然后，我们介绍了一种新的方法来找到一个分区，减少了对偶约束的数量，利用社区检测算法从物理文献。粗略地说，所提出的方法组的决策变量出现在一起的约束和解决所产生的子问题的变量块并行。在一个真实的应用上的实验表明，该方法显著地加快了分布式次梯度法的收敛速度。我们的方法的优势变得更加显着的问题的大小增加，每个约束涉及更多的变量。
This paper is about how to partition decision variables while decomposing a large-scale optimization problem for the best performance of distributed solution methods. Solving a large-scale optimization problem sequen- tially can be computationally challenging. One classic approach is to decompose the problem into smaller sub-problems and solve them in a distributed fashion. However, there is little discussion in the literature on which variables should be grouped together to form the sub-problems, especially when the optimization formulation involves complex constraints. We focus on one of the most popular distributed approaches, dual decomposition and distributed sub-gradient methods. Based on a theoretical guarantee on its convergence rate, we explain that a partition of variables can critically affect the speed of convergence and highlight the importance of the number of dualized constraints. Then, we introduce a novel approach to find a partition that reduces the number of dualized constraints by utilizing a community detection algorithm from physics literature. Roughly speaking, the proposed method groups decision variables that appear together in con- straints and solves the resulting sub-problems with blocks of variables in parallel. Empirical experiments on a real application show that the proposed method significantly accelerates the convergence of the distributed sub-gradient method. The advantage of our approach becomes more significant as the size of the problem increases and each constraint involves more variables.