Distributed optimization in multi-agent systems: applications to distributed regression

The context for this work is cooperative multi-agent systems (MAS). An agent is an intelligent entity that can measure some aspect of its environment, process information and possibly influence the environment through its action. A cooperative MAS can be defined as a loosely coupled network of agents that interact and cooperate to solve problems that are beyond the individual capabilities or knowledge of each agent. The focus of this thesis is distributed stochastic optimization in multi-agent systems. In distributed optimization, the complete optimization problem is not available at a single location but is distributed among different agents. The distributed optimization problem is additionally stochastic when the information available to each agent is with stochastic errors. Communication constraints, lack of global information about the network topology and the absence of coordinating agents make it infeasible to collect all the information at a single location and then treat it as a centralized optimization problem. Thus, the problem has to be solved using algorithms that are distributed, i.e., different parts of the algorithm are executed at different agents, and local, i.e., each agent uses only information locally available to it and other information it can obtain from its immediate neighbors. In this thesis, we will primarily focus on the specific problem of minimizing a sum of functions over a constraint set, when each component function is known partially (with stochastic errors) to a unique agent. The constraint set is known to all the agents. We propose three distributed and local algorithms, establish asymptotic convergence with diminishing stepsizes and obtain rate of convergence results. Stochastic errors, as we will see, arise naturally when the objective function known to an agent has a random variable with unknown statistics. Additionally, stochastic errors also model communication and quantization errors. The problem is motivated by distributed regression in sensor networks and power control in cellular systems. We also discuss an important extension to the above problem. In the extension, the network goal is to minimize a global function of a sum of component functions over a constraint set. Each component function is known to a unique network agent. The global function and the constraint set are known to all the agents. Unlike the previous problem, this problem is not stochastic. However, the objective function in this problem is more general. We propose an algorithm to solve this problem and establish its convergence.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2010

Author dc:creator

• Srinivasan, Sundhar Ram

Contributors dc:contributor

• Veeravalli, Venugopal V.
• Nedich, Angelia
• Srikant, Rayadurgam
• Meyn, Sean P.
• Jones, Douglas L.

• multi-agent systems
• stochastic optimization
• convex optimization
• distributed optimization
• regression
• distributed regression

Statement dc:rights

• Copyright 2010 Sundhar Ram Srinivasan

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/16105

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/16105