Séminaire Pluridisciplinaire d'Optimisation de Toulouse (SPOT) Pluridisciplinary Optimization Seminar in Toulouse (POST)

Comité local d'organisation 2013-2014

• Jérôme Bolte (UT1 et TSE)
• Sonia Cafieri (ENAC)
• Serge Gratton (CERFACS, IRIT et ENSEEIHT)
• Didier Henrion (LAAS – CNRS)
• Pierre Maréchal (ISAE)
• Frédéric Messine (LAPLACE et ENSEEIHT)
• Aude Rondepierre (INSA et IMT)

Liste des séances 2013-2014

SPOT 19. Lundi 2 juin, 2014. Lieu: ENSEEIHT.

14h: Philippe Toint (Université de Namur)

Une synthèse des résultats de complexité pour l'optimisation continue non convexe

Nous présenterons un panorama des résultats récents en complexité dans le pire des cas pour l'optimisation continue potentiellement non convexe. Les cas avec et sans contraintes seront abordés, montrant comment les résultats s'articulent en eux et permettent de jeter une nouvelle lumière, parfois un peu surprenante, sur des méthodes classiques. Des (contre-)exemples seront donnés pour justifier le caractère optimal de certains des ordres de complexité présentés.

15h: Ehouarn Simon (ENSEEIHT Toulouse)

Approche variationnelle à l'assimilation de données

L'assimilation de données englobe l'ensemble des techniques permettant de combiner, de la meilleure des façons possibles (dans un sens à définir), l'information mathématique contenue dans les équations et l'information physique provenant des observations en vue de reconstituer l'état d'un système. Une approche, dite variationnelle, consiste à minimiser une fonction de coût mesurant, entre autre, l'écart entre le modèle et les observations.

Dans cette étude, nous nous intéressons à la réduction des coûts de calculs liés à la minimisation de cette fonction de coût via un choix des observations à assimiler parmi l'ensemble des observations à notre disposition. Nous proposons un critère de sélection basé sur une estimation d'erreur a posteriori et exploitant une structure "multigrille" des observations. Cette approche conduit à une succession de problèmes de minimisation dont la résolution exploite des formulation duales dans des espaces emboîtés. Les performances de cette approche sont discutées dans le cas d'expériences jumelles réalisées sur des modèles "jouets" (équation d'onde 1D et système de Lorenz-96).

SPOT 18. Lundi 12 mai, 2014. Lieu: ENSEEIHT.

Ouverture de la conférence VORACE.

14h: Colin N. Jones (Ecole Polytechnique Fédérale de Lausanne)

Multi-Convex Splitting for Real-Time Model Predictive Control

Pushing predictive controllers, which require the solution of an optimization problem at each sampling interval, into the millisecond range opens up both new possibilities, as well as new challenges for control. Computational limits invalidate basic assumptions made when proving the stability, or invariance of constrained control laws and as a result cannot be used in fast, real-time implementations with confidence. In this talk, I will discuss some of our recent work that brings the benefits of optimization-based control to high-speed systems, while simultaneously providing the computational flexibility and hard real-time guarantees required by modern embedded control platforms. We'll begin with an overview of fast-MPC methods, and then argue that operator-splitting approaches have a lot to offer in this domain. I'll introduce a new technique for solving a class of nonlinear optimal control problems for distributed systems, or on parallel hardware, that comes with a formal guarantee of stability under fixed-time computation. Finally, I will report on a new fast code-generation toolbox, SPLIT, which provides a method to easily deploy real-time, optimisation-based control laws on various embedded platforms.

15h: Assalé Adjé (ONERA Toulouse)

Constrained optimisation and policy iteration applied to abstract interpretation

To test a program is not enough to show that they are correct. They have to be formally verified to ensure exhaustiveness of the analysis. However correction is not decidable in general and abstract interpretation aims at overcoming this undecidability by loosing completness. This method amounts to solve a non-linear fixed point equation involving a monotonic function describing the program behavior. In this talk, we are interested in verifying numerical programs. More precisely, we compute bounds on the values taken by the variable of a program (e.g. to prove that the set of reachable values is bounded, or to prove absence of critical values). We show that this problem can be formulated in term of values of a constrained maximisation problem and can be reduced to solve the upper value of a two-player zero-sum game thanks to Lagrange duality. This latter observation allows us to use algorithms from game theory such as policy iteration.

SPOT 17. Lundi 14 avril 2014. Lieu: ENSEEIHT.

14h: Paul Armand (Univ. Limoges)

A globally and quadratically convergent primal-dual augmented Lagrangian algorithm

We present a primal-dual augmented Lagrangian method to solve an equality constrained minimization problem. This is a Newton-like method applied to a perturbation of the optimality system that follows from a reformulation of the initial problem by introducing an augmented Lagrangian function. An important aspect of this approach is that, by a choice of suitable updating rules of the parameters, the algorithm reduces to a regularized Newton method applied to a sequence of optimality systems derived from the original problem. The global convergence is proved under mild assumptions. An asymptotic analysis is also presented and quadratic convergence is proved under standard regularity assumptions. Some numerical results are presented and show that the method is very efficient and robust. The extension to problems with inequality constraints is also discussed.

Global Optimization using Contractor Programming : an example of conflict avoidance of two robots with non-linear trajectories

Faced to complexity and diversity of real-life problems, it is hard to find a general pattern or an unique algorithm for solving all of them. Some algorithms deal with disjunctive constraints, others with dynamic constraints, others with uncertainties. Furthermore, when real-life problems merge different kinds of constraint, we often need to remove a part of the model because our solvers are not able to accept it. Unfortunately, these cases are not rare.

In this talk, we will present a general pattern that allows to handle a wide variety of problems. This paper introduces the use of the contractors for designing a global optimization algorithm. We recall the definitions related to interval arithmetic and contractor programming. Then, we present a short subset of some standard contractors and how we can combine and merge them. Finally, we will illustrate the entire process with an example of minimizing the consumption of two robots following non-linear parametric trajectories and subject to two constraints: conflict avoidance and validation of at least 80\% checkpoints.

SPOT 16. Lundi 19 mars 2014. Lieu: ENSEEIHT.

14h: Yannick Privat (CNRS-LJLL Paris)

Optimisation de domaine pour l'observabilité d'EDP

Le but de cet exposé est d'étudier des problèmes d'optimisation de forme pour l'équation des ondes ou de la chaleur sur un domaine Omega en dimension quelconque, avec des conditions frontières s'il y a un bord de type Dirichlet, Neumann, mixtes, ou Robin. Etant donné un état initial, on peut observer la solution de l'équation sur un sous-ensemble omega de Omega, ou bien la contrôler vers l'équilibre (par exemple à l'aide de la méthode HUM), ou encore la stabiliser (par damping linéaire) avec un contrôle de support omega. Dans les trois cas, on se pose la question de déterminer quel est le "meilleur" domaine possible omega parmi tous les sous-ensembles de Omega de mesure donnée (disons L*mes(Omega) avec 0 < L < 1). Ces questions sont d'abord étudiées à données initiales fixées, puis indépendamment des données initiales : par exemple, on se pose le problème de maximiser la constante d'observabilité parmi les domaines précédents. Il s'avère que ce problème est lié aux propriétés d'ergodicité quantique du domaine Omega, et notamment aux propriétés de type QUE (Quantum Unique Ergodicity). Ce sont des travaux en collaboration avec E. Trélat (Univ. Paris 6) et E. Zuazua (BCAM, Bilbao, Espagne).

Applications du transport optimal dans les jeux à potentiel

On s'intéressera à une situation dans laquelle les agents doivent décider où habiter lorsqu'ils arrivent dans une nouvelle ville. L'agent peut, par exemple, vouloir s'installer plutôt en centre ville parce que c'est l'endroit d'où il aura, en moyenne, le moins de chemin à parcourir pour interagir avec ses futures relations. Par contre il faut aussi prendre en compte le fait qu'en centre ville, la compétition est plus grande et donc les appartements plus petits ou plus chers. Mathématiquement, on considère un jeu non-coopératif, non-atomique, anonyme avec un continuum de joueurs. Mathématiquement, soient l'espace $X$ du type des agents, l'espace $Y$ des actions et un coût $c(x,y)$ qui mesure le coût d'un agent de type $x$ à prendre une action $y$. La distribution du type des agents $\mu \mathcal P(X)$ étant donné, un agent de type $x$ qui entreprend une action $y$ paie le coût $\Gamma(x,y, \lambda)$ où $\lambda$ est la distribution des actions de l'ensemble des joueurs. La question est de déterminer l'"équilibre" de Nash (= la situation dans laquelle personne n'a intérêt à déménager). Dans une situation très schématique, il est possible de déterminer les équilibres, en utilisant les derniers développements de la théorie du transport optimal. Références : [A. Blanchet, P. Mossay & F. Santambrogio, Existence and uniqueness of equilibrium for a spatial model of social interactions. Pre-print, 2012], [A. Blanchet & G. Carlier, Optimal transport and Cournot-Nash equilibria. Preprint, 2012].

SPOT 15. Lundi 3 février 2014. Lieu: ENSEEIHT.

14h: Laureano F. Escudero (Univ. Rey Juan Carlos, Madrid)

Risk averse modeling for air traffic flow management under uncertainty

An approach for air traffic management optimization under uncertainty is presented. The work is motivated by the fact that air traffic in Europe and the USA has undergone spectacular growth during the last years and a 50% traffic increase is expected by 2018 over the traffic in 1999 and, then, the airports and air sectors could be congested . Owing to the fact that many of the aircraft are used for consecutive flights, whatever delay is decided for a particular flight affects all the following flights programmed for the same aircraft. We present a framework for modeling multistage mixed 0-1 problems for the air traffic flow management problem with rerouting under uncertainty in airport arrival and departure capacity, air sector capacity and flight demand. It considers several types of objective functions to minimize. A scenario tree based scheme is used to represent the uncertainty in the problem. Traditionally, special attention has been given to optimizing the stochastic models by minimizing the objective function expected value (cost and other measures as well) over the scenarios, i.e., the so named risk neutral approach. However, it has the inconvenience of providing a solution that ignores the potential variability of the objective function value over the scenarios and, so, the occurrence of scenarios with an objective value worst than the expected one. A multistage risk averse strategy is presented for avoiding that inconvenience. Computational experience is presented. Joint work w/ A. Agustin, A. Alonso-Ayuso, C. Pizarro

Geodesics in spaces of curves: application to aircraft trajectories clustering

Aircraft trajectories are the most basic objects that are considered in the field of air trafic management. Oddly enough, the analysis tools for such data are still in early stages of develop- ment. One can roughly classify existing techniques into two cate- gories: visual analytics based tools on one hand and statistical pro- cedures on the other hand, the latter using only sampled positions of aircraft as input vector, forgetting about the time dependance between samples. A promising approach will be to work directly with trajectories understood as curves, in the spirit of functional data statistics. It has been successfully applied to the problem of trajectory clustering, and relies on the ability to derive metrics in spaces of curves. Starting with the pioneering work of D. Mumford and P. Michor, a mean of computing approximate shortest paths between two trajectories will be presented. Then, a clustering pro- cedure will be introduced along with the results obtained on some days of trafic recorded over France.

SPOT 14. Lundi 6 janvier 2014. Lieu: UT1, Salle MF323 (3ème étage, bât. F) conjoint au séminaire MAD

14h: Gilles Stoltz (HEC Paris)

Robust sequential learning with applications to the forecasting of air quality and of exchange rates

In this talk I will describe a setting of sequential learning in which many expert forecasts are available at each round to predict quantitative outcomes. We will combine the expert forecasts linearly or in a convex way and we will aim at performing almost as well as the best constant such combination. First, algorithms and performance bounds will be presented. Then, applications to real data sets will be discussed: one is concerned with air quality and the other one with exchange rates.

Incremental Optimization in Machine Learning

After a brief review of support vector machines (SVM) classification, we will discuss the underlying optimization issues and available methods to perform training and propose new first order constrained approaches. The methods exploit the structure of the SVM training problem and combine ideas of incremental gradient technique, gradient acceleration and successive simple calculations of Lagrange multipliers. Both primal and dual formulations will be presented and compared numerically. We will also discuss comparisons with an unconstrained large scale learning algorithm based on stochastic sub-gradient to emphasize that the proposed methods remain competitive for large scale learning due to the very special structure of the training problem.

SPOT 13. Lundi 9 decembre 2013. Lieu: ENSEEIHT.

14h: Grégoire Allaire (Ecole Polytechnique Palaiseau)

Multi-phase structural optimization

This is a joint work with Ch. Dapogny, G. Delgado and G. Michailidis. We consider the optimal distribution of several elastic materials in a fixed working domain. In order to optimize both the geometry and topology of the mixture we rely on the level set method for the description of the interfaces between the different phases. We discuss various approaches, based on Hadamard method of boundary variations, for computing shape derivatives which are the key ingredients for a steepest descent algorithm. The shape gradient obtained for a sharp interface involves jump of discontinuous quantities at the interface which are difficult to numerically evaluate. Therefore we suggest an alternative smoothed interface approach which yields more convenient shape derivatives. We rely on the signed distance function and we enforce a fixed width of the transition layer around the interface (a crucial property in order to avoid increasing "grey" regions of fictitious materials). It turns out that the optimization of a diffuse interface has its own interest in material science, for example to optimize functionally graded materials.

Compressed sensing with acquisition constraints

One of the key concepts emerging from the compressed sensing literature is that of variable density sampling (VDS). In its simplest abstract form, VDS consists in sampling a signal by performing projections on a set of vectors drawn independently at random among a given family. In the context of Magnetic Resonance Imaging (MRI) - which will be the application motivating my talk - it consists in measuring Fourier coefficients on the Fourier plane with a probability that decreases radially towards high frequencies. In this talk, I will first review the choice of an optimal probability density on the family of available projections. To make the compressed sensing samplers more practical, I will then turn to the problem of constrained acquisition. I will then propose numerical algorithms to construct good variable density samplers, by taking into account two different types of constraints: Block constraints, meaning that the signal can only be measured by groups of measurements such as lines on the Fourier plane; Kinematic constraints, meaning that the measurements have to lie on a parametric curve with constraints such as bounded first and second derivatives. The latter constraints are those that appear in MRI, but also in robot motion.

********************************************************

SPOT 12. Lundi 4 novembre 2013. Lieu: UT1, Salle MF323 (3ème étage, bât. F) conjoint au séminaire MAD

14h: Otmar Scherzer (Computational Science Center, University of Vienna)

Optical Flow Revisited

Variational optical flow is a method for analyzing movements in images. It is widely used in Computer Vision, surveillance, and image analysis. It is possible to reformulate optical flow as a denoising problem. In this paper we give an overview on variational denoising methods and extend them to optical flow models, which results in variational optimization problems for vector valued data. Optical flow is traditionally computed from a sequence of flat images. Finally, we extend the concept of optical flow in a dynamic non-Euclidean setting and introduce variational motion estimation for images that are defined on an (evolving) surfaces. Moreover, we are presenting some examples of biological imaging for cell movement analysis. This is joint work with Lukas Lang and Clemens Kirisits (Univ. of Vienna)

15h: Markus Grasmair (Norwegian Univ. Sci. Tech. Trondheim)

The Multi-resolution Norm for Non-parametric Regression and Inverse Problems

We study the application of the multi-resolution norm, which measures the maximal size of scaled local means of a function, in the problems of non-parametric regression and deconvolution. Our main result is the derivation of convergence rates for Tikhonov regularization, where we use the multi-resolution norm as the similarity term and a homogeneous Sobolev norm for the regularization term. The results are based on an asymptotic estimate for the norm of samples of a Gaussian random variable as the sample size tends to infinity, and an interpolation inequality for the multi-resolution norm and Sobolev norms. This is a joint work with Housen Li and Axel Munk (University of Goettingen).

********************************************************

SPOT 11. Lundi 7 octobre 2013. Lieu: ENSEEIHT.

13h30: Emmanuel Trélat (Univ. Pierre et Marie Curie Paris)

Optimisation de domaine pour l'observabilité d'EDP

Le but de cet exposé est d'étudier des problèmes d'optimisation de domaine pour l'équation des ondes, de Schrödinger, ou de la chaleur, sur un domaine Omega en dimension quelconque, avec des conditions frontières s'il y a un bord, de type Dirichlet, Neumann, mixtes, ou Robin. Etant donné un état initial, on peut observer la solution de l'équation sur un sous-ensemble omega de Omega, ou bien la contrôler vers l'équilibre (par exemple par la méthode HUM), ou encore la stabiliser (par damping linéaire) avec un contrôle de support omega. Dans les trois cas on se pose la question de déterminer quel est le "meilleur" domaine possible omega parmi tous les sous-ensembles de Omega de mesure donnée (disons L|Omega| avec L entre 0 et 1). Ces questions sont d'abord étudiées à donnée initiale fixée, puis indépendamment des données initiales: par exemple on se pose le problème de maximiser la constante d'observabilitè parmi les domaines précédents. Il s'avère que ce problème est lié aux propriétés d'ergodicité quantique du domaine Omega et notamment aux propriétés de type QUE (Quantum Unique Ergodicity). Ce sont des travaux en collaboration avec Y. Privat (CNRS, ENS Rennes) et E. Zuazua (BCAM Bilbao, Spain).

14h30: Hasnaa Zidani (ENSTA ParisTech)

Hamilton-Jacobi equations in singular domains

We consider deterministic control problems where the dynamics and the running cost can be completely different in two (or more) complementary domains of the space R^N. As a consequence, the dynamics and running cost present discontinuities at the interfaces of these domains. This leads to a complex interplay that has to be analyzed among transmission conditions to "glue" the propagation of the value function on the interfaces. Several questions arise: how to define properly the value function(s) and what is (are) the right Bellman Equation(s) associated with this problem?.