Chapter 8Gradient Algorithms in Network Design

8.1 Introduction

In this chapter, we introduce the application of gradient methods to network design problems. Most of these problems, like congestion control or fast capacity allocation in wireless networks, involve a potentially large amount of loosely coupled elements that operate more or less independently. Then, there is no possibility of having a central decision unit that receives all the problem inputs, implements a sophisticated algorithm and returns the outputs to the network nodes that have to apply them. For these important cases, we pursue algorithms where each element can proceed to make decisions on its own, coordinated by a small amount of signaling information. As we will see, gradient algorithms are a strong theoretical tool that permits creating such schemes, with convergence guarantees.

We concentrate on constrained convex problems of the form:

where c8-math-0002 is a vector in c8-math-0003, c8-math-0004 is convex in c8-math-0005, and is an arbitrary closed convex ...

Get Optimization of Computer Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.