Fully distributed algorithms for convex optimization problems

Year
2007
Type(s)
Author(s)
D. Mosk-Aoyama, T. Roughgarden, D. Shah
Source
Proceedings of International Symposium on distributed computing (Lecture Notes in Computer Science), Volume 4731, pp. 492-499, September 2007.
Url
https://pdfs.semanticscholar.org/a5fa/ae9c818ad666e4aed8f897db3ebaa4965a0b.pdf

We design and analyze a fully distributed algorithm for convex constrained optimization in networks without any consistent naming infrastructure. The algorithm produces an approximately feasible and near-optimal solution in time polynomial in the network size, the inverse of the permitted error, and a measure of curvature variation in the dual optimization problem. It blends, in a novel way, gossip-based information spreading, iterative gradient ascent, and the barrier method from the design of interior-point algorithms.