Change search
ReferencesLink to record
Permanent link

Direct link
On Distributed Optimization in Networked Systems
KTH, School of Electrical Engineering (EES), Automatic Control.
2008 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Numerous control and decision problems in networked systems can be posed as optimization problems. Examples include the framework of network utility maximization for resource allocation in communication networks, multi-agent coordination in robotics, and collaborative estimation in wireless sensor networks (WSNs). In contrast to classical distributed optimization, which focuses on improving computational efficiency and scalability, these new applications require simple mechanisms that can operate under limited communication. In this thesis, we develop several novel mechanisms for distributed optimization under communication constraints, and apply these to several challenging engineering problems.

In particular, we devise three tailored optimization algorithms relying only on nearest neighbor, also known as peer-to-peer, communication. Two of the algorithms are designed to minimize a non-smooth convex additive objective function, in which each term corresponds to a node in a network. The first method is an extension of the randomized incremental subgradient method where the update order is given by a random walk on the underlying communication graph, resulting in a randomized peer-to-peer algorithm with guaranteed convergence properties. The second method combines local subgradient iterations with consensus steps to average local update directions. The resulting optimization method can be executed in a peer-to-peer fashion and analyzed using epsilon-subgradient methods. The third algorithm is a center-free algorithm, which solves a non-smooth resource allocation problem with a separable additive convex objective function subject to a constant sum constraint.

Then we consider cross-layer optimization of communication networks, and demonstrate how optimization techniques allow us to engineer protocols that mimic the operation of distributed optimization algorithms to obtain an optimal resource allocation. We describe a novel use of decomposition methods for cross-layer optimization, and present a flowchart that can be used to categorize and visualize a large part of the current literature on this topic. In addition, we devise protocols that optimize the resource allocation in frequency-division multiple access (FDMA) networks and spatial reuse time-division multiple access (TDMA) networks, respectively.

Next we investigate some variants of the consensus problem for multi-robot coordination, for which it is usually standard to assume that agents should meet at the barycenter of the initial states. We propose a negotiation strategy to find an optimal meeting point in the sense that the agents' trajectories to the meeting point minimize a quadratic cost criterion. Furthermore, we also demonstrate how an augmented state vector can be used to boost the convergence rate of the standard linear distributed averaging iterations, and we present necessary and sufficient convergence conditions for a general version of these iterations.

Finally, we devise a generic optimization software component for WSNs. To this end, we implement some of the most promising optimization algorithms developed by ourselves and others in our WSN testbed, and present experimental results, which show that the proposed algorithms work surprisingly well.

Place, publisher, year, edition, pages
Stockholm: KTH , 2008. , x, 188 p.
Trita-EE, ISSN 1653-5146 ; 2008:065
Keyword [en]
convex optimization, resource allocation, networked systems, peer-to-peer, distributed optimization
National Category
Telecommunications Control Engineering
URN: urn:nbn:se:kth:diva-9801ISBN: 978-91-7415-190-9OAI: diva2:133093
Public defence
2009-01-30, F3, Lindstedtsvägen 26, Stockholm, 13:15 (English)
QC 20100813Available from: 2009-01-12 Created: 2009-01-07 Last updated: 2010-08-13Bibliographically approved

Open Access in DiVA

fulltext(3266 kB)3892 downloads
File information
File name FULLTEXT01.pdfFile size 3266 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Johansson, Björn
By organisation
Automatic Control
TelecommunicationsControl Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 3892 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1680 hits
ReferencesLink to record
Permanent link

Direct link