Optimization of Computer Networks

Chapter 10Dual Gradient Algorithms

10.1 Introduction

In this chapter we present a selected set of case studies to illustrate the so-called dual approach for devising network design algorithms. In brief, a dual approach means that a gradient projection algorithm is applied to find the optimum multipliers of a Lagrange relaxation of the problem, as an indirect form to also find its primal solution. Methods obtained in the case studies are amenable to distributed implementation, and inherit the convergence properties for asynchronous executions and noisy gradient observations from the standard gradient iteration.

Let (10.1) be the primal problem to solve.

10.1a

10.1b

where set represents an arbitrary set of constraints which are not relaxed, are the relaxed constraints and their associated non-negative multipliers. Given a vector of feasible multipliers , the set of associated primal solutions ...