Networked optimization: models and novel algorithms

Abstract:

Flexible information networks now allow real-time data gathering from truly large-scale dynamic systems. This makes it tempting to try to control, coordinate and optimize wide-area systems, such as complete industrial processes, infrastructures and distribution networks. To avoid excessive communication and the single point-of failure of centralized approaches, it is natural to look for distributed optimization solutions. However, in-network decision making has often to be implemented on small embedded processors with very limited memory and restricted computational capabilities. Furthermore, it is desirable that the traffic for coordinating nodes is minimal and that the communication can be done in an energy-efficient way. Finally, several emerging applications require that nodes do not reveal “private” information when coordinating their decisions. Bringing state-of-the art optimization solvers to this resource-constrained environment clearly is a grand challenge.

Recently, a large research effort has been devoted to understanding distributed quadratic programming problems and the properties of the associated distributed averaging algorithms. However, moving beyond the least-squares framework offers distinctive advantages in applications and the development of a generic optimization component for embedded networked processors could potentially have a very broad engineering applicability. In this talk, we report our recent progress on distributed optimization for networked embedded systems. This includes a randomized incremental subgradient method which conforms to a nearest neighbor communication pattern; an ``any-time´´ optimization algorithm that combines subgradient steps and consensus iterations which converges asymptotically yet ensures that nodes have reasonably similar ideas of the global decision variable even if the algorithm is terminated prematurely; and, finally, an algorithm for non-smooth optimization which maintains a given network-wide resource budget at all times.