L’optimisation est la branche des mathématiques qui vise à déterminer un extremum d’une fonction avec ou sans contraintes, en tant que modélisation d’une situation réelle. Si, dans le cas linéaire, cette détermination ne pose pas trop de difficulté, il n’en va pas de même dans le cadre non linéaire.

MAXIMUM ET MINIMUM MODÉLISÉS

L’optimisation est une branche des mathématiques qui a pour objet la détermination du maximum (ou du minimum) d’une fonction à valeurs dans l’ensemble des réels. En fait, cet objectif est double: d’une part, on souhaite trouver la valeur du maximum (ou du minimum), d’autre part on cherche le point pour lequel cette fonction atteint ce maximum (ou ce minimum). En pratique, on peut toujours ramener la recherche d’un maximum à celle d’un minimum, et inversement. L’optimisation est un outil mathématique, il permet donc de résoudre des situations modélisées. On part ainsi d’une situation réelle qu’il faut modéliser (c’est- à-dire qu’on doit trouver la fonction à maximiser, son ensemble de définition, ainsi qu’un modèle pour les contraintes quand il y en a). Ensuite, il ne reste plus qu’à résoudre, soit analytiquement (mathématiquement), soit numériquement (programme). Il existe un grand nombre de situations réelles qui font appel à l’optimisation: recherche opérationnelle, économie, transports, réseaux, etc.
FONCTION OBJECTIF ET SOLUTION OPTIMALE
Comme dans toute théorie mathématique, un vocabulaire spécifique caractérise l’optimisation. La fonction f, modèle de la situation réelle, s’appelle la « fonction objectif ». La valeur optimale est le résultat de la maximisation (ou minimisation) de f, qui se réalise en un certain point de l’ensemble de définition de f, appelé « solution optimale ». L’ensemble de définition de f s’appelle quant à lui l’« ensemble des solutions réalisables du problème ». Il existe deux grands types d’optimisation: avec ou sans contraintes. Lorsqu’il n’y a pas de contraintes, il faut juste déterminer le maximum (ou le minimum) sans conditions supplémentaires sur l’ensemble de définition de f. Il est en revanche nécessaire de réduire cet ensemble lorsque le problème est avec contraintes. Ces dernières peuvent se présenter sous forme soit d’égalités, soit d’inégalités. Dans ce cas, l’ensemble des solutions réalisables du problème sera plus petit, puisque ses éléments devront respecter les égalités ou les inégalités.
LINÉAIRE OU NON LINÉAIRE ?
On peut classer les problèmes d’optimisation (qu’ils soient avec ou sans contraires) dans deux grandes catégories: l’optimisation linéaire et l’optimisation non linéaire. Les problèmes d’optimisation linéaire sont, en général, les plus simples à résoudre, dans la mesure où la fonction objectif et les contraintes (quand il y en a) sont linéaires. Dans ce cadre, il existe un certain nombre de méthodes de résolution, comme la méthode graphique, la méthode des sommets ou encore la méthode du simplexe. Dans le cadre de l’optimisation non linéaire, on part d’une fonction quelconque, qui
À RETENIR
n’a, a priori, pas de propriétés particulières. Il faut alors se fixer des critères afin d’être capable de résoudre le problème. Il est ainsi possible de résoudre les problèmes d’optimisation non linéaire quand la fonction est une forme quadratique (fonction définie à l’aide d’une matrice symétrique) ou une fonction convexe (fonction devant satisfaire une certaine inégalité, dite « de convexité »).
EXTREMA LOCAUX ET EXTREMA GLOBAUX
Si, dans le cas de l’optimisation linéaire, l’étude des problèmes conduit à des solutions simples, tel n’est pas le cas dans les problèmes d’optimisation non linéaire. Pour simplifier le problème, on cherche en général des extrema locaux (sur une partie de l’ensemble des solutions réalisables), quitte à examiner par la suite si ce sont des extrema globaux (sur l’ensemble tout entier). Pour déterminer un point où la fonction atteint un extremum local, les méthodes consistent à construire une suite de points qui doit converger vers un point satisfaisant une condition nécessaire d’optimalité. Ce n’est souvent pas suffisant, et il faut alors effectuer une étude supplémentaire pour étudier le comportement de la fonction au voisinage de ce point, pour vérifier que c’est bien un extremum local. Dans le cas des problèmes sans contraintes, plusieurs méthodes existent, telles que la méthode du gradient, celle des gradients conjugués, celle de Newton ou l’optimisation unidimensionnelle.
OPTIMISATION NON LINÉAIRE AVEC CONTRAINTES
Le cas de l’optimisation non linéaire avec contraintes est de loin le cadre le plus difficile pour résoudre les problèmes. C’est un domaine de l’optimisation où beaucoup de choses restent à faire. Il existe cependant des exemples de conditions nécessaires pour qu’un point soit un extremum local: la condition de Lagrange, par exemple, ou bien la condition de Kuhn et Tucker. Dans ces deux cas, ce ne sont encore une fois que des conditions nécessaires. Il faut d’autres critères pour confirmer le fait que le point considéré est bien un extremum local. Un autre exemple de méthode est celle des directions admissibles. On peut évoquer également deux types d’optimisation encore plus difficiles et qui nécessitent des outils mathématiques très sophistiqués: d’une part, l’optimisation multicritère (l’ensemble de départ est à n dimensions) et l’optimisation stochastique (dans laquelle on travaille avec des données aléatoires, à ne pas confondre avec les méthodes stochastiques d’optimisation).
• L’optimisation mathématique vise à fournir des méthodes en vue de déterminer le maximum (ou le minimum) d’une fonction modélisant une situation réelle. Cette modélisation peut inclure ou non des contraintes
supplémentaires sur la valeur cherchée. On peut distinguer l’optimisation linéaire (la fonction
et les contraintes sont linéaires) de l’optimisation non linéaire. Dans ce dernier cas, il faut des critères
assez forts sur la fonction afin de pouvoir déterminer la solution optimale.