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 equation
10.1b equation

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

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.