|
Séminaire Pluridisciplinaire d'Optimisation de Toulouse (SPOT)
|
SPOT 35. Lundi 20 juin 2016. Lieu: ENSEEIHT, Salle des thèses.
14h: Monique Laurent, CWI Amsterdam, Pays-Bas
Semidefinite hierarchies for non-commutative polynomial optimization with applications in quantum information
We consider polynomial optimization problems in non-commutative variables, where variables may be instantiated at symmetric matrices of arbitrary sizes. Such problems arise in particular in quantum information as, for instance, finding the maximum entangled value of a non-local game, or estimating quantum analogs of classical graph parameters like the chromatic number. We will discuss how to construct moment-based semidefinite hierarchies, their convergence properties and links to completely positive semidefinite matrices.
15h: Etienne de Klerk, Tilburg University, Pays-Bas
Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It is known that, for the Lebesgue measure $d\mu(x) = dx$, one may show an error bound $O(1/\sqrt{r})$ if $h$ is a sum-of-squares density, and an $O(1/r)$ error bound if $h$ is the density of a beta distribution. In this paper, we show an error bound of $O(1/r^2)$, if $d\mu(x) = \left(\prod_{i=1}^n \sqrt{1-x_i^2} \right)^{-1}dx$ (the well-known measure in the study of orthogonal polynomials), and $h$ has a Schm\"udgen-type representation with respect to $[-1,1]^n$, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels, and in particular on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities. (Joint work with Monique Laurent and Roxana Hess.)
********************************************************
SPOT 34. Lundi 6 juin 2016. Lieu: ENSEEIHT, Salle des thèses.
14h: Jalal Fadili, Université de Caen, France -- Exposé annulé
14h: Aurélien Garivier, Université de Toulouse, France
On the Complexity of Best Arm Identification with Fixed ConfidenceI will present a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. In other words, we give a new, tight lower bound for the expected number of obervations required in order to identify, with high probability, the maximum of a discrete function observed in noise. Furthermore, we propose the 'Track-and-Stop' strategy, which we prove to be asymptotically optimal. As a conclusion, I will present perspectives of extensions to continuous optimization.
Joint work with Emilie Kaufmann, accepted at COLT'16, see this preprint.
15h: S. K. Mishra, Banaras Hindu University, Varanasi, India
Mathematical Programs with Equilibrium Constraints: Optimality, Duality and Applications
In this presentation, we focus on optimality conditions of MPEC. We introduce Wolfe type and Mond-Weir type dual programs to the mathematical programming problem with equilibrium constraints (MPEC). We have established weak and strong duality theorems relating the MPEC and the two dual programs. To the best of our knowledge, dual problem to a MPEC were not been given in the literature before Mishra and Pandey (2016). Some applications are also presented.
********************************************************
SPOT 33. Lundi 2 mai 2016. Lieu: ENSEEIHT, Salle des thèses.
14h: Joaquim Martins, University of Michigan, Ann Arbor, USA
Optimisation numérique de la conception d'une aile d'avion: Rêve ou réalité?
Wing shape is a crucial aircraft component that has a large impact performance. Wing design optimization has been an active area of research for several decades, but achieving practical designs has been a challenge. One of the main challenges is the wing flexibility, which requires the consideration of both aerodynamics and structures. To address this, we proposed the simultaneous optimization of the outer mold line of a wing and its structural sizing. The solution of such design optimization problems is made possible by a framework for high-fidelity aerostructural optimization that uses state-of-the-art numerical methods. This framework combines a three-dimensional CFD solver, a finite-element structural model of the wingbox, a geometry modeler, and a gradient-based optimizer. This framework computes the flying shape of a wing and is able to optimize aircraft configurations with respect to hundreds of aerodynamic shape and internal structural sizes. The theoretical developments include coupled- adjoint sensitivity analysis, and an automatic differentiation adjoint approach. The algorithms resulting from these developments are all implemented to take advantage of massively parallel computers. Applications to the optimization of aircraft configurations demonstrate the effectiveness of these approaches in designing aircraft wings for minimum fuel burn. The results show optimal tradeoffs with respect to wing span and sweep, which was previously not possible with high-fidelity models.
15h: Daniel Delahaye, ENAC, Toulouse
Some Mathematical Models for Aircraft Trajectory Design Applications to Air Traffic Management
Air traffic management ensures the safety of flight by optimizing flows and maintaining separation between aircraft. After giving some definitions, some typical feature of aircraft trajectories are presented. Trajectories are objects belonging to spaces with infinite dimensions. The naive way to address such problem is to sample trajectories at some regular points and to create a big vector of positions (and or speeds). In order to manipulate such objects with algorithms, one must reduce the dimension of the search space by using more efficient representations. Some dimension reduction tricks are then presented for which advantages and drawbacks are presented. Then, front propagation approaches are introduced with a focus on Fast Marching Algorithms and Ordered upwind algorithms. Applications of such tools to the following problems are then presented: - Large scale trajectory planning (continental and oceanic); - Wind optimal trajectory design; - Tactical trajectory planning; - Emergency trajectory design.
********************************************************
SPOT 32. Lundi 4 avril 2016. Lieu: ENSEEIHT, Salle des thèses.
14h: Patrick Louis Combettes, Université Pierre et Marie Curie, Paris
Traitement proximal en science des données, de Gerchberg-Papoulis aux décompositions par blocs
On fera on survol historique des méthodes proximales en sciences des données et on présentera des résultats récents sur les algorithmes d'éclatement proximal décomposés par blocs.
15h: Sébastien Gadat, Université Toulouse 1 Capitole
Comment calculer le barycentre d'un (très grand) graphe?
L'objectif de cet exposé est de décrire un algorithme de calcul de barycentre pour des structures discrètes telles que les graphes pondérés. De telles structures sont couramment utilisées pour décrire des bases de données, modéliser des communications, internet, des flux de transport routier ou aérien, etc. Le calcul du barycentre de telles structures, pour un graphe possiblement très gros, induit des difficultés liées à l'optimisation de fonctionnelles non convexes. Nous décrivons dans cet exposé une première manière de calculer le barycentre de graphes pondérés (arêtes et noeuds), au travers d'un algorithme de recuit simulé homogénéisé et démontrons la convergence d'une telle procédure. Enfin, nous élucidons la question fondamentale ;): ''quel est le mathématicien central de l'Université de Toulouse?'', au travers d'une application sur un graphe de citations de plus de 13000 noeuds.
Ce travail est en collaboration avec I. Gavra (Etudiante en thèse) , L. Miclo (DR CNRS) et L. Risser (IR CNRS)
********************************************************
SPOT 31. Lundi 8 février 2016. Lieu: ENSEEIHT, Salle des thèses.
14h: Guy Bouchitté, Université de Toulon
Un schéma de dualité pour des problèmes non convexes du calcul des variations
In this talk I will develop a duality theory for classical problems of the Calculus of Variations of the kind $J(\Omega) := \inf \left\{\int_\Omega (f(\nabla u) + g(u))\,dx + \int_{\Gamma_1} \gamma(u) \, dH^{d-1}$, $u=0$ on $\Gamma_0$, where $g$, $\gamma$ are possibly non convex functions with suitable growth conditions and $f$ is a convex intergrand on $R^d$. Here $(\Gamma_0 , \Gamma_1)$ is a partition of $\partial \Omega$. A challenging issue is to characterize the global minimizers of such a problem and the stability of the minimal value (with respect for instance to small deformations of the domain $\Omega$).
We present a duality scheme in which the dual problem reads quite nicely as a linear programming problem. A min-max algorithm can be then applied in which possibly multiple solutions of the initial problem can be identified. Applications are given for a class of free boundary problems.
15h: Guillaume Garrigos, Istituo Italiano di Tecnologia, Genoa, Italie, et Massachusetts Institute of Technology, Boston, USA
Dynamique(s) gradient pour l'optimisation multi-objectif
Certains problèmes d’ingénierie, notamment en optimisation de forme, peuvent se présenter sous la forme d'un problème multi-objectif, où plusieurs fonctions doivent être minimisées. Dans ce cas on s'intéressera à chercher un (les) équilibre de Pareto du système. Étant donné que tous les équilibres de Pareto sont équivalemment admissibles, on pourra également chercher à choisir, parmi les équilibres de Pareto, celui minimisant un certain critère: c'est le problème d'optimisation post-Pareto.
Nous présenterons dans un premier temps une dynamique continue de type gradient, dont les trajectoires convergent vers des équilibres de Pareto. Dans un second temps, nous modifierons cette dynamique en y introduisant un terme inertiel afin d'améliorer la vitesse de convergence, et nous verrons que les trajectoires associées convergent aussi vers des équilibres de Pareto. Enfin nous discuterons une méthode de pénalisation à la Tikhonov pour permettre la résolution du problème post-Pareto.
********************************************************
SPOT 30. Lundi 14 décembre 2015. Lieu: Manufacture des Tabacs
(UT1), salle MF323. Conjointement avec le séminaire MAD.
14h: Thierry Champion,
Université de Toulon
A new class of costs for optimal transport problems
Résumé ici.
15h: Vladimir
Shikhman (Université Catholique de Louvain)
Computation of Fisher-Gale equilibrium by auction
Abstract: We study the Fisher model of a competitive market from the
algorithmic perspective. For that, the related convex optimization problem
due to Gale and Eisenberg is used. The latter problem is known to yield a
Fisher equilibrium under some structural assumptions on consumers'
utilities, e.g. homogeneity of degree 1, homotheticity etc. Our goal is to
examine the applicability of the convex optimization framework by
departing from these traditional assumptions. We just assume the concavity
of consumers' utility functions. For this case we suggest a novel concept
of Fisher-Gale equilibrium by using consumers' utility prices. The prices
of utility transfer the utility of a consumption bundle to a common
numeraire. We develop a subgradient-type algorithm from Convex Analysis to
compute a Fisher-Gale equilibrium via Gale's approach. In order to
decentralize prices, we additionally implement the auction design, i.e.
consumers settle and update their individual prices and producers sell at
the highest o.er price. Our price adjustment is based on a tatonnement
procedure, i.e. the prices change proportionally to consumers' individual
excess supplies. Historical averages of consumption are shown to clear the
market of goods. Our algorithm enjoys a convergence rate. In worst case,
the number of price updates needed to achieve the E-tolerance is
proportional to 1/E^2 .
********************************************************
SPOT 29. Lundi 16 novembre 2015. Lieu: ENSEEIHT. Salle des Thèses
14h: Milan Korda
(EPFL Lausanne, Suisse)
Constrained LQR control with accelerated proximal gradient algorithm
This talk presents an algorithmic scheme for solving the infinite-time constrained linear quadratic regulation problem. We employ an accelerated version of a popular proximal gradient scheme, commonly known as the Forward-Backward Splitting (FBS), and prove its convergence to the optimal solution in our infinite-dimensional setting. Each iteration of the algorithm requires only finite memory, is computationally cheap, and makes no use of terminal invariant sets; hence, the algorithm can be applied to systems of very large dimensions. The acceleration brings in optimal convergence rates O(1/k^2) for function values and O(1/k) for primal iterates and renders the proposed method a practical alternative to model predictive control schemes for setpoint tracking. In addition, for the case when the true system is subject to disturbances or modelling errors, we discuss an efficient warm-starting procedure, which significantly reduces the number of iterations when the algorithm is applied in closed-loop.
15h: Jérôme Renault
(Univ. Toulouse 1 Capitole)
Acylic gambling games
We consider general 2-player zero-sum stochastic games where each player controls his own state variable living in a compact metric space. The terminology comes from gambling problems where the state of a player represents its wealth in a casino. Under natural assumptions (such as continuous running payoff and non expansive, possibly stochastic, transitions), we consider for each discount factor the value of the $\lambda$-discounted stochastic game and investigate its limit when $\lambda$ goes to 0. We show that under a strong acyclicity condition, the limit exists and is characterized as the unique solution of a system of functional equations. The approach generalizes and provides a new viewpoint on the Mertens-Zamir system coming from the study of zero-sum repeated games with lack of information on both sides. A counterexample shows that under weak acyclicity, the convergence may fail to exist. Joint work with Rida Laraki.
********************************************************
SPOT 28. Lundi 12 octobre 2015. Lieu: ENSEEIHT. Salle des Thèses.
14h: Andrew
Conn (IBM T. J. Watson Research Center, NY, USA)
Inversion, history matching, clustering and linear algebra
The inversion of large-scale ill-posed problems introduces multiple challenges,including, identifying appropriate noise models, prescription of suitable prior information, incorporation of heterogeneous sources of data, and the definition of an appropriate optimization scheme. In this presentation, the inherent uncertainty of the problem is mitigated by devising efficient and comprehensive approaches for prior sampling. In particular, geo-statisticians may often propose large sets of prior samples that regardless of their apparent geological distinction are almost entirely flow equivalent. As an antidote, a reduced space hierarchical clustering of flow relevant indicators is proposed for aggregation of these samples. The effectiveness of the method is demonstrated both with synthetic and field scale data.
In addition, numerical linear algebra techniques that exploit the special structure of the underlying problems are elucidated.
Finally, if time permits, I will include some very recent work using derivative free methods.
15h: Olivier Cots
(IRIT-ENSEEIHT, Toulouse)
Méthodes géométrique et numérique pour le contrôle en temps minimal d'un véhicule électrique
On reprend le modèle de véhicule électrique étudié dans une série d'articles par F. Messine et al. On s'intéresse ici au déplacement du véhicule en temps minimal. Le problème de contrôle optimal s'écrit sous une forme de Mayer, avec un système en dimension trois, affine en le contrôle (scalaire), avec deux contraintes sur l'état. On montre à l'aide du principe du maximum de Pontryagin et de la configuration des crochets de Lie que les trajectoires optimales sont constituées seulement d'arcs bangs et d'arcs contraints. L'étude couplée à l'utilisation du logiciel hampath, permettent de construire une synthèse optimale en fonction des bornes des contraintes.
********************************************************
SPOT 27. Lundi 28 septembre 2015. Lieu: ENSEEIHT. Salle des Thèses.
14h: Jean-Baptiste Caillau
(Univ. Bourgogne, Dijon)
Déterminants d'opérateurs de Schrödinger
Le déterminant intervient dans l'étude des opérateurs elliptiques à spectre discret en physique mathématique. On considère le cas d'opérateurs de Schrödinger de la forme Laplacien + potentiel, le potentiel s'interprétant comme un opérateur de multiplication. On s'intéresse en particulier à la maximisation du déterminant d'un tel opérateur sous une contrainte de norme L^1 en dimension un. Levit et Smilansky (1977) puis Burghelea, Friedlander et Kappeler (1995) ont montré que ce problème se reformule en contrôle optimal. L'étude de l'existence et de l'unicité de solution montre l'importance des contrôles singuliers pour la détermination du potentiel maximisant.
Travail en commun avec C. Aldana (U. Luxembourg) et P. Freitas (U. Lisbonne)
15h: Edouard Pauwels
(Univ. Paul Sabatier, Toulouse)
Nonsmooth Optimization with Semi-Algebraic Data: Convergence Beyond the Proximal Setting
We focus on convergence of iterative schemes for non-smooth non-convex optimization in finite dimension. Most of current results are given for "prox-friendly" data: the nonsmooth part can be handled through efficiently computable operators. Many methods and applications do not fit this setting. We focus on Sequential Quadratic Programming ideas for general Nonlinear Programs. Despite their large usage, these methods lack satisfactory convergence analysis. This work constitutes a step toward the obtention of such theoretical guaranties. We combine properties of local tangent majorizing models with results from algebraic geometry to analyse the asymptotic properties of two recent methods for solving general Nonlinear Programming problems.
This is joint work with J. Bolte.
