|
Séminaire Pluridisciplinaire d'Optimisation de Toulouse (SPOT)
|
SPOT 26. Lundi 1 juin 2015. Lieu: ENSEEIHT. Salle des Thèses.
14h: Luís Nunes Vicente (Univ. Coimbra)
Direct Search Based on Deterministic and Probabilistic Descent
Direct-search methods are a class of popular derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions. When applied to the minimization of smooth functions, the polling directions are typically taken from positive spanning sets which in turn must have at least $n+1$ vectors in an $n$-dimensional variable space. In addition, to ensure the global convergence of these algorithms, the positive spanning sets used throughout the iterations must be uniformly non-degenerate in the sense of having a positive (cosine) measure bounded away from zero.
However, recent numerical results indicated that randomly generating the polling directions without imposing the positive spanning property can improve the performance of these methods, especially when the number of directions is chosen considerably less than $n+1$.
In this talk, we analyze direct-search algorithms when the polling directions are probabilistic descent, meaning that with a certain probability at least one of them is of descent type. Such a framework enjoys almost-sure global convergence. More interestingly, we will show a global decaying rate of $1/\sqrt{k}$ for the gradient size, with overwhelmingly high probability, matching the corresponding rate for the deterministic versions of the gradient method or of direct search. Our analysis helps to understand numerical behavior and the choice of the number of polling directions.
This is joint work with Mahdi Dodangeh, R. Garmanjani, S. Gratton, Clément Royer, and Zaikun Zhang.
15h: Chloé Jimenez
(Univ. Brest)
Croissance d'une pile de sable sur une table bordée par des murs verticaux
Dans ce travail en collaboration avec Luigi De Pascale, nous prouvons l'existence d'une solution pour un système d'EDP qui décrit la croisssance d'une pile de sable - sur une table bordée par des murs verticaux - sous l'action d'une source mesure verticale. Nous utilisons pour cela une approximation discrète de la source et la dualité en transport optimal.
********************************************************
SPOT 25. Lundi 27 avril 2015. Lieu: ENSEEIHT. Salle: A203.
14h: Michael Overton (Courant Inst., New York Univ.)
Nonsmooth, Nonconvex Optimization and Crouzeix's Conjecture
In many applications one wishes to minimize an objective function that is not convex and is not differentiable at its minimizers. For such "nonsmooth" optimization problems, we have found that BFGS, a well known quasi-Newton method developed for smooth problems, is remarkably effective, although it lacks a satisfactory convergence theory. After discussing the behavior of BFGS in the nonsmooth context, we apply it to investigate a challenging problem in the theory of non-normal matrices called Crouzeix's conjecture, which we will explain in some detail. We compute the Crouzeix objective function using CHEBFUN, a very useful tool that we will also discuss briefly.
15h: Jean-Bernard Lasserre
(LAAS-CNRS Univ. Toulouse)
Reconstruction of algebraic-exponential data from moments
Let G be a bounded open subset of Euclidean space with real algebraic boundary Gamma. In a first part of the talk we consider the case where G={x: g(x) <=1} for some quasi-homogeneous polynomial g and derive several properties of G as well as the non-Gaussian integral \int exp(-g)dx. In particular we show that the volume of G is a convex function of the coefficients of g and solve a generalized version of the Lowner-John problem.
Next, we consider a more general case and under the assumption that the degree d of Gamma is given, and the power moments of the Lebesgue measure on G are known up to order 3d, we describe an algorithmic procedure for obtaining a polynomial vanishing on Gamma. The particular case of semi-algebraic sets defined by a single polynomial inequality raises an intriguing question related to the finite determinateness of the full moment sequence. The more general case of a measure with density equal to the exponential of a polynomial is treated in parallel. Our approach relies on Stokes theorem and simple Hankel-type matrix identities.
Joint work with Mihai Putinar.
********************************************************
SPOT 24. Lundi 2 mars 2015. Lieu: Manufacture des Tabacs, Bâtiment S (rue de l'abreuvoir Saint-Pierre), Salle MS001 (RDC).
14h: Marc Teboulle (Tel Aviv Univ., Israel)
Performance of First Order Methods for Convex Minimization: A Novel Approach
We introduce a novel approach for analyzing the worst-case performance of first-order black-box convex optimization methods. Our approach relies on the observation that by definition, the worst-case behavior of an optimization method is by itself an optimization problem which consists of finding the maximal abolute inacurracy over all possible inputs of the algorithm, and which we call the performance estimation problem (PEP). This is an abstract and challenging optimization problem in infinite dimension which appears to be untractable. We will present a methodology to design and analyze the PEP for a broad class of first order black-box algorithms. It allows to derive new and improved complexity bounds for the gradient method, the heavy-ball method and the fast gradient schemes. We also show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance. This is joint work with Yoel Drori.
15h: J. Frédéric Bonnans (INRIA Saclay, Ecole Polytechnique)
On Pontryagin's principle in stochastic control
We discuss stochastic optimal control problems whose volatility does not depend on the control, and which have finitely many equality and inequality constraints on the expected value of function of the final state, as well as control constraints. The main result is a proof of necessity of some second order optimality conditions involving Pontryagin multipliers.
********************************************************
SPOT 23. Lundi 2 février 2015. Lieu: ENSEEIHT.
14h: Fabian Bastin (Univ. Montréal)
Application de l'algorithme de couverture progressive pour la planification à moyen terme de la production hydroélectrique
L'algorithme de couverture progressive, introduit en 1991 par Rockafellar and Wets, demeure à ce jour un des seuls algorithmes disponibles pour traiter des problèmes de programmation stochastique multi-étapes. Dans cet exposé, nous montrerons comment il peut s'appliquer aux questions de gestion des réservoirs de barrages hydroélectriques au Québec, en considérant un horizon de deux années, pour des décisions définies sur base hebdomadaire, en tenant compte de l'incertitude liée aux apports hydrologiques. Diverses stratégies permettant d'augmenter l'efficacité de la méthode seront également examinées.
15h: Christian Artigues (LAAS-CNRS Univ. Toulouse)
Programmation linéaire en nombres entiers pour l'ordonnancement sous contraintes de ressources
Le problème d'ordonnancement de projet sous contraintes de ressources est un problème d'ordonnancement NP-difficile qui se situe au coeur d'applications pratiques multiples et diverses : gestion de projet, lignes d'assemblages aéronautiques, systèmes d'exploitations multi-coeurs, etc. Dans cet exposé, des formulations de programmation mixte en nombres entiers de ce problème sont présentées. Des formulations classiques issues de la littérature, ainsi que des nouvelles formulations sont classifiées selon leur taille. Dans cette classification, des modèles compacts (de taille polynomiale), des modèles de taille pseudo-polynomiales et des modèles étendus (de taille exponentielle) sont exposés. Une comparaison théorique et expérimentale de ces formulations est effectuée. La complémentarité de ces formulations pour différents usages est finalement mise en avant et des directions de recherche future, comme l'hybridation avec d'autres approches et en particulier les modèles SAT, sont évoquées.
********************************************************
SPOT 22. Lundi 8 décembre 2014. Lieu: ENSEEIHT.
14h: René Henrion (Weierstrass Inst. Berlin)
Gradient formulae in probabilistic programming
Probabilistic Programming is a discipline dealing with optimization problems under probabilistic constraints. The latter have proven to be useful in many engineering problems, in particular in the management of hydro reservoirs. A major challenge in the solution of such problems is to calculate values and gradients of parameter-dependent probability functions, where the parameter is given by the decision te be optimized. The talk discusses this issue for the important class of linear probabilistic constraints under Gaussian distribution with a perspective to nonlinear constraints and Gaussian-like distributions.
15h: Fabrice Gamboa (Univ. Paul Sabatier Toulouse)
La méthode Pick and Freeze de Sobol à la sauce COSTA BRAVA
Nous présentons ici des résultats récents obtenus sur l'estimation des indices de Sobol dans le projet ANR COSTA BRAVA. Ces coefficients apparaissent naturellement dans la décomposition de Hoeffding d'une fonction de L^2.
********************************************************
SPOT 21. Lundi 3 novembre 2014. Lieu: UT1.
14h: Pierre Cardaliaguet (Univ. Paris-Dauphine)
Mean Field Games with local coupling
We will discuss several aspects of mean field games (MFG), which are differential games with infinitely many small agents. Here we consider MFG with local coupling, meaning that the agents only interact with the other agent which are in a very close neighborhood. These MFG games turn out to be potential games, thus allowing to build solutions by techniques of calculus of variation. We will also show how the solution of the mean field game system can be used to build approximate Nash equilibria for differential games with a finite number of players.
15h: Christine Gruen (Univ. Toulouse 1 Capitole)Stopping games for continuous time Markov chains with incomplete information
We study a model of a two-player, zero-sum, stopping game with incomplete information on both sides. We assume that the payoff depends on two continuous-time Markov chains (X_t),(Y_t) where (X_t) is only observed by player 1 and (Y_t) only by player 2. We show the existence of a value by PDE methods. In the case of incomplete information on one side we establish a different characterisation of the value by a stochastic optimisation problem and study an example in case of a two state Markov process. Joint work with Fabien Gensbittel
********************************************************
SPOT 20. Lundi 6 octobre 2014. Lieu: ENSEEIHT.
14h: Alberto Seeger (Univ. Avignon)
Extremal problems on the space of closed convex cones
We establish a suitable conic formulation of a number of classical extremal problems on the space of convex bodies (Blaschke-Santalo inequality, Mahler conjecture, John's ellipsoid theorem, Ball's volume ratio theorem, etc).
15h: Frédéric de Gournay (Univ. Paul Sabatier Toulouse)
Robust optimization in shape optimization
In this talk, we will address the problem of shape optimization and its particularities. The standard shape optimization problem we shall concentrate on is the one of optimizing the elastic energy stored in a body with given loads. The optimization variable being the set on which the PDE of elasticity is defined. We will then investigate the recent advances in robust optimization, a concept that integrates the notion of error in the prescribed load or in the shape itself.
