A distributed algorithm for high-dimension convex quadratically constrained quadratic programs

Run Chen () and Andrew L. Liu ()
Additional contact information
Run Chen: Purdue University
Andrew L. Liu: Purdue University

Computational Optimization and Applications, 2021, vol. 80, issue 3, No 5, 830 pages

Abstract: Abstract 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, high-dimension 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, high-dimension 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. 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 high-dimension problems.

Keywords: Convex QCQP; Distributed algorithm; Proximal method; Parallel computing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00319-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:80:y:2021:i:3:d:10.1007_s10589-021-00319-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00319-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().