Decentralized control and optimization

Franco Blanchini, University of Udine

Abstract:  We consider a minimum Euclidean norm problem. In particular, we aim at minimizing the Euclidean norm of the m-vector u, which satisifies the equality Bu = w, where B is a matrix and w is an n-vector, and has entries bounded between a minimum and a maximum. Matrix B has a given sparsity structure, namely it has structurally zero entries.
We aim at solving the problem in a (network) decentralized way as follows.
There is a set of control agents associated with the columns of B and a set of information agent associated with the rows of B. The two basic rules of the game are the following.

a) Each control agent j (associated with a column B.j of B) must decide its action based exclusively on the information coming from information agents that correspond to structurally nonzero entries of the column B.j of B.
The agent ignores the number of other control agents, their actions, the columns of B other than its own and vector w.

b) Each information agent i (associated with a row Bi. of B) can measure the effect on the i-th constraint due the actions of the agents corresponding to structurally nonzero entries of the row Bi. of B. In practice, the information agent can measure the violation of the i-th constraint integrated over time.
It ignores the existence of other information agents and of control agents other than those it is connected to.

In the special case of flow networks, B is an incidence matrix. The information agents correspond to nodes (reservoirs) and control agents to arcs (flows). Then each control agent must decide the arc flow, based on the levels of the reservoirs to which it is connected. The information agents, corresponding to reservoirs, are affected only by the control agents corresponding to the incident arcs. Our goal is to find a strategy for the control agents that ensures converge to the optimal solution. As a main result, this problem can be solved exactly by a saturated decentralized strategy, which ensures asymptotic convergence to the constrained flow of minimum norm. We show how this property, introduced in a network--decentralized control context, can be applied to several decentralized optimization problems, such as optimal power generation, decentralized knapsack problems, large scale and distributed minimum norm problems.