O'Reilly logo

Optimization of Computer Networks by Pablo Pavón Mariño

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required