# Optimisation

## Presentation

Program (detailed contents):

deterministic differentiable optimisation :

-Existence and unicity of constrained optimization (including convexity)

-Tangent cone, Farkas lemma, KKT points

-Line search, Wolfe conditions

-First order algorithms for unconstrained optimisation

-Second order algorithms for unconstrained optimisation (including BFGS)

-Lagrangian duality

-First and second order algorithms for unconstrained optimization (projected gradient, SQP, penalization methods, interior points, augmented Lagrangian)

-Algorithm convergence

Discrete stochastic optimization :

-Metropolis-Hastings method for simulating, approximately, a given probability distribution known modulo a multiplicative constant (construction of a reversible Markov chain, convergence to the invariant measure, speed of convergence).

-Simulated annealing algorithm (Gibbs measure, temperature scheme, proof of the algorithm convergence, parameter adjustment in practice).

-Genetic algorithms (general presentation, convergence results, parameter adjustment in practice).

## Objectives

At the end of this module, the student will have understood and be able to explain (main concepts):

-       Deterministic differentiable optimisation :

Existence and unicity of optimisation problems, KKT points, Convergence of optimization algorithm, Lagrangian duality

-       Discrete stochastic optimisation :

The Metropolis-Hastings algorithm, the simulated annealing algorithm, genetic algorithms.

The student will be able:

-          To identify families of optimization problems

-          To choose and implement suitable first and second order algorithms

-          To implement a Metropolis-Hastings algorithm in order to simulate, approximately, a given discrete probability distribution on a huge finite space.

-          To implement a simulated annealing algorithm and a genetic algorithm in order to minimize a given function on a huge finite space.

## Needed prerequisite

- Precedent courses on the following subjects : linear algebra, numerical analysis.

## Form of assessment

The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...