Distributed optimization - intensive course

During the last couple of years, applied optimization has had a tremendous impact on the development of algorithms for coordination and resource sharing in networks and systems. Examples include multi-robot coordination, distributed estimation, radio resource management in wireless systems, and traffic engineering in data networks. Very quickly, optimization theory has moved from the periphery to the core of many engineering disciplines: classical optimization techniques are being rediscovered and enhanced, and completely new optimization algorithms, tailored to the constraints of networked systems, are being developed. This intensive course attempts to present some of the key techniques for distributed optimization in such systems in a coherent and comprehensible manner.

Lecturers:

Prof. Stephen Boyd, Stanford University
Prof. Mikael Johansson, KTH
Dr. Bo Yang KTH

Schedule

Lecture 1	Introduction, subgradients	Mo 8/2 09-10	F2, Lindstedtv. 26
Lecture 2	Subgradient methods	Mo 8/2 13-15	F2, Lindstedtv. 26
Lecture 3	Decomposition techniques	Tue 9/2 10-12	V2, Teknikringen 76
Lecture 4	Decomposition techniques, Ciruits interpretation	Tue 9/2 13-15	F2, Lindstedtv. 26
Lecture 5	Distributed collaborative optimization	We 10/2 10-12	L1, Drottning Kristinas v. 30
Lecture 6	Non-cooperative optimization and games	We 10/2 13-15	V2, Teknikringen 76
Lecture 7	Non-cooperative games cont'd	Th 11/2 10-12	F2, Lindstedtv. 26
Lecture 8	Dynamics of distributed optimization	Th 11/2 13-15	V2, Teknikringen 76
Lecture 9	Influence of noise and stochastic parameters	Fri 12/2 10-12	K2, Teknikringen 28
Lecture 10	Conclusions	Fri 12/2 13-15	D2, Lindstedtv. 5

Additional material

Many of the slides come from ee364b course at Stanford. At this web site you will find additional slides, additional notes and source code for the examples.
CVX and YALMIP are useful tools for describing and solving convex optimization problems.
Another useful reference for large-scale convex optimization is ee236c at UCLA.

Homework

Handin 1 (due Tuesday morning) Implement a basic subgradient method for solving the following problem:

$mbox{minimize}~sum_{i=1}^m (a_i^T x-b_i)_{+}.$
Here a_i

are the rows of $A in {mathbf R}^{ntimes m}$ , and b_i

the components of $bin mathbf{R}^m$ . If the set of inequalities Axleq b

is feasible, then any feasible

is optimal. If there is no

that satisfies the inequalities, then the optimal

is the one that minimizes the sum of constraint violations. At the bare minimum, implement constant and diminishing stepsizes as well as the Polyak rule. We also encourage you to try the more advanced schemes, such as the “big ball” method and any other method that you can find.

Handin 2 (due Wednesday morning) Today, we want you to solve a multi-aircraft coordination problem, where each aircraft

can be described by a linear dynamical system x_i(t+1) = Ax_i(t)+Bu_i(t), quad t=1, dots, T.

Your task is to find a decomposition-based algorithm for coordinating towards a common target state at time

, i.e. to make sure that
$x_i(T)= x_{f}; forall i$
while satisfying a limitation on the total control energy
$sum_t u_i(t)^T u_i(t) leq u_{max}; forall i$

As an objective, use the quadratic cost function
$mbox{minimize}quad sum_i sum_t x_i(t)^T x_i(t)+ u_i(t)^T u_i(t)$
The optimization variables are the (private) controls u_i

of individual aircrafts, as well as the (public) common terminal state x_f

.

At the bare minimum, derive a solution based on dual decomposition (even this might lead you into some of the fine print in the lectures). You will learn a lot from also trying out primal decomposition, prox decomposition or any other decomposition method you can find.

The following file contains matrices A_i

and

, along with initial states for a four-aircraft example.

Handin 3 Consider a wireless network with a set of mathcal{V=}left{ 1,2,cdots ,leftvert mathcal{V}rightvert right}

mathcal{V=}left{ 1,2,cdots ,leftvert mathcal{V}rightvert right}

mobile stations (players) connecting to a common base station. Each player

aims to tune its transmission power $P_{v}$ within $left[ 0,P_{v}^{max }right]$ to maximize its individual payoff function $w_{v}left( mathbf{P}right)$ , textit{i.e.}
$max_{P_{v}in left[ 0,P_{v}^{max }right] }w_{v}left( mathbf{P}right) , mbox{ }forall vin mathcal{V}.$
$gamma _{v}left( P_{v},mathbf{P}_{-v}right) =frac{G_{v}P_{v}}{ sum_{min mathcal{V},mneq v}G_{m}P_{m}+n_{0}}$ is the signal to interference and noise ratio of player

received at the base station, and $G_{i},iin mathcal{V}$ $n_{0}$ are constants, which are known as channel gain and background noise, respectively. Questions: - If $w_{v}left( mathbf{P}right) =frac{gamma _{v}left( P_{v},% mathbf{P}_{-v}right) }{P_{v}},$ is there any Nash equilibrium in the game? - If $w_{v}left( mathbf{P}right) =frac{gamma _{v}left( P_{v},% mathbf{P}_{-v}right) }{P_{v}}-kappa _{v}P_{v},$ is there any Nash equilibrium in the game?

Handin 4 A set of players (or agents) mathcal{V=}left{ 1,2,cdots,leftvert mathcal{V}rightvert right}

in a fixed, connected and un-directed graph seek to come to a consensus upon a common scalar value by repeatedly interacting with each other. By reaching a consensus, the agreement space is characterized by $x_{1}=x_{2}=cdots =x_{leftvert mathcal{V}rightvert }$ where $x_{v}$ is referred to as the state of player

This common objective can be achieved for each player

by selecting its strategy $x_{v}in mathcal{S}_{v}$ to maximize its local payoff function $w_{v}left( x_{v},x_{-v}right) =-sum_{min mathcal{N}% _{v}}leftVert x_{v}-x_{m}rightVert$ , i.e.
$max_{x_{v}in mathcal{S}_{v}}w_{v}left( x_{v},x_{-v}right)$
where $mathcal{N}_{v}subset mathcal{V}$ is player

's time-invariant neighbor set. Questions: - Discuss whether this game is a potential game? If yes, what is the potential function according to the definition of potential game?

Handin 5 Consider a wireless network with a set of mathcal{V}=left{ 1,2,cdots ,vertmathcal{V}vert right}

mathcal{V}=left{ 1,2,cdots ,vertmathcal{V}vert right}

mobile stations (players) connecting to a common base station. Each player

aims to tune its transmission power $P_{v},$ within $left[ 0,P_{v}^{max }right]$ to maximize its individual payoff function
$w_{v}( mathbf{P}) =-(gamma_{v}( P_{v},mathbf{P}_{-v}) -gamma_{v}^{tgt})^{2}$
where
$gamma_{v}( P_{v},mathbf{P}_{-v}) =frac{G_{v}P_{v}}{sum_{jin mathcal{V},jneq v}G_{j}P_{j}+n_{0}}$
is the SINR, $G_{v}>0$ , is the channel gain of player v, forall vin mathcal{V}

, $gamma^{tgt}>0$ , is the target SINR of player

and $n_{0}>0$ is the background noise. Questions: - Is there any Nash equilibrium in the above power control game? - If there exist some equilibria, can you find a best response update to arrive at the Nash equilibrium and prove its convergence?

Handin 6 Let $Gamma =left[ mathcal{V},left{ mathcal{S}_{v}right} _{vin mathcal{V}},left{ w_{v}right} _{vin mathcal{V}}right]$ be a supermodular game. Please discuss convergence of the following “maximal” best response strategy,
$x_{v}left( k+1right) =max left{ arg _{z_{v}mathcal{in S}% _{v}}w_{v}left( z_{v},x_{-v}left( kright) right) right} ,;forall vin mathcal{V}.qquad mbox{(1)}$
If (1) converges, where does it converge?