– Introduction to constrained optimization: definitions and generalities, existence of solutions, convexity and uniqueness
– Optimality conditions: first and second order conditions in unconstrained differentiable optimization, Karush-Kuhn-Tucker (KKT) conditions in constrained differentiable optimization, Lagrangian notion
– Algorithms for unconstrained optimization: gradient algorithm (fixed step, optimal step), Newton’s algorithm, linear and nonlinear least squares problems
– Introduction to linear constrained optimization: modeling formalisms, characterization of the search space, geometric interpretation, graphical resolution, link with KKT conditions, simplex algorithm, method of dictionaries, complexity, duality of a PL problem, strong and weak duality theorems, complementary deviations theorems, Farkas lemma, alternatives theorem.
Detailed course handout provided.
Keywords : differentiable optimization, first and second order optimality conditions, gradient algorithms, Newton, least squares problems, linear programming and simplex algorithm.
Objectifs
At the end of this module, the student will have understood and be able to explain (main concepts):
- The notions of local extremum and convexity
- Characterization of a local extremum by optimality conditions: first and second order conditions in unconstrained differentiable optimization, Karush-Kuhn-Tucker (KKT) conditions in constrained differentiable optimization
- The first algorithms for unconstrained optimization: gradient algorithm (fixed step, optimal step), Newton's algorithm, linear and nonlinear least squares problems
- Optimization under linear constraints (Linear Programming/PL): modeling in PL, characterization of the search space, geometric interpretation, solution principle, simplex algorithm, dictionary methods, complexity, duality.
The student will be able to:
Choose and implement a relevant and numerically efficient optimization method for an unconstrained differentiable optimization problem or for a linear programming problem.
Pré-requis
Differential calculus: know how to calculate a gradient and a hessian. Link with differential.
Linear algebra: know how to diagonalize a matrix, calculate the eigenvalues, notion of semi-definite positivity.
É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…
