L’optimisation est un domaine au confluent des mathématiques, de l’informatique et de l’économie, dont l’importance est croissante aussi bien sur le plan académique que sur le plan de ses applications à des problèmes socio-économiques. Ce parcours concerne toutes les composantes de l’optimisation au sens-large, avec une attention particulière pour celles qui sont spécifiques au contexte de recherche du Plateau de Saclay, dynamisé par la présence du Programme Gaspard Monge pour l’Optimisation (PGMO). Les thématiques abordées sont variées : contrôle optimal (temps discret et continu, déterministe et stochastique), théorie des jeux (théorie, modélisation en économie et réseaux), calcul des variations (et plus généralement optimisation en analyse et en EDP), optimisation stochastique et méthodes stochastiques pour l’optimisation, recherche opérationnelle. Une part significative des cours proposés est mutualisée avec d’autres parcours et spécialités en mathématiques, informatique, économie. En particulier une offre de cours de « recherche opérationnelle » est proposée grâce à une collaboration avec le parcours MPRO.
Pour plus d'informations, vous pouvez consulter le site web de cette formation M2 Optimisation.
Lieu(x) d'enseignement
ORSAY
GIF SUR YVETTE
PALAISEAU
Pré-requis, profil d’entrée permettant d'intégrer la formation
Formation de niveau M1 en mathématiques ou mathématiques appliquées.
Informations complémentaires
Regardez la vidéo ci-dessous pour en savoir plus sur le M2 Optimisation.
Compétences
Comprendre et modéliser mathématiquement un problème afin de le résoudre.
Expliquer clairement une théorie et des résultats mathématiques.
Maitriser des outils numériques et langages de programmation de référence.
Analyser un document de recherche en vue de sa synthèse et de son exploitation.
Analyser des données et mettre en oeuvre des simulations numériques.
Maitriser et mettre en oeuvre des outils et méthodes mathématiques de haut niveau.
Profil de sortie des étudiants ayant suivi la formation
L'objectif est que les étudiants sortent du master en sachant traiter les questions que l'on rencontre dans les sciences appliquées en lien avec l'optimisation, le contrôle optimal et la théorie des jeux : la modélisation mathématique d'un problème en termes de minimisation, maximisation ou équilibre, son analyse mathématique (existence, unicité, etc.), les approches algorithmiques pour la trouver ou l'approcher, et la mise en oeuvre effective de ces méthodes. On n'attend pas forcement que tous les élèves maîtrisent parfaitement tous ces aspects, cela pouvant dépendre de leur études antérieures et des directions choisies, mais qu'ils sachent comment s'orienter devant chacun de ces problèmes, et qu'ils aient une expérience avancée dans au moins un.
Débouchés de la formation
La plupart des étudiants font une thèse à l'issue de la formation, souvent en lien avec une entreprise (contrat CIFRE ou autre). Une minorité s'oriente vers le monde professionnel dès la fin du master.
Collaboration(s)
Laboratoire(s) partenaire(s) de la formation
Laboratoire de mathématiques d'Orsay
Laboratoire des Signaux et Systèmes.
Centre de Mathématiques Appliquées (Ecole Polytechnique)
Unité de Mathématiques Appliquées (ENSTA)
Fédération de Mathématiques (CentraleSupélec).
Programme
Les étudiants doivent suivre des cours parmi la liste ci-dessous.
?- Calcul des variations en dimension 1
- Semi-continuité des fonctionnelles intégrales
- Lien avec EDP elliptiques et fonctions harmoniques ; quelques résultats de régularité en utilisant la minimalité .
- $\Delta_p$, $\Delta_\infty$ et minimiseurs absolus.
- Problèmes sous contraintes de divergence en trafic et en mécanique (compliance) et dualité.
- Quelques notions sur les problèmes vectoriels (quasi- et poly-convexité\dots).
- Notions sur l'espace BV, problème isopérimétrique, existence et applications.
- Théorie générale de la $\Gamma$-convergence.
- Transition de phase, approximation à la Modica-Mortola.
- D'autres problèmes de calcul des variations, approfondissements.
Objectifs pédagogiques visés :
Contenu :
On étudiera les problèmes d'existence et caractérisation des minimiseurs dans les problèmes d'optimisation dans des classes de fonctions, avec une attention particulière aux problèmes issus de modèles physiques ou économiques, ainsi qu'aux problèmes géométriques les plus naturels. On étudiera aussi la notion de convergence pour une suite de problèmes variationnels, Gamma-convergence, et ses exemples les plus significatifs.
Bibliographie :
G. Buttazzo, M. Giaquinta, S. Hildebrandt, One-dimensional variational problems
E. Giusti, Direct Methods in the Calculus of Variations
A. Braides : Gamma-convergence for beginners.
The course is centered on the analysis and resolution of minimization problems of criteria related to deterministic control systems, with finite dimensional states, in continuous time, from two complementary points of view:
- Trajectorial approach, Pontryagin minimum principle (PMP), shoooting algorithm
- HJB (Hamilton-Jacobi-Bellman) approach: characterisation by the viscosity solutions theory
In both cases
- the numerical methods related to the discretization in time are discussed, and error estimates are established
- the theory is illustrated by numerous applications: spatial vehicles, cell populations, prey-predator systems, dam management, running races.
List of lessons
- 1: Introduction: examples, infinite dimension calculus
- 2 Pontryagi' minimim principle (PMP).
- 3: Applications of the PMP.
- 4: Minimal time, optimal syntheis
- 5: Shooting: theory and time discretization
- 6: TP on numerical methods
- 7: PMP with state constraints
- 8: Singular arcs
- 9: Introduction to infinite dimension: problems with delays
- 10 Reachable set, continuity of the value function
- 11 Equation HJB: existence, uniqueness, verification
- 12 Discretization of the HJB equation: error estimates.
Prérequis :
Basic knowledge in integration, calculus and optimization (Lagrange multipliers).
Bibliographie :
N.P. Osmolovskii, H. Maurer:
Applications to regular and bang-bang control: Second-order necessary and sufficient optimality conditions in calculus of variations and optimal control.
SIAM, 2012.
H. Sch{\"a}ttler, U. Ledzewicz:
Geometric optimal control. Springer, 2012.
M. Bardi, I. Capuzzo-Dolcetta:
Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations,
Birkhäuser, 1997
G. Barles:
Solutions de viscosité des équations de Hamilton-Jacobi.
Springer-Verlag, 1994.
Operations Research is an area of applied mathematics aiming at helping organizations to make better decisions. It relies on a variety of mathematical techniques to model and solve decision and optimization problems arising in many different contexts such as manufacturing, transportation, health care, telecommunications or financial planning. The objective of the course is to provide an introduction to Operations Research by focusing mainly on the use of mathematical programming while keeping a balance between theoretical material and practice. In the first part of the course, we will explore some of the mathematical foundations of operations research, through an introduction to linear programming and the theory of convex polyhedra. The second part of the course will consist of an introduction to mixed-integer linear programming.
- Introduction to Operations Research
- Linear programming: problem modelling, theory of convex polyhedra, simplex algorithm, application to real-world optimization problems, use of the mathematical programming solver CPLEX
- Mixed-integer linear programming (MILP): problem modelling, Branch & Bound algorithm, application to real-world optimization problems, use of the mathematical programming solver CPLEX
- Integer Quadratic Programming IQP: problem modelling, solution method via equivalent reformulation into an integer linear program.
Prérequis :
Linear algebra.
Bibliographie :
?- Introduction to Operations Research, 10th edition : F. S. Hillier, G.J. Liebermann, Editions McGraw-Hill, 2014.
- Theory of Linear and Integer Programming", Alexander Schrijver, Wiley, 1998
- Lectures on polytopes, Günter M. Ziegler, Springer, 1995
- Optimisation Discrète : Alain Billionnet, Editions Eyrolles 2007
- Mixed Integer Nonlinear Programming: Editors: Lee, Jon, Leyffer, Sven (Eds.) Springer 2012.
Tropical algebra deals with structures of “characteristic one”, in which the addition is idempotent. The max-plus semifield, which consists of the real numbers equipped with the maximum, thought of as an additive operation, and the addition, thought of as a multiplication operation, is the prototypical example of tropical structure. The tropical approach provides tools, of a combinatorial nature, to deal with deterministic and stochastic optimal control, and more generally, with zero-sum two player problems. It applies to the ergodic or long horizon problems, in which one is interested in a mean payoff per time unit, or in the growth of the income as the horizon tends to infinity. The objective of this lecture is to present tools and recent results inspired by tropical geometry, concerning control and games problems, paying a special attention to combinatorial and algorithmic results. Some results will be illustrated by examples from applications, including growth optimisation in population dynamics or web ranking.
This lecture makes also use of the operator approach of repeated games, in which the dynamic programming operators are studied from the metric geometry point of view. It develops some tools from non-linear Perron-Frobenius theory, dealing with order preserving operators on cones.This lecture has relatively few prerequisites, except elements of optimisation (convexity, polyhedra) and analysis (fixed point theory). The needed results are systematically recalled.
Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. Ceci explique l'essor de la discipline depuis son apparition. L'objectif de ce cours est d'approfondir les connaissances en théorie des graphes et algorithmique des graphes.
Dans la première partie, des notions et résultats généraux seront présentés : graphes bipartis, couplages, transversaux (vertex cover), isthmes et k-connexité, rappels flot max/coupe min ; théorèmes de base associés (lemme de Berge, théorème de König-Egervary, théorème de Hall, théorème de Ford-Fulkerson, théorème de Menger).
Dans la deuxième partie, on s'intéressera aux relations entre les problèmes d'optimisation dans les graphes et la programmation mathématique, notamment via la dualité et les approches primales-duales. On s'intéressera en particulier aux cas où la matrice associée à une formulation PLNE du problème de graphe est totalement unimodulaire.
Dans la troisième partie, on abordera la notion de d-facteur (qui généralise celle de couplage parfait), et les résultats associés.
Dans la quatrième partie, le sujet traité sera celui de la coloration des graphes dont les applications sont très nombreuses : on s'intéressera aux aspects de complexité et d'algorithmique, à l'étude de ces problèmes pour des graphes particuliers, aux graphes adjoints...
Prérequis :
Connaître les bases de la théorie des graphes et de la programmation linéaire continue ou en entiers.
The course presents both theoretical and numerical aspects of decision problems with uncertainty, where one sets a probabilistic framework in order to minimize the expectation of a cost. Two directions are explored:
- we investigate the so-called "open-loop" situation, that is, the case where decisions do not depend on information available for the problem, and we thoroughly study the stochastic gradient method and its variants,
- we also study "closed-loop" optimization problems, that is, the case where decisions are based on partial information (often corresponding to measurements made in the past when facing an unknown future).
Such problems are of course well-motivated by decision problems in the industry. They also have a deep mathematical content, especially in the dynamic case when only the past information is available. In this setting the decision is a function in a high dimensional space and therefore the numerical aspects also are challenging.
The aim of this course is to introduce different stochastic control models and to present dynamic programming as a tool for solving them. Illustrations selected among stock management, portfolio selection, yield management, transportation or Web PageRank optimisation will be presented.
We shall consider essentially stochastic dynamical systems with discrete time and finite state space, or finite Markov chains. This framework already contains the essential difficulties (for instance for long term problems), and allows one to give at the same time an insight of algorithms, mathematical techniques and qualitative properties. We may however consider some examples with infinite state space or continuous time.
We shall present the different types of stochastic control problems: complete and incomplete observation problems, criteria with finite horizon, discounted infinite horizon, stopping time, ergodic criteria, risk-sensitive criteria, constrainted problems, armed bandit problems. For some of these criteria, we shall state the corresponding dynamic programming equations, study their qualitative properties, and the algorithms for solving them (value iterations, policy iterations, linear programming), and deduce in some cases the structure of optimal strategies.
This course will present the main models of strategic games, related mathematical tools, important results and applications.
1- Decision problems (one-player games): Preference relations, utility and payoff functions, decision under risk and VnM axioms, representation theorems.
2- Zero-sum games: MinMax Theorems, pure and mixed strategies.
3- n-player games: Dominance and Rationalizability. Nash equilibria and fixed points, correlated equilibria.
4- Extensive form games: perfect information and backward induction, Zermelo and Kuhn's Theorems. Imperfect information, mixed and behavioral strategies, perfect recall and equivalence Theorems.
The standpoint of this course is built on three objectives : to give a unified overview of game theory to the students (direct game theory and mechanism design, strategic form and coalition form, analysis and algorithms, etc) ; to provide students a good and rigorous methodology to study equilibria in games ; to show to sthe tudents through fundamental case studies how game theory is applied in practice (5G wireless networks, smart energy networks, viral marketing). Technically, the following aspects will be developped :
- Methodologies to study equilibria in games (existence theorems, uniqueness –when relevant-, efficiency, ...).
- Important special classes of games : potential games, S-modular games, and congestion games. Mathematical properties and applications.
- Repeated games and stochastic games : Folk theorems for the case with perfect monitoring and imperfect monitoring. First connections with Shannon theory coding theorems.
- Coalitional form games (solution concepts such as the core and nucleolus, existence theorems, ...)
- Multi-agent learning. Description and analysis of well-known learning rules : reinforcement learning in games, regret matching, etc. The role of stochastic approximation.
L'objectif du séminaire est de donner aux étudiants une vue de thématiques de recherches actuelles en optimisation, théorie des jeux et contrôle. Chaque séance sera constitué d'un exposé d'un chercheur ou d'un étudiant, suivi d'une discussion avec les étudiants.
This course considers optimization problems constrained by a certain PDE called the state equation, which allows to express the state as function of the control (the decision variable). We discuss the well-posedness of the control to state mapping, the existence of solution and the first-order optimality conditions in the setting of elliptic and parabolic equations. For state constrained problems we see how the alternative optimality system provides regularity results for the optimal control. We also study time-optimal problems and establish second-order optimality conditions (and a related sensitivity analysis of the value function) in the polyhedric
setting. These results will be applied to a protein synthesis problem whose model is an ODE-PDE coupling with control in the coefficients ofthe PDE.
List of lessons
Lecture 1 : Motivating examples, tools from functional analysis, Fourier transform; costate equation, optimality system
Lecture 2 : Sobolev spaces, Lax-Milgram setting, Dirichlet and Neumann boundary control, semilinear state equations
Lecture 3 : Parabolic setting: application to the Fokker-Planck equation. Semilinear state equations.
Lecture 4 : ODE-PDE coupling. Application to a protein synthesis problem.
Lecture 5 : State constraints, alternative optimality system. Time optimal problems.
Lecture 6 : Second-order optimality conditions: polyhedricity theory.
Prérequis :
Basic knowledge in integration, PDEs and optimization (Lagrange multipliers).
Bibliographie :
J.F. Bonnans, A. Shapiro, Perturbation Analysis of Optimization Problems. Springer, 2000.
J.-L. Lions, Optimal Control of Systems Governed by Partial Differential Equations. Springer, 1971.
J.-P. Raymond, Optimal Control of Partial Differential Equations. Lecture notes, U.P.S., Toulouse.
F. Tröltzsch: Optimal Control of Partial Differential Equations - Theory, Methods and Applications. American Math. Society, 2010.
Yacine Chitour (Université Paris-Saclay)
Frédéric Jean (ENSTA)
Dario Prandi (CNRS).
Objectifs pédagogiques visés :
Contenu :
The aim of the course is to provide an introduction to control theory with a geometric viewpoint, i.e.
using tools from differential geometry. The couse is divided into two parts. In the first, we will study
the geometry of families of dynamical system, exhibing in particular the structure of the set of
trajectories. In the second, we wil deal with optimal control theory, stressing in particular the
Pontryagin Maximum Principle and its underlying geometry, in connection with properties of hypo-
elliptic operators.
This course is given by a renowned invited research, usually international, who presents his research to an audience comprising M2 Students, PhD Students and industrial researchers.
Prérequis :
Basic knowledge of optimisation, control or game theory -- depending on the topic of the course.
Intitulé de l’UE en anglais :
Optimization and statistics
ECTS :
4
Détail du volume horaire :
Cours :20
Modalités d'organisation et de suivi :
Coordinateur :Bach Francis
Déroulement et organisation pratique :
Volume Horaire : 20h. Validation du cours
(a) Prise de notes manuscrites en Latex pour chacune des seances
(b) Lecture d’articles.
Objectifs pédagogiques visés :
Contenu :
De nombreux problèmes d’estimation en apprentissage statistique sont formulés comme des problèmes d’optimisation. Ces formulations ont permis une separation entre l’analyse des performances de l’estimateur et le développement d’algorithmes de résolution du problème. Face aux grands volumes de données, une telle séparation n’est plus efficace et l’analyse doit mêler statistique et optimisation. Dans ce cours, seront présentés de manière unifiée les résultats statistiques classiques sur la M-estimation et l’optimisation convexe, en montrant les liens entre statistique et optimisation. Un accent sera mis sur l’analyse non-asymptotique de l’approximation stochastique.
Fiche de choix de M2 (obligatoire pour les candidats inscrits en M1 à l'Université Paris-Saclay) à télécharger sur https://urlz.fr/i3Lo.
Document justificatif des candidats exilés ayant un statut de réfugié, protection subsidiaire ou protection temporaire en France ou à l’étranger (facultatif mais recommandé, un seul document à fournir) :
- Carte de séjour mention réfugié du pays du premier asile
- OU récépissé mention réfugié du pays du premier asile
- OU document du Haut Commissariat des Nations unies pour les réfugiés reconnaissant le statut de réfugié
- OU récépissé mention réfugié délivré en France
- OU carte de séjour avec mention réfugié délivré en France
- OU document faisant état du statut de bénéficiaire de la protection subsidiaire en France ou à l’étranger.
