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

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