logo Insalogo Insa

Optimisation I


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


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