Sparsity-Exploiting Distributed Projections onto a Simplex

Yongzheng Dai () and Chen Chen ()
Additional contact information
Yongzheng Dai: Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210
Chen Chen: Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210

INFORMS Journal on Computing, 2024, vol. 36, issue 3, 820-835

Abstract: Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, the primary focus of the literature is on serial algorithms. We present a parallel method that decomposes the input vector and distributes it across multiple processors for local projection. Our method is especially effective when the resulting projection is highly sparse, which is the case, for instance, in large-scale problems with independent and identically distributed (i.i.d.) entries. Moreover, the method can be adapted to parallelize a broad range of serial algorithms from the literature. We fill in theoretical gaps in serial algorithm analysis and develop similar results for our parallel analogues. Numerical experiments conducted on a wide range of large-scale instances, both real world and simulated, demonstrate the practical effectiveness of the method.

Keywords: simplex; parallel algorithm; projection algorithm (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0328 (application/pdf)

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:inm:orijoc:v:36:y:2024:i:3:p:820-835

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().