Optimisation (mathématiques) - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Définition - Techniques - Notation - Historique - Utilisations

Notation

Les problèmes d’optimisation sont souvent exprimés avec une notation spéciale. Voici quelques exemples :

On cherche la valeur minimale pour l’expression $x 2 + 1$ , où $x$ s’étend sur les nombres réels $\mathbb R$ . La valeur minimale dans ce cas est 1, s’occasionnant à $x = 0$ .

On cherche la valeur maximale pour l’expression $2 x$ , où $x$ s’étend sur les réels. Dans ce cas, il n’y a pas de tel maximum puisque l’expression n’est pas bornée, donc la réponse est « l’infini » ou « indéfini ».

On cherche la ou les valeurs de $x$ dans l'intervalle $]-\infty, -1]$ qui minimise l'expression $x 2 + 1$ . (La valeur minimale véritable de cette expression n'est pas importante.) Dans ce cas, la réponse est $x = - 1$ .

On cherche la ou les paires $(x, y)$ qui maximisent la valeur de l'expression $x cos(y)$ , avec la contrainte ajoutée que la valeur absolue de $x$ ne peut excéder 5. (À nouveau, la valeur maximale véritable de l'expression n'est pas importante.) Dans ce cas, les solutions sont les paires de la forme $(5,2 k π)$ et $( - 5,(2 k + 1)π)$ , où $k$ s'étend sur tous les entiers.

Historique

Les premiers problèmes d'optimisation auraient été formulés par Euclide, au IIIe siècle avant notre ère, dans son ouvrage historique Éléments. Trois cent ans plus tard, Héron d'Alexandrie dans Catoptrica énonce le principe du plus court chemin dans le contexte de l'optique. (voir figure)

Le plus court chemin pour aller de A à C en passant par un point B de la droite est obtenu lorsque l'angle d'incidence est égal à l'angle réfléchi (sur la figure, il s'agit du chemin vert).

Au XIIe siècle, l'apparition du calcul différentiel entraîne l'invention de techniques d'optimisation, ou du moins en fait ressentir la nécessité. Newton met au point une méthode itérative permettant de trouver les extrémums locaux d'une fonction en faisant intervenir la notion de dérivée, issue de ses travaux avec Leibniz. Cette nouvelle notion permet de grandes avancées dans l'optimisation de fonctions car le problème est ramené à la recherche des racines de la dérivée.

Durant le XVIIIe siècle, les travaux des mathématiciens Euler et Lagrange mènent au calcul variationnel, une branche de l'analyse fonctionnelle regroupant plusieurs méthodes d'optimisation. Ce dernier invente une technique d'optimisation sous contraintes: Les multiplicateurs de Lagrange.

Le XIXe siècle est marqué par l'intérêt croissant des économistes pour les mathématiques. Ceux-ci mettent en place des modèles économiques qu'il convient d'optimiser, ce qui accélère le développement des mathématiques. Depuis cette période, l'optimisation est devenue un pilier des mathématiques appliquées et le foisonnement des techniques est tel qu'il ne saurait être résumé en quelques lignes.

On peut tout de même évoquer l'invention plusieurs méthodes itératives utilisant le gradient de la fonction, ainsi que l'utilisation du terme programmation mathématique, pour désigner des problèmes d'optimisation. Historiquement, le premier terme introduit fut celui de programmation linéaire, inventé par George Dantzig dans les années 1940. Le terme programmation dans ce contexte ne réfère pas à la programmation informatique (bien que les ordinateurs soient largement utilisés de nos jours pour résoudre des programmes mathématiques). Il vient de l’usage du mot programme par les forces armées américaines pour établir des horaires de formation et des choix logistiques, que Dantzig étudiait à l’époque. L’emploi du terme « programmation » avait également un intérêt pour débloquer des crédits en une époque où la planification devenait une priorité des gouvernements.