Optimisation et Informatique

Cours 1

La programmation linéaire et mathématique (optimisation).

Le terme programmation fait référence ici au domaine de la prise de décision et non au codage informatique.

TD 1

La programmation mathématique est un ensemble de méthodes ou processus mathématiques dont le but est de trouver un optimum au moins local (on ne peut pas faire mieux avec des décisions proches) voire global (on ne peut pas faire mieux tout court, quelques soient les décisions) pour un problème décisionnel donné.La programmation linéaire (encore appelée optimisation linéaire) : elle est utilisé lorsque de grands volumes (des tonnages, des puissances électriques) sont en jeu et lorsque les relations entre ces quantités sont linéaires. la programmation linéaire en nombres entiers : c’est une extension de la méthode précédente qui permet de travailler aussi sur des petites quantités entières (nombre de bus, nombre d’avions) et décisions binaires (telle action est effectuée ou non).»..

TP 1

la programmation non linéaire : elle est utilisée lorsque les relations entre les décisions ne peuvent pas du tout être exprimées de façon linéaire, même avec des hypothèses simplificatrices. Elle est plus générale que la programmation linéaire mais a le défaut de ne pas garantir d’avoir les meilleures décisions. la programmation dynamique : adaptée aux cas où le problème décisionnel possède une propriété de sous-optimalité, c’est-à-dire que des décisions bonnes pour le problème global sont aussi bonnes pour des sous-problèmes.

Cours 2

En mathématiques, les matrices sont des tableaux de nombres qui servent à interpréter en termes calculatoires et donc opérationnels les résultats théoriques de l'algèbre linéaire et même de l'algèbre bilinéaire.

TD 2

Toutes les disciplines étudiant des phénomènes linéaires utilisent les matrices.

TP 2

Quant aux phénomènes non linéaires, on en donne souvent des approximations linéaires, comme en optique géométrique avec les approximations de Gauss.

Cours 3

L’optimisation est découpée en sous-disciplines qui se chevauchent, suivant la forme de la fonction objectif et celle des contraintes : l'optimisation en dimension finie ou infinie (on parle ici de la dimension de l'espace vectoriel des variables à optimiser), l'optimisation continue ou combinatoire (les variables à optimiser sont discrètes dans ce dernier cas), commande optimale, l'optimisation stochastique (en) et robuste (présence d'aléas), l'optimisation multicritère (un compromis entre plusieurs objectifs contradictoires est recherché).

TD 3

L'optimisation différentiable ou non lisse (on qualifie ici la régularité des fonctions définissant le problème), l'optimisation linéaire (fonctions affines), quadratique (objectif quadratique et contraintes affines), semi-définie positive (la variable à optimiser est une matrice dont on requiert la semi-définie positivité), copositive (la variable à optimiser est une matrice dont on requiert la copositivité), conique (généralisation des disciplines précédentes, dans laquelle on minimise une fonction linéaire sur l'intersection d'un cône et d'un sous-espace affine), convexe (fonctions convexes), non linéaire.

TP 3

L'optimisation algébrique (fonctions polynomiales), l'optimisation bi-niveaux, l'optimisation sous contraintes de complémentarité, l'optimisation disjonctive (l'ensemble admissible est une réunion d'ensembles), etc.

Cours 4

L'idée principale des heuristiques est d'explorer l'espace des solutions en essayant de converger vers la meilleure solution. Cependant, il est important d’éviter une convergence prématurée de l'algorithme vers un extremum, ou optimum, local. Un extremum local est la meilleure solution dans une zone restreinte, en opposition à l’extremum global, qui est la meilleure solution dans l’ensemble..

TD 4

Une métaheuristique est un algorithme d'optimisation visant à résoudre des problèmes d'optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît pas de méthode classique plus efficace.

TP 4

Les algorithmes génétiques utilisent la théorie de Darwin sur l’évolution des espèces. Elle repose sur trois principes : le principe de variation, le principe d'adaptation et le principe d'hérédité..