Description
Cumulative Reading Assignments:
• Read Boyd & Vandenberghe, Sections 2.1-2.3, 2.5-2.6
• Read Boyd & Vandenberghe, Sections 3.1-3.2, 3.4
• Read Boyd & Vandenberghe, Sections 4.1-4.2
• Read Boyd & Vandenberghe, Sections 5.1-5.6
• Read Boyd & Vandenberghe, Sections 9.1-9.5
• Read Bertsekas & Tsitsiklis, Sections 3.1.1, 3.2.1-3.2.3, 3.3.1-3.3.3
(1) Consider a communication network with L links that is operating in a time-slotted manner. Each link l has an associated set of interfering neighbors given by N l
. A constant
probability vector p := (pl)l
is to be assigned to the links so that in each slot link l will
attempt a packet transmission with its assigned probability pl ∈ [0, 1] independently. The
transmission of link l succeeds in a slot only if it transmits and none of its interfering
neighbor does.
(a) Express the average rate of success of link l transmissions, denoted as xl(p), as a
function of p.
(b) Suppose the utility that link l receives from a successful transmission rate of xl
is
given by ωl
log(xl) for a given constant ωl > 0. Then, express the total utility maximization
problem as a convex problem, justifying its convexity.
(c) Solve the problem of part (b) to express the optimal choice of p
∗ as a function of
the weight vector (ωl)l
. Comment on the result.
(2) Consider a network represented by a graph G = (N ,L), where N is the set of nodes,
L is the set of directed links. Let x = (x
d
s
) be the rate of flow from source node s to
destination d, and Usd(·) be the utility function associated with that flow. There are no
apriori set routes for the communication.
Each node i ∈ N has a maximum power constraint P
max
i
that is available for transmission
over its outgoing links. For each link (i, j), there is a noise level given by Nij (which
also accounts for the channel gain between nodes i and j). Then, the rate achieved by
transmitting data at rate Pij over link (i, j) ∈ L is given by
Rij (Pij ) = log(1 + Pij/Nij ).
(Note that the formulation is free from interference).
(a) Formulate the joint congestion control for utility maximization and link rate allocation for optimal routing problem under the power constrained network setting described
above. Clearly describe each new term and indicate what each constraint is due to.
(b) Write the Lagrangian function and develop the gradient-based algorithm for the
problem designed in part (a) (You can leave some components of the algorithm description
as maximizations/minimizations).
(3) In PS2, Problem 6 (referring to Boyd & Vandenberghe 4.62), you have confirmed the
convexity of the optimization problem (with known positive constants (αi)i and (βi)i):
maximize Xn
i=1
αiWi
log
1 +
βiPi
Wi
subject to
P
Pi ≥ 0, Wi ≥ 0, ∀i
n
P
i=1 Pi ≤ Ptot
n
i=1 Wi = Wtot
Now, associate a Lagrange multiplier µ only with the inequality constraint Pn
i=1 Pi ≤ Ptot
and develop the associated gradient method that clearly describes the update rule for
{µ
(t)}t as well as the power and bandwidth allocations in each step.
(4) Consider a single discrete-time queue with a service process S(t) = Bernoulli(µ) for some
µ ≤ 1, i,e, P(S(t) = 1) = 1 − P(S(t) = 0) = µ, and an arrival process A(t) that follows
the following congestion control rule:
P(A(t) = 1| Q(t) = q) = 1 − P(A(t) = 0| Q(t) = q) = 1
(1 + q)
, ∀q ∈ {0, 1, 2, · · · }
where Q(t) is the queue-length at time t that evolves as
Q(t + 1) = (Q(t) + A(t) − S(t))+.
(Note that a packet can arrive and leave the queue in the same time slot).
(a) Draw the Markov Chain diagram of Q(t) showing the transition probabilities.
(b) Using Foster-Lyapunov criterion, find the range of µ for which the Markov Chain
is positive recurrent (with proof).
(c) For any µ in the range found in (b), find the stationary distribution π
∗ = (π
∗
i
)∞
i=0.
Do not leave terms in infinite sums. (Hints: Write global balance equations for sets of
states {0}, {0, 1}, {0, 1, 2}, so on; and recall that X∞
k=0
ρ
k
k!
= e
ρ
).
(5) (Programming Exercise) In this problem, we will consider fair allocation of a shared
resource among users in the context of telecommunication networks. Consider a network
consisting of N users.
User i derives a utility of Ui(xi) by sending data at rate xi
. We assume that Ui
is an
increasing, continuously differentiable function. The service rate to user i is ri ≥ 0. In
order for stability, each user must send data at a rate less than its service rate, i.e., xi ≤ ri
.
Due to interference between links and limited capacity of each link, the service rate vector
r must satisfy the following constraint:
X
N
i=1
ri
ci
≤ 1 (1)
for given constants (ci)i
, which are defined by the network. The objective in this problem
is to maximize utility under these constraints:
max
x
X
N
i=1
Ui(xi)
subject to xi ≤ ri
, i = 1, . . . , N,
X
N
i=1
ri
ci
≤ 1
(2)
Assume that Ui(x) = log(x) for all i.
1. (Dual Algorithm) Associate each constraint (2) with Lagrange multiplier qi ≥ 0 and
write the Lagrangian of the primal problem L(x, r, q). Then, for given q, find the
optimum x and r by solving the following problems:
x
∗ = arg max
x
L(x, r, q) (3)
r
∗ = arg max
r:
P
i
ri
ci
≤1
L(x, r, q) (4)
Note that maximization over x and r are decoupled from each other, and the dual
function is D(q) = L(x
∗
, r∗
, q).We will use gradient descent to minimize D(q):
qi(t) = (qi(t − 1) − γ
d
dqi
D(q(t)))+ (5)
In summary, at stage t of the Dual Algorithm, for given q = q(t − 1), you will first
find x(t) = x
∗ and r(t) = r
∗ as the optimizers of problems (3) and (4), respectively.
Then you will update the dual variable as in (5).
(a) Solve the problems (3), (4), (5), and find the explicit rules for x(t), r(t) and q(t).
(Hint: Exploit the additive structure of Ui and thus decoupling of (xi)i and r. Also,
for finding r
∗
, observe that only one user receives a non-zero service rate at each
time slot. Which one?)
(b) Implement the Dual Algorithm for N = 2 and Ui(x) = log(x), ∀i. Let the initial
queue-lengths be q1(0) = q2(0) = 1 and (c1, c2) = (1, 2). Show the evolution of
(xi(t))i and (qi(t))i
. In a two-dimensional plot, show the trajectory of (x1(t), x2(t)).
(c) How can we interpret the dual variable qi(t)? How does its increase affect xi(t)
and ri(t)? (Hint: Identify an arrival and a service process in the explicit form of
(5).)
2. (Primal-Dual Algorithm) In Primal-Dual Algorithm, instead of finding xi(t) and at
one step as in (3), we will use gradient ascent. So, for given q(t − 1),
xi(t) = (xi(t − 1) + α
d
dxi
L(x, r, q(t − 1)))+ (6)
for all i = 1, 2, . . . , N. The rest of the algorithm is identical to Dual Algorithm.
(a) Find the update rules for (xi(t))i
.
(b) Implement the Primal-Dual Algorithm for N = 2 and Ui(x) = log(x), ∀i. Let the
initial queue-lengths be q1(0) = q2(0) = 1 and (c1, c2) = (1, 2). Show the evolution of
(xi(t))i and (qi(t))i
. In a two-dimensional plot, show the trajectory of (x1(t), x2(t)).
(c) Compare the performances of Dual and Primal-Dual Algorithm. Which one
provides faster convergence? Explain why.
3. (Heavy-Ball Method) For (c1, c2) = (1, 2), N = 2 and Ui(x) = log(x), Heavy-Ball
Method works as follows:
• Choose parameters K > 0 and β ∈ [0, 1). Set t = 0.
• Let q1(0) = q2(0) = 0. Defined the weights for each queue wi(0) = wi(−1) =
0, i = 1, 2.
• For t ≥ 1, do the following at each iteration:
∗ r(t) = arg max
r:
P
i
ri
ci
≤1
P
i wi(t)ri
. (Hint: Only one user receives a non-zero service
rate at each time slot. Which one?)
∗ xi(t) = min{U
′−1
i
(
wi(t)
K
), xmax}.
∗ qi(t + 1) = (qi(t) − ri(t) + xi(t))+.
∗ Let ∆qi(t) = qi(t + 1) − qi(t). Then, update the weights as follows:
wi(t + 1) =
wi(t) + ∆qi(t) + β(wi(t) − wi(t − 1))+
(7)
where x
max is a sufficiently large constant.
(a) Fix β = 0.5 and K = 100, and implement the Heavy-Ball Method described
above. Show the evolution of (xi(t))i and (qi(t))i
. In a two-dimensional plot, show
the trajectory of (x1(t), x2(t)).
(b) For fixed β = 0.5, increase K and observe how the total utility changes after a
sufficiently long time for increasing K.
(c) Compare the performance of Heavy-Ball Method with the algorithms implemented previously. Which one converges fastest? Explain why.
