HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Topics in Control Theory
May 27 - June 13, 2014


Jorge Cortes (University of California, San Diego)
http://carmenere.ucsd.edu/jorge/

Distributed Coverage Optimization

This talk presents a class of coverage optimization problems that find application in optimal deployment of robotic networks and distributed spatial estimation. Robotic sensors can service events that occur in a spatial domain, improve the efficiency of data collection, adapt to changes in the environment, and provide a robust response to individual failures. We formalize the coverage task using tools from geometric optimization and computational geometry. A careful analysis of the resulting utility functions leads us to propose various gradient descent algorithms for distributed optimization. The resulting closed-loop behavior is adaptive, distributed, verifiably correct, and amenable to asynchronous implementation. Our analysis of these problems is based on concepts and methods from systems and control, distributed and geometric optimization, and facility location.

Robert McCann (University of Toronto)
http://www.math.toronto.edu/mccann/

Optimal Transportation and Applications to Economic Theory

Keywords of the presentation: optimal transportation, infinite-dimensional linear programming duality, Monge-Ampere type equations, curvature, stable matching, principal-agent, asymmetric information

Optimal transportation has enjoyed a mathematical renaissance over the last twenty-five years, weaving together threads from analysis, geometry, partial differential equations and dynamical systems. In the first lecture we introduce these mathematical developments, focusing particularly on duality theory, regularity questions, and connections to different notions of curvature in differential geometry and topology. The second lecture will concentrate on different applications to economic theory: stable matching problems, optimal decision making facing informational asymmetries, and equilibria for hierarchical multi-stage decision problems in multidimensional settings.

A. Stephen Morse (Yale University)

Control of Rigid Formation

We will review several recent results concerned with the maintenance of formations of mobile autonomous agents {eg robots} based on the idea of a rigid framework. We will talk briefly about certain classes of “directed” formations for which there is a moderately complete methodology. We then turn to “undirected” formations which is the main focus of this presentation. By an undirected rigid formation of mobile autonomous agents is meant a formation based on “graph rigidity” in which each pair of “neighboring” agents i and j is responsible for maintaining the prescribed distance dij between them. Recent research by several different groups has led to the development of an elegant potential function based theory of formation control which provides gradient laws for asymptotically stabilizing a large class of rigid, undirected formations in two-dimensional space assuming all agents are described by kinematic point models. This particular methodology is perhaps the most comprehensive currently in existence for maintaining undirected formations based on graph rigidity. The main purpose of this talk is to explain what happens if neighboring agents i and j using such gradient controls have slightly different understandings of what the desired distance dij between them is suppose to be. The question is relevant because no two positioning controls can be expected to move agents to precisely specified positions because of inevitable imprecision in the physical comparators used to compute the positioning errors. The question is also relevant because it is mathematically equivalent to determining what happens if neighboring agents have differing estimates of what the actual distance between them is. In either case, what one would hope for would be a gradual distortion of the formation from its target shape as discrepancies in desired or sensed distances increase. While this is observed for the gradient laws in question, something else quite unexpected happens at the same time. In this talk we will describe what occurs and explain why. The robustness issues raised here have broader implications extending well beyond formation maintenance to the entire field of distributed optimization and control. In particular, this research illustrates that when assessing the efficacy of a particular distributed algorithm, one must consider the consequences of distinct agents having slightly different understandings of what the values of shared data between them is suppose to be. For without the protection of exponential stability/convergence, it is likely that such discrepancies will cause significant misbehavior to occur.

A. Stephen Morse (Yale University)
Angelia Nedich (University of Illinois at Urbana-Champaign)
http://ise.illinois.edu/directory/faculty/angelia

Week 2: Control of Networked and Distributed Systems

Over the past decade there has been growing in interest in distributed optimization and control problems of all types. Among these are consensus and flocking problems, constrained consensus problems, distributed optimization problems, the distributed optimal coverage problem, distributed averaging problems, and distributed formation control problems. The broad aim of these lectures is to explain what these problems are and to discuss their solutions. Related concepts from spectral graph theory, rigid graph theory, nonhomogeneous Markov chain theory, stability theory, optimization theory, and linear system theory will be covered.

A. Stephen Morse will discuss "Consensus, Distributed Averaging & Formation Control"

Angela Nedich will lecture on "Distributed Optimization over Networks"

A. Stephen Morse (Yale University)

Flocking and Consensus

We will present graph-theoretic results appropriate for the analysis of a variety of consensus problems cast in dynamically changing environments. The concepts of rooted, strongly rooted, and neighbor-shared graphs will be defined, and conditions will be derived for compositions of sequences of directed graphs to be of these types. As an illustration of the use of the concepts covered, graph theoretic conditions will be derived which address the convergence question for the leaderless version of the widely studied flocking problem. We will also explain how to use these graph-theoretic constructions to address modified versions of the flocking problem in which there are measurement delays, asynchronous events, or a group leader. In all three cases the conditions under which consensus is achieved prove to be almost the same as the conditions under which consensus is achieved in the synchronous, delay-free, leaderless case.

A. Stephen Morse (Yale University)

Distributed Averaging and Gossiping

One particular type of consensus process which has received much attention lately is called “distributed averaging.” By the distributed averaging problem is meant the problem of computing the average value of a set of numbers possessed by the agents in a distributed network using only communication between neighboring agents. Gossiping is a well known approach to the problem which seeks to iteratively arrive at a solution by allowing each agent to interchange information with at most one neighbor at each iterative step. Crafting a gossiping protocol which accomplishes this is challenging because gossiping is an inherently collaborative process which can lead to deadlock unless careful precautions are taken to ensure that it does not. The actual sequence of gossip pairs which occurs during a specific gossiping process might be determined either probabilistically or deterministically, depending on the problem of interest. It is the latter type of process to which this talk is addressed.

Angelia Nedich (University of Illinois at Urbana-Champaign)
http://ise.illinois.edu/directory/faculty/angelia

Distributed Optimization over Networks


Angelia Nedich (University of Illinois at Urbana-Champaign)
http://ise.illinois.edu/directory/faculty/angelia

Distributed Optimization over Networks


Angelia Nedich (University of Illinois at Urbana-Champaign)
http://ise.illinois.edu/directory/faculty/angelia

Distributed Optimization Over Networks


Angelia Nedich (University of Illinois at Urbana-Champaign)
http://ise.illinois.edu/directory/faculty/angelia

Distributed Optimization over Networks

The advances in wired and wireless technology necessitated the development of theory, models and tools to cope with new challenges posed by large-scale optimization problems over networks. The classical optimization works under the premise that all problem data is available to some central entity. This premise does not apply to large networked systems where typically each agent (node) in the network has access to its private local information and has a local view of the network only. The lectures will cover the development of such distributed computational models for time-varying networks, both deterministic and stochastic. For each of these network dynamics, distributed algorithms for convex constrained minimization and Nash-equilibrium problems will be considered including direct primal methods and primal-dual methods, including their extensions for solving the stochastic counterparts of the aforementioned problems. The development of these methods combines optimization techniques with graph theory and the non-negative matrix theory, which model the network aspect. The lectures will provide some basic background theory on graphs, graph Laplacians and their properties, and the convergence results for stochastic matrix sequences. Using the graph models and optimization techniques, the convergence and convergence rate analysis of the methods will be presented, of which the convergence rate results will demonstrate the dependence of the method’s performance with respect to the problem and the network properties, such as the network capability to diffuse the information.

Adam Oberman (McGill University)
http://wiki.math.mcgill.ca/doku.php/personal/staff/aoberman/home

Convergent Finite Difference Solvers for the Monge-Ampère Equation with Optimal Transportation Boundary Conditions

Keywords of the presentation: Partial Differential Equations, Optimal Transportation, Monge-Ampere, Finite Difference Method, viscosity solutions

The Optimal Transportation problem with quadratic cost can be solved via the elliptic Monge-Ampère Partial Differential Equation (PDE) with nonlocal boundary conditions. Up until now, building numerical solutions for the Monge-Ampère PDE has been a challenge, even with Dirichlet boundary conditions.

Indirect methods, such at the fluids reformulation by Brenier-Benamou, as possible, but a direct solver is preferable. Recently several groups of researchers have proposed numerical schemes. Unfortunately these schemes fail to converge, or converge only in the case of smooth solutions. I'll show how naive schemes can work well for smooth solutions, but break down in the singular case. This makes having a convergent scheme even more important.

Starting with the Dirichlet problem, I will present a finite difference scheme which is the only scheme proven to converge to weak (viscosity) solutions. Building on the original discretization, I'll describe modifications which improve the accuracy and solution speed. Finally, I will show how to solve the problem with Optimal Transportation boundary conditions.

This is joint work with Jean-David Benamou and Brittany Froese.

Alex Olshevsky (University of Illinois at Urbana-Champaign)
https://publish.illinois.edu/aolshevsky/

Convergence Rates in Distributed Consensus & Averaging

We discuss the problem of bounding worst-case convergence rates in distributed consensus and averaging. The presentation will include a self-contained proof of the exponential speedup in worst case convergence speed which comes from choosing the so-called ”Metropolis weights” over the naive equal-neighbors choice in consensus. We will emphasize the link between consensus convergence speed and Markov chain intersection times, and the ability to derive bounds on consensus speed by arguing combinatorially about the latter.

Pablo A. Parrilo (Massachusetts Institute of Technology)
http://www.mit.edu/~parrilo/
Ben Recht (University of California, Berkeley)

Week 1: Optimization and Control: a Convex Perspective

In this course we will present a unified perspective on recent developments in optimization and control theory. We will focus on convex methods, and their applications in control and dynamical systems, estimation, system identification, and machine learning. We will make particular emphasis on computational methods, duality as suboptimality or infeasibility certificates, and focus on the exciting developments that have occurred in the last few years, including convex relaxations of combinatorial optimization problems, algebraic methods such as sum-of-squares, and applications to sparsity and rank minimization problems.

The following topics will be covered:

Introduction to dynamical systems. First-order methods for optimization. Semidefinite programming and sum of squares techniques. Solvers for semidefinite programs. Lyapunov functions, KYP lemma, analysis via integral quadratic constraints (IQCs). Sparse approximation approaches to estimation, system identification, and machine learning

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html
Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Week 3: Optimal Mass Transport and Distributed Systems

Allen Tannenbaum will be speaking on the theme of Optimal Mass Transport for Problems in Systems, Control, and Signal Processing. The lectures will be based on a number of published papers as well as lecture notes. He will lead participants through basic methods in the calculus of variations for the classical solution of the Monge-Kantorovich problem as well as the Monge-Ampere equation. He will then describe some newer, partial differential equation approaches. This will lead to a Riemannian structure on spaces of probability densities that allows one in turn to define a notion of curvature on rather general metric measure spaces. Applications to medical image processing, signal processing, control, and large networks will be provided.

Svetlozar Rachev will speak on the theme of Monge-Kantorovich Mass Transference Problem and Theory of Probability Metrics. The Monge-Kantorovich and the Kantorovich-Rubinstein problems are introduced and illustrated in a one-dimensional and multidimensional setting. These problems - more commonly referred to as the mass transportation and mass transshipment problems, respectively - are abstract formulations of optimization problems. Although the applications are important in areas such as job assignments, classification problems, and best allocation policy, our purpose will be their application to the Theory of Probability Metrics (TPM).

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html

Glivenko-Cantelli Functional Limit Theorem and Bernstein-Kanttorovich Invariance Pronciple

Day 3: Fortet-Mourier, Varadarajan, and Wellner Theorems, Functional Limit Theorem and Bernstein-Kanttorovich Invariance Pronciple

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html

Generalized Kantorovich and Kantorovich-Rubinstein Functionals and K-minimal Metrics

Day 2: Relations between Multidimensional Kantorovich and Strassen Theorem: Convergence of Minimal Metrics and Minimal distances

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html

Theory of Probability Metrics

Day 4: Primary, Simple, and Compound Probability Distances and Minimal and Maximal Distances and Norms; Structural Classification of Probability Distances - Hausdoerff Lambda- and Dzeta- Structures of Probability semidistances

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html

Monge-Kantorovich Mass Transference Problem, Minimal distances and minimal norms

Day 1: Statement of Monge-Kantorovich problem, Multidimensional Kantorovich Theorem, kantorovich-Rubinstein Theorem and minimal norms in probability theory

Svetlozar (Zari) Rachev (State University of New York, Stony Brook (SUNY))
http://www.ams.sunysb.edu/~rachev/index.html

Stability of Stochastic Systems

Day 5: The following topics will be covered:Stability of Queueing Systems; Stochastic Dominance Revisited, Almost Stochastic Orders and Degree of Violations.

Peter Seiler (University of Minnesota, Twin Cities)
http://www.aem.umn.edu/people/faculty/bio/seiler.shtml

Stability Analysis with Dissipation Inequalities and Integral Quadratic Constraints

Keywords of the presentation: Integral Quadratic Constraints, Dissipation Inequalities, Semidefinite Programming, J-spectral Factorization

This talk considers the use of Integral Quadratic Constraints (IQCs) for stability and performance analysis. IQC analysis theorems can be formulated in the frequency domain or with a time-domain dissipation inequality. This talk focuses on the time-domain, dissipation inequality perspective. First, the time-domain approach to IQCs is reviewed along with the associated numerical algorithms to perform the analysis. Next, the connections between the frequency domain and time-domain approaches are clarified. Finally, several extensions enabled by the time-domain approach are provided, e.g. to nonlinear and time-varying systems.

Peter Seiler (University of Minnesota, Twin Cities)
http://www.aem.umn.edu/people/faculty/bio/seiler.shtml

Synthesis for Linear Parameter Varying Systems

Keywords of the presentation: Linear Parameter Varying, Semidefinite Programming

This talk reviews methods for synthesizing and analyzing controllers for linear parameter varying (LPV) systems. This class of systems was widely studied in the early 90's to formalize the use of ad-hoc gain-scheduling in industry. The talk reviews the existing results for LPV systems and covers recent progress on numerical algorithms for these systems. First, techniques are described to model practical systems within the LPV framework. Next, the existing analysis and controller synthesis conditions are summarized. These conditions lead, in some cases, to parameterized linear matrix inequalities (LMIs). The talk discusses heuristic algorithms to approximately solve these parameterized LMIs. Finally, recent results on robustness analysis for LPV systems using integral quadratic constraints are provided.

Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Wasserstein Metric from Transport Theory and Riemannian Structure of Density Functions

Day 4: Transport theory leads to a natural metric of the space of probability densities that in turn leads to a natural Riemannian structure. We will describe some of the basic geometric concepts such as Ricci curvature, and see how this methodology allows one to define a notion of curvature on rather general metric spaces. We will describe applications to large data networks.

Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Calculus of Variations

Day 1: We introduce the Monge-Kantorovich (MK) problem and then give a brief overview of the calculus of variations, and how this may be used to treat Monge-Kantorovich, that is, the Optimal Transport problem.

Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Partial Differential Equation Approach to Monge-Kantorovich

Day 2: Using ideas from fluid dynamics, we derive a partial differential equation (pde) whose asymptotic solution solves the optimal transport problem in L2. Numerical schemes are then described allowing one to implement the pde on computer to be used in real-world applications.

Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Approaches to Matricial Optimal Mass Transport (OMT)

Day 3: We describe several possible approaches to extending the classical theory of OMT to the multivariate (matrix-valued) case. Some applications to spectral analysis will be given.

Allen Tannenbaum (State University of New York, Stony Brook (SUNY))
http://iacs.stonybrook.edu/people/affiliates/allen-tannenbaum

Applications to Medical Imaging and Theory of Shape

Day 5: Optimal mass transport has become an essential tool in medical imaging analysis. We will show how it may be used for various purposes such as elastic image registration as well as visualization. Topics include prediction of outcomes for left atial fibrillation ablation and traumatic brain injury.

Stephen Wright (University of Wisconsin, Madison)
http://www.cs.wisc.edu/

Optimality, Duality, and Complementarity for Constrained Optimization

 

Stephen Wright (University of Wisconsin, Madison)
http://www.cs.wisc.edu/

Interior-Point and Augmented Lagrangian Algorithms for Optimization and Control

 

Connect With Us:
Go