L'optimisation mathématique ou la programmation mathématique est la sélection d'un meilleur élément (par rapport à un critère) parmi un ensemble d'alternatives disponibles.

Des problèmes d'optimisation de toutes sortes se posent dans toutes les disciplines quantitatives, de l'informatique et de l'ingénierie à la recherche opérationnelle et à l'économie, et le développement de méthodes de résolution intéressent les mathématiques depuis des siècles.

Dans le cas le plus simple, un problème d'optimisation consiste à maximiser ou minimiser une fonction réelle en choisissant systématiquement des valeurs d'entrée dans un ensemble admissible et en calculant la valeur de la fonction. La généralisation de la théorie et des techniques d'optimisation à d'autres formulations constitue un vaste domaine des mathématiques appliquées. Plus généralement, l'optimisation comprend la recherche des «meilleures valeurs disponibles» d'une fonction objectif étant donné un domaine (ou entrée) défini, y compris une variété de différents types de fonctions objectives et différents types de domaines. Le mot optimisation est employé dans plusieurs matières :

·         en mathématiques, l'optimisation traite de la recherche d'un extremum d'une fonction, dont les entrées peuvent être soumises à des contraintes;

·         en informatique, l'optimisation de code permet d'améliorer les performances d'un logiciel :

o    plus particulièrement dans les bases de données, l'optimisation de requête définit la meilleure exécution par le SGBD d'un code donné,

o    l'optimisation pour les moteurs de recherche permet d’améliorer le classement d'un site web dans les résultats d'une requête sur les moteurs de recherche ;

·         en finance, l'optimisation fiscale permet de minimiser l'imposition légalement.

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble.

Beaucoup de systèmes susceptibles d’être décrits par un modèle mathématique sont optimisés. La qualité des résultats et des prédictions dépend de la pertinence du modèle, du bon choix des variables que l'on cherche à optimiser, de l’efficacité de l’algorithme et des moyens pour le traitement numérique.

Formellement, l'optimisation est l’étude des problèmes qui s'expriment de la manière suivante :

Étant donné une fonction définie sur un ensemble  à valeurs dans l'ensemble   des nombres réels.

Trouver un élément  de tel que  pour tous les  dans  (minimisation), ou bien, pour tous les  dans  (maximisation).

On peut représenter alors un problème d’optimisation par un couple (A,f) avec :

·         Espace de recherche : ensemble des solutions possibles .

·         Fonction objectif : critère de qualité (ou de non-qualité) .

Une telle formulation est appelée un problème d'optimisation ou un problème de programmation mathématique (terme non directement lié à la programmation informatique, mais toujours utilisé par exemple en programmation linéaire). De nombreux problèmes du monde réel et théoriques peuvent être modélisés dans ce cadre général.

Les problèmes formulés à l'aide de cette technique dans les domaines de la physique peuvent désigner la technique de minimisation de la consommation d'énergie, parlant de la valeur de la fonction f comme représentant l'énergie du système modélisé. En apprentissage automatique, il est toujours nécessaire d'évaluer en continu la qualité d'un modèle de données en utilisant une fonction de coût où un minimum implique un ensemble de paramètres éventuellement optimaux avec une erreur optimale (la plus faible).

On dit que l'on cherche à minimiser (ou maximiser) la fonction   sur l’ensemble .La fonction   porte divers noms : fonction-coût ou simplement coût, fonction-objectif ou simplement objectif, critère, etc.

L'ensemble   est appelé l'ensemble admissible et les points de  sont appelés les points admissibles du problème (surtout lorsqu'il s'agit d'une partie d'un autre ensemble {\displaystyle B} et que l'on ne veut pas que {\displaystyle {\bar {x}}}appartienne au complémentaire {\displaystyle B\setminus A}). On dit que le problème est réalisable si   est non vide (l'ensemble admissible étant souvent défini de manière implicite, son caractère non vide n'est pas nécessairement évident, ce qui justifie le besoin de ce concept de réalisabilité). Le domaine  de  est appelé espace de recherche ou ensemble de choix, tandis que les éléments de  sont appelés solutions candidates ou solutions réalisables.

La fonction  est appelée, diversement, une fonction objectif, une fonction de perte ou fonction de coût (minimisation), une fonction d'utilité ou fonction de fitness (maximisation), ou, dans certains domaines, une fonction énergétique ou fonctionnelle énergétique. Une solution réalisable qui minimise (ou maximise, si tel est le but) la fonction objectif est appelée solution optimale.

Les opérateurs arg min et arg max sont parfois aussi écrits comme argmin et argmax, et représentent l'argument du minimum et l'argument du maximum.Trouver la (ou les) meilleure solution selon le critère de qualité(Dans le cas de maximisation) .

En mathématiques, les problèmes d'optimisation classiques sont généralement énoncés en termes de minimisation.

Un minimum local  est défini comme un élément pour lequel il existe un  tel que :

où

l’expression  est vérifiée;

C'est-à-dire que sur une région autour de , toutes les valeurs de fonction sont supérieures ou égales à la valeur de cet élément. Les maxima locaux sont définis de la même manière.

Alors qu'un minimum local est au moins aussi bon que n'importe quel élément à proximité, un minimum global est au moins aussi bon que chaque élément réalisable. Généralement, à moins que la fonction objectif ne soit convexe dans un problème de minimisation, il peut y avoir plusieurs minima locaux. Dans un problème convexe, s'il y a un minimum local qui est intérieur (pas sur le bord de l'ensemble des éléments réalisables), c'est aussi le minimum global, mais un problème non convexe peut avoir plus d'un minimum local dont tous ne sont pas forcément des minima globaux.

Un grand nombre d'algorithmes proposés pour résoudre les problèmes non convexes - y compris la majorité des solveurs commerciaux - ne sont pas capables de faire une distinction entre les solutions localement optimales et les solutions globalement optimales, et traiteront les premières comme des solutions réelles au problème d'origine. L'optimisation globale est la branche des mathématiques appliquées et de l'analyse numérique qui s'intéresse au développement d'algorithmes déterministes capables de garantir la convergence en temps fini vers la solution optimale réelle d'un problème non convexe.

Les problèmes d'optimisation peuvent aussi être divisés en deux catégories, selon que les variables sont continues ou discrètes:

Un problème d'optimisation avec des variables discrètes est connu sous le nom d'optimisation discrète, dans laquelle un objet tel qu'un entier, une permutation ou un graphique doit être trouvé à partir d'un ensemble dénombrable.

Un problème avec des variables continues est connu comme une optimisation continue, dans laquelle une valeur optimale d'une fonction continue doit être trouvée. Ils peuvent inclure des problèmes contraints et des problèmes multimodaux.

Pour résoudre des problèmes d’optimisation, les chercheurs peuvent utiliser des algorithmes qui se terminent par un nombre fini d'étapes, ou des méthodes itératives qui convergent vers une solution (sur une classe spécifique de problèmes), ou des heuristiques qui peuvent fournir des solutions approximatives à certains problèmes (bien que leurs itérations n'aient pas besoin converger).

Parmi les méthodes de résolution des problèmes d’optimisation, on trouve la catégorie des algorithmes d'optimisation, la catégorie des méthodes itératives, la catégorie de la convergence globale, et la catégorie des heuristiques et méta-heuristiques qui font l’objet général du contenu de ce polycopié cours d’optimisation avancée.

 

L’optimisation a plusieurs applications possibles, on peut citer à titre d’exemple :

·         La mécanique,

·         L’économie et la finance,

·         Le génie électrique,

·         Le génie civil,

·         La recherche opérationnelle,

·         La technique de contrôle,

·         La géophysique,

·         La modélisation moléculaire,

·         la biologie des systèmes informatiques ;

·         Apprentissage automatique.

Alors, pour avoir un bon modèle du problème d’optimisation, il faut transformer le problèmeréel en un problème d'optimisation, en faisant appel à des technique d’abstraction de la réalité, la simplification en gardant les éléments pertinents par rapport au problème à résoudre. Et ça nécessite aussi une connaissance experte du domaine ainsi qu’une connaissance des méthodes de résolution (informatique)

 


Figure 1. Résoudre un problème d'optimisation en mode réel.

Dans le reste de ce polycopié,  les différents algorithmes sont présentés dont le principal objectif étant d'appréhender les propriétés et les fonctionnalités les plusintéressantes de ces algorithmes pour l'apprentissage numérique et en particulier desréseaux de neurones. On développera les notions d’optimisation avancée et particulièrementon s’intéressera à la résolution de l’amélioration des problèmes en classification àl’aide des différents algorithmes évolutionnaires.