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)在多节点的计算机集群上实施我们的算法。我们进行的数字实验是针对不同应用的不同尺度的数据集进行的,结果显示我们的算法在解决大规模问题方面具有有利的比例性。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
3+阅读 · 2018年3月13日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员