CIM PROGRAMS AND ACTIVITIES

May 25, 2015

Click for larger size

Stéphane Gaubert (INRIA and École Polytechnique)
Tropical geometry, Perron-Frobenius theory, and mean payoff games

We will survey some relations which have recently emerged between non-linear Perron-Frobenius theory, tropical geometry, and zero-sum repeated games. Perron-Frobenius theory deals with linear maps leaving a cone invariant. Tropical objects, like polyhedra, or semi-algebraic sets, arise as images by log-glasses, or by non-Archimedean valuations, of the same objects over fields. We shall see that by applying log-glasses to non-linear Perron-Frobenius maps, we end up with Shapley operators (dynamic programming operators of zero-sum games). Moreover, the sub or super fixed points of these operators provide optimality certificates for the mean payoff criteria. Finally, mean payoff games will be shown to be equivalent to feasibility problems in tropical linear programming, whereas zero-sum stochastic games will be reduced to feasibility problems in tropical convex programming. This talk is based on a work with M. Akian and A. Guterman. It will also cover more recent materials with X. Allamigeon, P. Benchimol, and, M. Joswig.

Pascal Benchimol (EDF Research Center)
Applications of tropical geometry to linear programming and mean payoff games

We present two results obtained from applying the viewpoint of tropical geometry to linear programming. Tropical geometry is the algebraic geometry over semirings such as the real numbers endowed with the maximum as the first operation, and the sum as the second. Tropical geometry arises as a logarithmic limit of classical geometry. In particular, the tropical analogue of a linear program is a logarithmic limit of a classical linear program, that yet retains much information on the classical problem. Using this approach, we exhibit a counter-example to the continuous analogue of the Hirsch conjecture, that is we present a family of classical linear programs with 3r+4 inequalities in dimension 2r+2 where the central path has a total curvature which is exponential in r. Tropical linear programs are equivalent to a class of infinite two player games, called mean payoff games, whose complexity status is still unsettled. By tropicalizing the simplex method, we obtain the first algorithm that solves mean payoff games in polynomial time on average. This talk is based on a joint work with X. Allamigeon, S. Gaubert and M. Joswig

March 16, 2015

Location:
Stewart Library

Click for larger size

Miguel Anjos, Ecole Polytechnique Montréal
Current Challenges and Recent Progress in Optimization for the Smart Grid

A smart grid is the combination of a traditional power distribution system with two-way communication between suppliers and consumers. This combination is expected to deliver energy savings, cost reductions, and increased reliability and security, but smart grids introduce numerous challenges for the management of the resulting system. These include integrating renewable energy sources such as wind and solar electricity generation, managing bidirectional flows of power, and incorporating demand-response. We will present an overview of the challenges in this area, and examples of how optimization is helping to meet these challenges.

Innocent Kamwa, Hydro-Québec
Applications of Optimization to Improve Performance of Power Transmission Networks

Hydro-Québec's electrical transmission system is an extensive, international grid with extensions into the northeastern United States of America. For such large power systems, one of the major issues is to ensure reliability while improving the steady-state and dynamic performances of the network. We will present different ways in which optimization algorithms can be applied in this context, such as the optimal location and rating of flexible AC transmission system devices, the design and coordination of damping controllers, and the optimal allocation and scheduling of multiple battery energy storage systems to improve energy efficiency.

December 9, 2014

Click for larger size

Paul McNicholas, McMaster University
Multiple-Scale Asymmetric Clustering

Finding groups of points within data can present a challenging problem. This is especially so when data are asymmetric and/or high-dimensional. While clustering high-dimensional data has garnered much attention for the past decade or so, clustering asymmetric data has only recently become the subject of significant research endeavour. This talk aims to address the problem of clustering asymmetric data in a manner that can easily be extended to high-dimensional data. The approaches that will be discussed are based on extensions of a mixture of generalized hyperbolic distributions. Issues around cluster convexity and parameter estimation will be discussed. Examples will be used for illustration.

Mark-John Bruwer, Prosensus
Rapid development of new products via advanced statistical modeling and optimization

Today manufacturers face fierce competition to establish, maintain and grow market share for their products. Product lifetimes for many food or chemical products can be as short as a year or less. Traditional approaches to product development typically require 2 to 5 years to take a new product from conception to commercial launch. Therefore there is an urgent need for more effective and efficient methods to navigate the product development process.

This talk will present an approach to product development that has shown considerable success for ProSensus clients in the food and chemical industries. The method is based around the use of latent variable models that combine raw material properties, product formulation, and process operating conditions into an integrated model that predicts the key quality attributes of the desired product. The latent variable approach can often achieve a significant dimension reduction for the product development problem, enabling the space to be explored with significantly fewer experiments, saving time and money. Once a reliable model is attained, numerical optimization is applied to it to generate candidate designs that specify the product formulation and process operating conditions that achieve the desired product. Typically multiple solutions are possible, enabling secondary optimization criteria to be introduced, such as minimizing the cost of the selected raw materials, using more reliable suppliers, etc.

We believe this technology has the potential to revolutionize the way product development is implemented.

October 14, 2014


Click for larger size

Tamás Terlaky, Lehigh University
Optimization Theory and Dynamical Systems : Invariance and Invariance Preserving Discretization Methods

First we present a novel, unified, general approach to investigate sufficient and necessary conditions under which four types of convex sets, polyhedra, polyhedral cones, ellipsoids and Lorenz cones, are invariant sets for a linear continuous or discrete dynamical system. The Farkas Lemma and the S-lemma are the key tools in deriving sufficient and necessary conditions for invariance.

Second, we consider invariance preserving step-length thresholds on a set when a discretization method is applied to a continues linear or nonlinear dynamical system. Our main result, both for linear and nonlinear dynamical systems, is the existence of a uniform invariance preserving step-length threshold for a large class of discretization methods for convex compact sets, and proper cones.

Third, the computation of step-length thresholds for invariance preserving of some classes of discretization methods on a polyhedron are considered. For for rational function type discretization methods a valid step length threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions.

Finally, for the forward Euler method, the largest step-length threshold for invariance preserving is presented by solving a finite number of linear optimization problems.

Piyush Grover, Mitsubishi Electric Research Laboratories
Dynamical systems and optimization: Exploiting structure in nonlinear systems

Nonlinear systems of mechanical origin often have structure that can be uncovered via various methods of dynamical systems. This structure can often lead to simplification of optimal design problems. We use geometric, topological and statistical methods to uncover this structure in problems in astrodynamics and micro-fluidics. First we discuss the geometric structure of the restricted three-body problem. We use this structure to construct nearly optimal solutions to global optimal control problems in mission design.

Next, we discuss the topological nature of mixing and transport in two-dimensional fluid mechanics. The main theorem we use here is the Thurston-Nielsen classification theorem (TNCT), which can be used to give lower bounds on topological entropy for flows with periodic orbits. We use statistical methods to construct almost-invariant sets in more general flows, and make the case that a topological analysis based on spatiotemporal braiding of almost-invariant sets can be used for analyzing and optimizing chaos in fluid flows.