Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Queen's University

$30,000.00

Continuous-time distributed optimization and tradeoffs of optimality and heterogeneity

FY 2015-16

Summary
This research program will further contribute to the understanding of the underpinnings of collective behavior and information aggregation in (sub)systems interconnected over large-scale networks by developing mathematical tools for analyzing their stability properties and influencing their behaviors by feedbacks. These phenomena are widespread in a variety of disciplines including engineering systems (e.g., oscillator synchronization, distributed robotic networks, and distributed sensing and control in electrical energy systems), biological systems, and social learning and economics. The diverse nature of interconnections in these systems usually makes it difficult to classify them in any useful manner. One approach is to prescribe the behavior of each individual by using a payoff function which is dependent on the actions taken by neighboring subsystems. Each subsystem then aims to maximize its payoff function. In most engineering scenarios, there is a designer whose objective is to assign appropriate such functions to ensure certain global performances, while still allowing for execution in a decentralized manner. In the first part of the research program, we focus on the so-called distributed optimization problem, where a group of agents aim to maximize a sum of (concave) functions, while each agent has only access to one of these functions. We propose a catalog of provably convergent continuous-time saddle point algorithms for distributed optimization. The novelty of the approach is in its applicability to scenarios where the information flow is unidirectional. Various properties of these algorithms, including robustness and finite-time convergence, will be the subjects of study. Current applications under study include source localization, robust estimation, market design and energy dispatch in power distribution networks, influence-cascade dynamics in competitive economic networks, optimization on manifolds, and online distributed optimization. In the second part, we turn our attention to the issue of scalability of the existing distributed optimization protocols. In particular, most of the existing algorithms rely on estimating the optimal solution using communications between agents. When the optimization variable is the state of a network, such algorithms do not scale well with the size of the network. In order to address this issue, building on the intriguing interplay between the theory of learning in games and systems and control, this research program will propose a catalog of dynamical systems which will capture various instances of strategic interactions over networks. Interestingly, the proposed suite of dynamical systems, inspired by myopic continuous-time set-valued best-response dynamical systems, can be cast as fast converging distributed algorithms which approximate interesting optimization problems. The novel notion of the price of heterogeneity captures the quality of these approximations. The research program is multidisciplinary by its nature and the technical approach combines ideas from optimization, game theory, networks and communications, nonsmooth analysis, stochastic analysis, and control theoretic tools. The broader impacts of the research program on problems in economy, social networks, and biology, along with the algorithmic aspects of this research project will provide a variety of applications with considerable scientific significance, and will be of great interest to various governmental labs, including Environment Canada and National Defence. In addition to promising M.Sc. and Ph.D. theses, the educational component of the project consists of establishing a new research group on Networked Control Systems at Queen's and the design of new undergraduate and graduate courses.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-05387
Name nom
Gharesifard, Bahman
Department département
Mathematics and Statistics
Organization id
29
Institution établissement
Queen's University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2014
Award amount
30000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1510
Committee name en
Electrical and Computer Engineering
Committee name fr
Génie électrique et informatique
Area of application code
1206
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Engineering
Area of application fr
Génie
Research subject code
2509
Research subject group en
Electrical and electronic engineering
Research subject group fr
Génie électrique et électronique
Research subject en
Control systems
Research subject fr
Asservissements
Partie
2
Nb partie
5
Application title
Continuous-time distributed optimization and tradeoffs of optimality and heterogeneity
Keyword
NSERC
Application summary
This research program will further contribute to the understanding of the underpinnings of collective behavior and information aggregation in (sub)systems interconnected over large-scale networks by developing mathematical tools for analyzing their stability properties and influencing their behaviors by feedbacks. These phenomena are widespread in a variety of disciplines including engineering systems (e.g., oscillator synchronization, distributed robotic networks, and distributed sensing and control in electrical energy systems), biological systems, and social learning and economics. The diverse nature of interconnections in these systems usually makes it difficult to classify them in any useful manner. One approach is to prescribe the behavior of each individual by using a payoff function which is dependent on the actions taken by neighboring subsystems. Each subsystem then aims to maximize its payoff function. In most engineering scenarios, there is a designer whose objective is to assign appropriate such functions to ensure certain global performances, while still allowing for execution in a decentralized manner. In the first part of the research program, we focus on the so-called distributed optimization problem, where a group of agents aim to maximize a sum of (concave) functions, while each agent has only access to one of these functions. We propose a catalog of provably convergent continuous-time saddle point algorithms for distributed optimization. The novelty of the approach is in its applicability to scenarios where the information flow is unidirectional. Various properties of these algorithms, including robustness and finite-time convergence, will be the subjects of study. Current applications under study include source localization, robust estimation, market design and energy dispatch in power distribution networks, influence-cascade dynamics in competitive economic networks, optimization on manifolds, and online distributed optimization. In the second part, we turn our attention to the issue of scalability of the existing distributed optimization protocols. In particular, most of the existing algorithms rely on estimating the optimal solution using communications between agents. When the optimization variable is the state of a network, such algorithms do not scale well with the size of the network. In order to address this issue, building on the intriguing interplay between the theory of learning in games and systems and control, this research program will propose a catalog of dynamical systems which will capture various instances of strategic interactions over networks. Interestingly, the proposed suite of dynamical systems, inspired by myopic continuous-time set-valued best-response dynamical systems, can be cast as fast converging distributed algorithms which approximate interesting optimization problems. The novel notion of the price of heterogeneity captures the quality of these approximations. The research program is multidisciplinary by its nature and the technical approach combines ideas from optimization, game theory, networks and communications, nonsmooth analysis, stochastic analysis, and control theoretic tools. The broader impacts of the research program on problems in economy, social networks, and biology, along with the algorithmic aspects of this research project will provide a variety of applications with considerable scientific significance, and will be of great interest to various governmental labs, including Environment Canada and National Defence. In addition to promising M.Sc. and Ph.D. theses, the educational component of the project consists of establishing a new research group on Networked Control Systems at Queen's and the design of new undergraduate and graduate courses.