May 27 - June 13, 2014
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.
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.
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.
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.
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"
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.
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.
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.
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.
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
Day 1: Statement of Monge-Kantorovich problem, Multidimensional Kantorovich Theorem, kantorovich-Rubinstein Theorem and minimal norms in probability theory
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).
Day 3: Fortet-Mourier,
Varadarajan, and Wellner Theorems, Functional Limit Theorem and
Bernstein-Kanttorovich Invariance Pronciple
Day 5: The following topics will be covered:Stability of Queueing
Systems; Stochastic Dominance Revisited, Almost Stochastic Orders and
Degree of Violations.
Day 2: Relations between
Multidimensional Kantorovich and Strassen Theorem: Convergence of Minimal
Metrics and Minimal distances
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
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.
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.
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.
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.
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.
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.
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.