 # Optimisation I

## Presentation

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).

## 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

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 in order to minimize a given function on a huge finite space.

## Needed prerequisite

Optimisation [MIC3]

Markov chains and applications [I3MIMT11]

## 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...