Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
Open accessThe DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Abstract
We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multi-user interfering systems. Our main contributions are i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing ad hoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descent schemes for convex functions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Finite-Dimensional Variational Inequalities and Complementarity Problems
(2004) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/b97544 · Cited by 3,521
Shi, Q., Razaviyayn, M., Luo, Z.-Q., & He, C. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2147784 · Cited by 2,129 · cited 14×
“on the best-response (termed MIMO-SJBR) with those of the schemes proposed in the literature for a similar problem, namely the MIMO-MDP [23], [24], and the MIMOWMMSE [30].”
BackgroundMethodInfluentialParlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures
Chiang, M., Low, S. H., Calderbank, A. R., & Doyle, J. C. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887322 · Cited by 1,352
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization
Razaviyayn, M., Hong, M., & Luo, Z.-Q. (2013) · SIAM Journal on Optimization · doi:10.1137/120891009 · Cited by 1,304
Iterative Water-Filling for Gaussian Vector Multiple-Access Channels
Yu, W., Rhee, W., Boyd, S., & Cioffi, J. M. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.821988 · Cited by 1,026
Technical Note—A General Inner Approximation Algorithm for Nonconvex Mathematical Programs
Marks, B. R., & Wright, G. P. (1978) · Operations Research · doi:10.1287/opre.26.4.681 · Cited by 985
Dynamic Spectrum Management: Complexity and Duality
Luo, Z.-Q., & Zhang, S. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.914876 · Cited by 929
Cited by
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
Sun, Y., Babu, P., & Palomar, D. P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2601299 · Cited by 1,820
Self-citationJoint Optimization of Radio and Computational Resources for Multicell Mobile-Edge Computing
Sardellitti, S., Scutari, G., & Barbarossa, S. (2015) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2015.2448520 · Cited by 891
Self-citationHong, M., Luo, Z.-Q., & Razaviyayn, M. (2016) · SIAM Journal on Optimization · doi:10.1137/140990309 · Cited by 841
NEXT: In-Network Nonconvex Optimization
Lorenzo, P. D., & Scutari, G. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2524588 · Cited by 473
Self-citationGroup sparse regularization for deep neural networks
Scardapane, S., Comminiello, D., Hussain, A., & Uncini, A. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.02.029 · Cited by 457
Hong, M., Razaviyayn, M., Luo, Z.-Q., & Pang, J.-S. (2016) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2481563 · Cited by 447
Self-citationOptimization Methods for Designing Sequences With Low Autocorrelation Sidelobes
Song, J., Babu, P., & Palomar, D. P. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2425808 · Cited by 382
Self-citationDC programming and DCA: thirty years of developments
Le Thi, H. A., & Pham Dinh, T. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1235-y · Cited by 348
Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory
Scutari, G., Facchinei, F., & Lampariello, L. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2637317 · Cited by 314
Self-citationSequence Design to Minimize the Weighted Integrated and Peak Sidelobe Levels
Song, J., Babu, P., & Palomar, D. P. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2510982 · Cited by 312
Self-citationPark, S.-H., Simeone, O., Sahin, O., & Shamai, S. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2280111 · Cited by 290
Distributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86
“The crux of the framework is a general convexification-decomposition technique that hinges on our recent (primal) Successive Convex Approximation (SCA) methods [14], [15], coupled with i) a tacking mechanism that allows every agent i to estimate locally the gradients of other agents’ functions ∑ j =i fj ; and ii) a no…”
MethodSelf-citation
Metadata
- Authors
- Scutari, G., Facchinei, F., Song, P., Palomar, D. P., & Pang, J.-S.
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2014-02
- Volume
- 62
- Issue
- 3
- Pages
- 641-656
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W1974661392
- Cited by
- 338
- References
- 38
- FWCI
- 46.62
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.