Files in this item
Files  Description  Format 

application/pdf Jayash_Koshal.pdf (1MB)  (no description provided) 
Description
Title:  Distributed algorithms for networked multiagent systems: optimization and competition 
Author(s):  Koshal, Jayash 
Director of Research:  Nedich, Angelia; Shanbhag, Vinayak V. 
Doctoral Committee Chair(s):  Nedich, Angelia 
Doctoral Committee Member(s):  Shanbhag, Vinayak V.; Pang, JongShi; Hajek, Bruce 
Department / Program:  Industrial and Enterprise Systems Engineering 
Discipline:  Industrial Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Distributed optimization
Distributed algorithms Variational Inequalities Stochastic Approximation Aggregative games Multiuser optimization 
Abstract:  This thesis pertains to the development of distributed algorithms in the context of networked multiagent systems. Such engineered systems may be tasked with a variety of goals, ranging from the solution of optimization problems to addressing the solution of variational inequality problems. Two key complicating characteristics of multiagent systems are the following: (i) the lack of availability of systemwide information at any given location; and (ii) the absence of any central coordinator. These intricacies make it infeasible to collect all the information at a location and preclude the use of centralized algorithms. Consequently, a fundamental question in the design of such systems is the need for developing algorithms that can support their functioning. Accordingly, our goal lies in developing distributed algorithms that can be implemented at a local level while guaranteeing a global systemlevel requirement. In such techniques, each agent uses locally available information, including that accessible from its immediate neighbors, to update its decisions, rather than availing of the decisions of all agents. This thesis focuses on multiagent systems tasked with the solution of three sets of problems: (i) convex optimization problems; (ii) Cartesian variational inequality problems; and (iii) a subclass of Nash games. In the first part of this thesis, we consider a multiuser convex optimization problem. Traditionally, a multiuser problem is a constrained optimization problem characterized by a set of users (or agents). Such problems are characterized by an objective given by a sum of userspecific utility functions, and a collection of separable constraints that couple user decisions. We assume that userspecific utility information is private while users may communicate values of their decision variables. The multiuser problem is to maximize the sum of the usersspecific cost functions subject to the coupling constraints, while abiding by the informational requirements of each user. In this part of the thesis, we focus on generalizations of convex multiuser optimization problems where the objective and constraints are not separable by user and instead consider instances where user decisions are coupled, both in the objective and through nonlinear coupling constraints. To solve this problem, we consider the application of distributed gradientbased algorithms on an approximation of the multiuser problem. Such an approximation is obtained through a regularization and is equipped with bounds of the difference between the optimal function values of the original problem and its regularized counterpart. In the algorithmic development, we consider constant stepsize primaldual and dual schemes in which the iterate computations are distributed naturally across the users, i.e., each user updates its own decision only. We observe that a generalization of this result is also available when users choose their stepsize and regularization parameters independently from a prescribed range. The second part of this thesis is devoted to the solution of a Cartesian variational inequality (VI) problem. A Cartesian VI provides a unifying framework for studying multiagent systems including regimes in which agents either cooperate or compete in a Nash game. Under suitable convexity assumptions, sufficiency conditions of such problems can be cast as a Cartesian VI. We consider a monotone stochastic Cartesian variational inequality problem that naturally arise from convex optimization problems or a subclass of Nash games over continuous strategy sets. Almost sure convergence of standard implementations of stochastic approximation rely on strong monotonicity of the mappings arising in such variational inequality problems. Our interest lies in weakening this requirement and this motivates the development of distributed iterative stochastic approximation algorithms. We introduce two classes of stochastic approximation methods, each of which requires exactly one projection step at every iteration, and provide convergence analysis for them. Of these, the first is a stochastic iterative Tikhonov regularization method which necessitates the update of regularization parameter after every iteration. The second method is a stochastic iterative proximalpoint method, where the centering term is updated after every iteration. Conditions are provided for recovering global convergence in limited coordination extensions of such schemes where agents are allowed to choose their stepsize sequences, regularization and centering parameters independently, while meeting a suitable coordination requirement. We apply the proposed class of techniques and their limited coordination versions to a stochastic networked rate allocation problem. The focus of the third part of the thesis is on a class of games, termed as aggregative games, being played over a networked system. In an aggregative game, an agent's objective function is coupled across agents through a function of the aggregate of all agents decisions. Every agent maintains an estimate of the aggregate and agents exchange this information over a connected network. We study two classes of distributed algorithm for information exchange and computation of equilibrium. The first method, a diffusionbased algorithm, operates in a synchronous setting which can contend with timevarying connectivity of the underlying network graph model. The second method, a gossipbased distributed algorithm, is inherently asynchronous and is applicable when the network is static. Our primary emphasis is on proving the convergence of these algorithms under an assumption of a diminishing (agentspecific) stepsize sequence. Under standard conditions, we establish the almostsure convergence of these algorithms to an equilibrium point. Moreover, we also develop and analyze the associated error bounds when a constant stepsize (userspecific) is employed in the gossipbased method. Finally, we present numerical results to assess the performance of the diffusion and the gossip algorithm for a class of aggregative games for various network models and sizes. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42298 
Rights Information:  Copyright 2012 Jayash Koshal 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Industrial and Enterprise Systems Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois