Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Efficient Methods in Optimization - WMM9AM16

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Number of hours

    • Lectures : 18.0
    • Tutorials : -
    • Laboratory works : -
    • Projects : -
    • Internship : -
    • Written tests : -
    ECTS : 3.0
  • Officials : Roland HILDEBRAND

Goals

The student will have an overview over modern methods of convex programming and their problem solving capabilities. He will be able to recognize a convex problem and to formulate it in standard form.

Content

Theoretical foundations of convex optimization.

This course deals with:
Topic 1: convex analysis
Topic 2: convex programming

Basic notions: vector space, affine space, metric, topology, symmetry groups, linear and affine hulls, interior and closure, boundary, relative interior

Convex sets: definition, invariance properties, polyhedral sets and polytopes, simplices, convex hull, inner and outer description, algebraic properties, separation, supporting hyperplanes, extreme and exposed points, recession cone, Carathéodory number, convex cones, conic hull

Convex functions: level sets, support functions, sub-gradients, quasi-convex functions, self-concordant functions

Duality: dual vector space, conic duality, polar set, Legendre transform

Optimization problems: classification, convex programs, constraints, objective, feasibility, optimality, boundedness, duality

Linear programming: Farkas lemma, alternative, duality, simplex method

Algorithms: 1-dimensional minimization, Ellipsoid method, gradient descent methods, 2nd order methods

Conic programming: barriers, Hessian metric, duality, interior-point methods, universal barriers, homogeneous cones, symmetric cones, semi-definite programming

Relaxations: rank 1 relaxations for quadratically constrained quadratic programs, Nesterovs ?/2 theorem, S-lemma, Dines theorem

Polynomial optimization: matrix-valued polynomials in one variable, Toeplitz and Hankel matrices, moments, SOS relaxations

Prerequisites

Linear algebra: matrices, vector spaces, linear functions

Analysis: differentiability, gradients, convergence, continuity

Tests

The course is composed of 18 hours lectures.

Evaluation : A two-hours written exam (E1) in session 1. For those who do not pass there will be another two-hours exam (E2) in session 2.

N1 = E1
N2 = E2

The exam is given in english only FR

Calendar

The course exists in the following branches:

  • Curriculum - Master 2 in Applied Mathematics - Semester 9 (this course is given in english only EN)
  • Curriculum - Master 2 in Applied Mathematics - Semester 9 (this course is given in english only EN)
see the course schedule for 2020-2021

Additional Information

Course ID : WMM9AM16
Course language(s): FR

You can find this course among all other courses.

Bibliography

Aharon Ben-Tal, Laurent El Ghaoui, Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.

Aharon Ben-Tal, Arkadi Nemirovski. Lectures on Modern Convex Optimization - Analysis, Algorithms, and Engineering Applications. Vol. 2 of MPS/SIAM Series on Optimization. SIAM, 2001.

Steven Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

Jean-Bernard Lasserre. Moments, Positive Polynomials and their Applications. Vol. 1 of Imperial College Press Optimization Series. Imperial College Press, 2009.

Yurii Nesterov, Arkadi Nemirovski. Interior-Point Algorithms in Convex Programming. Vol. 13 of SIAM Stud. Appl. Math. SIAM, Philadelphia, 1994.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

Date of update January 15, 2017

Université Grenoble Alpes