Random Block Coordinate Descent Methods for Linearly Constrained Optimization over Networks

Ion Necoara (), Yurii Nesterov () and François Glineur
Additional contact information
Ion Necoara: University Politehnica Bucharest
Yurii Nesterov: Universite Catholique de Louvain

Journal of Optimization Theory and Applications, 2017, vol. 173, issue 1, No 11, 227-254

Abstract: Abstract In this paper we develop random block coordinate descent methods for minimizing large-scale linearly constrained convex problems over networks. Since coupled constraints appear in the problem, we devise an algorithm that updates in parallel at each iteration at least two random components of the solution, chosen according to a given probability distribution. Those computations can be performed in a distributed fashion according to the structure of the network. Complexity per iteration of the proposed methods is usually cheaper than that of the full gradient method when the number of nodes in the network is much larger than the number of updated components. On smooth convex problems, we prove that these methods exhibit a sublinear worst-case convergence rate in the expected value of the objective function. Moreover, this convergence rate depends linearly on the number of components to be updated. On smooth strongly convex problems we prove that our methods converge linearly. We also focus on how to choose the probabilities to make our randomized algorithms converge as fast as possible, which leads us to solving a sparse semidefinite program. We then describe several applications that fit in our framework, in particular the convex feasibility problem. Finally, numerical experiments illustrate the behaviour of our methods, showing in particular that updating more than two components in parallel accelerates the method.

Keywords: Convex optimization over networks; Linear coupled constraints; Random coordinate descent; Distributed computations; Convergence analysis; 90C06; 90C25; 90C35 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-016-1058-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
Working Paper: Random block coordinate descent methods for linearly constrained optimization over networks (2017)
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:joptap:v:173:y:2017:i:1:d:10.1007_s10957-016-1058-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-016-1058-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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