Decentralized optimization with appliation to flow control

Abstract

Decentralized computation is considered an important design goal of large systems. This may be to increase the reliability of the system or to reduce the computation time, and in some situations, it is a necessity. Decentralization can arise in terms of computation as well as information associated with the system. Two important issues here are the feasibility of decentralization under certain constraints and designing decentralized algorithms given a particular problem and the information and computational constraints. This thesis concerns decentralized optimization and addresses both of these issues. As an example of a practical situation wherein the above analysis can be useful, we consider the flow control problem in communication networks. The different nodes in the communication network may represent the processors of the decentralized system where computations are to be performed. The problem is to choose input rates for virtual circuits in such a way that a global function is optimized. Because of communication delays, each node in the network has incomplete information about the network and has to compute its rate of transmission. Hence, there is a need for decentralized optimization. The existing literature addresses the decentralizability problem for the case of optimization in computer networks with specific information structures. This work brings out necessary and sufficient conditions for a function to be optimized when certain information and communication constraints are present. are to be satisfied. The objective function can be a scalar valued or a vector valued function. The analysis is done separately for the above cases. When the given objective function cannot be optimized under the information constraints the approximate algorithms are suggested with the allowed error. Another suggestion in such a case is to enlarge the information structure by providing additional information. When the decentralizability conditions are satisfied, algorithms are suggested to compute the optimal points. The convergence of these algorithms can be established using the existing results for optimization algorithms. In the case of vector valued optimization, though many solution concepts can be defined { note that usual optimal point cannot be defined for vector valued functions) the Pareto optimal points are considered here. The decentralized algorithms can be implemented in a synchronous as well as asynchronous mode. Whenever possible the asynchronous version of the algorithms are described and their convergence proofs indicated. We also consider the situation, where in principle, with the given information and communication requirements a function can be optimized but the available optimization algorithms require more information. For such a case, we devise estimation schemes to estimate certain parameters needed for these algorithms from the information supplied. We apply these estimators on several algorithms and show by simulations that they can provide near optimal points in flow control problems.