Program (detailed contents):
– Elements of convex analysis: convexity, lower semi-continuity, notion of subdifferential, elements of analysis for algorithmic purposes (Lipschitz gradient functions, strong convexity, conditioning)
– Optimality conditions (Karush Kuhn Tucker conditions, second order sufficient conditions)
– Lagrangian duality
– Algorithms for unconstrained differentiable optimization and link with ODEs: generalities on descent methods, gradient algorithms, Newton and quasi-Newton algorithms. Convergence study and convergence speed depending on the geometry of the functions to be minimized.
– Algorithms for constrained differentiable optimization: SQP, penalization methods, augmented Lagrangian.
– Convex optimization: how convexity can improve the convergence speed of algorithms.
– Inertial algorithms, Nesterov acceleration. Subgradient algorithms. Notion of proximal operator, Moreau regularization, proximal algorithms. Splitting methods: Forward Backward algorithm and Nesterov acceleration (FISTA). Study of convergence and convergence rate on the class of convex functions.
Objectifs
At the end of this module, the student will have understood and be able to explain (main concepts):
* Existence and uniqueness conditions for solutions of an optimization problem (constrained differentiable optimization, non-differentiable convex optimization)
* Optimality conditions: Karush Kuhn Tucker points in the constrained differentiable case, optimality NHA in unconstrained convex optimization.
* The duality principle: Lagrangian duality, Fenchel-Rockafellar duality
* Gradient and Newton type algorithms, and their convergence results, classical algorithms of constrained optimization:
* The general principle of inertial algorithms: acceleration of gradient algorithms, generalization to the composite case.
The student will be able to:
- Interpret the behavior of an algorithm as a discretization of a dynamic system
- Identify classes of optimization problems and propose algorithms adapted to the geometry of the functions to be minimized.
- Implement and numerically calibrate these algorithms.
Pré-requis
Basics of differential calculus and linear algebra.
3rd year MIC optimization course
Évaluation
L’évaluation des acquis d’apprentissage est réalisée en continu tout le long du semestre. En fonction des enseignements, elle peut prendre différentes formes : examen écrit, oral, compte-rendu, rapport écrit, évaluation par les pairs…
