logo Insalogo Insa

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

Optimisation [MIC3]

Markov chains and applications [MIC3]

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