The need for speed: convergence rates and accelerated algorithms for networked optimization.

Mikhael Johansson
Royal Institute of Technology (KTH)

The framework of networked optimization, where decision-makers coordinate their action with only a subset of the other decision-makers, is natural in a variety of coordination and control problem involving multiple agents. Examples include multi-vehicle coordination and the control of large-scale infrastructures such as water and energy distribution networks. Most of the existing techniques for networked optimization are first-order methods, with limited theoretical and practical convergence rates. Although proposals for distributed higher-order methods exist, they typically require a large amount of coordination among agents.

In this talk, we will discuss how multi-step techniques, such as the Polyak's heavy ball method, can be applied to accelerate networked optimization algorithms, resulting in methods with improved convergence rates without the communication penalty of higher-order methods Examples to resource allocation, consensus and network utility maximization will be given. Particular attention is given to step-size rule selection, and the impact of uncertain or misestimated system parameters on the guaranteed speedup. Time permitting, we will also discuss some recent surprising results on topology-dependent convergence rates for networked optimization.

The talk is based on joint work with students and colleagues at KTH and UC Berkeley.

Back to Workshop V: Applications of Optimization in Science and Engineering