The Université Paris-Saclay website is currently being updated following the cyberattack it underwent in August. Certain information may not yet have been updated. We are working as quickly as we can to update all of the website’s content. Thank you for your understanding.
Optimization is at the confluence of mathematics, computer science and economics, and its importance is growing both in academia and in industry. The Optimization master program deals with all components of mathematical optimization understood in the broadest sense, with a particular focus on those specific to Paris-Saclay, which is strenghtened by the presence of the Gaspard Monge Program for Optimization (PGMO). The themes include: optimal control (discrete and continuous time, deterministic and stochastic), game theory (theory, modeling in economics and networks), calculus of variations (and more generally optimization in analysis and PDE), stochastic optimization and stochastic methods for optimization, operation research. A significant part of the courses are shared with other programs and specialties in mathematics, computer science and economics.
Watch the video below to know more about the M2 Optimization.
Skills
Understand and mathematically model a problem in order to resolve it.
Clearly explain a theory and mathematical results.
Be proficient in the use of digital tools and major programming languages.
Analyse a research paper with a view to summarising it and using it.
Analyse data and implement digital simulations.
Understand and proficiently use high-level mathematical tools and methods.
Post-graduate profile
The programme aims to prepare graduates to deal with the matters that arise in the applied sciences surrounding optimisation, optimal control and game theory: the mathematical modeling of a problem in terms of minimisation, maximisation or equilibrium, its mathematical analysis (existence, uniqueness, etc.), algorithmic approaches to determine such a problem or tackle it, and the effective implementation of those methods. Students are not necessarily expected to have a perfect command of all these aspects, since that depends on their previous studies and their chosen path: but they are expected to know how to position themselves faced with such problems, and they should have advanced experience in at least one.
Career prospects
Most students go on to do a thesis at the end of the programme, often in connection with a company (CIFRE industry contract or other contract). A minority enter working life at the end of the Master's.
Collaboration(s)
Laboratories
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.
Prerequisites :
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.
Prerequisites :
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...
Prerequisites :
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.
Prerequisites :
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.
Prerequisites :
Basic knowledge of optimisation, control or game theory -- depending on the topic of the course.
Title of educational component in English :
Optimization and statistics
ECTS :
4
Détail du volume horaire :
Lecture :20
Modalités d'organisation et de suivi :
Coordinator :Bach Francis
Procedure and organisation :
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.
Title of educational component in English :
Internship or Report
ECTS :
21
Détail du volume horaire :
Lecture :0
Modalités d'organisation et de suivi :
Coordinator :Mérigot Quentin
Pedagogical team :
Quentin Mérigot.
Période(s) et lieu(x) d’enseignement :
Period(s) :
Avril;Mai;Juin;Juillet.
Location :
ORSAY
Modalités de candidatures
Application period
From 01/03/2024 to 16/07/2024
Compulsory supporting documents
Motivation letter.
All transcripts of the years / semesters validated since the high school diploma at the date of application.
Curriculum Vitae.
Additional supporting documents
Supporting documents (TOEFL, TOEIC, certificate of a teacher ...) of a level of a foreign language.
VAP file (obligatory for all persons requesting a valuation of the assets to enter the diploma).
The application procedure, which depends on your nationality and your situation is explained here : https://urlz.fr/i3Lo.
Supporting documents :
- Residence permit stating the country of residence of the first country
- Or receipt of request stating the country of first asylum
- Or document from the UNHCR granting refugee status
- Or receipt of refugee status request delivered in France
- Or residence permit stating the refugee status delivered in France
- Or document stating subsidiary protection in France or abroad
- Or document stating temporary protection in France or abroad.
