We propose a Jacobi-style distributed algorithm to solve convex, quadratically constrained quadratic programs (QCQPs), which arise from a broad range of applications. While small to medium-sized convex QCQPs can be solved efficiently by interior-point algorithms, large-scale problems pose significant challenges to traditional algorithms that are mainly designed to be implemented on a single computing unit. The exploding volume of data (and hence, the problem size), however, may overwhelm any such units. In this paper, we propose a distributed algorithm for general, non-separable, large-scale convex QCQPs, using a novel idea of predictor-corrector primal-dual update with an adaptive step size. The algorithm enables distributed storage of data as well as parallel distributed computing. We establish the conditions for the proposed algorithm to converge to a global optimum, and implement our algorithm on a computer cluster with multiple nodes using Message Passing Interface (MPI). The numerical experiments are conducted on data sets of various scales from different applications, and the results show that our algorithm exhibits favorable scalability for solving large-scale problems.
翻译:我们提出一个雅各比式分布式算法,以解决来自广泛各种应用的锥形、二次限制的二次程序(QCQPs),这种算法可以由内部点算法有效解决,而大型问题则对主要设计在一个单一计算单位上实施的传统算法构成重大挑战。数据爆炸量(以及因此造成的问题大小)可能会压倒任何这类单位。在本文中,我们提出一个普通、非可分离、大尺度的锥形QQQPs的分布式算法,采用预测或校正或初步更新的新概念,采用适应性步骤大小。这种算法能够分散存储数据,同时平行分布式计算。我们为拟议的算法建立条件,以便与全球最佳结合,并利用信息通过接口(MPI)在多节点的计算机集群上实施我们的算法。我们进行的数字实验是针对不同应用的不同尺度的数据集进行的,结果显示我们的算法在解决大规模问题方面具有有利的比例性。