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.
L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.
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.
Histoire et dénomination Antiquité Les premiers problèmes d'optimisation auraient été formulés par Euclide, au avant notre ère, dans son ouvrage historique Éléments. Trois cents ans plus tard, Héron d'Alexandrie dans Catoptrica énonce le « principe du plus court chemin » dans le contexte de l'optique. (voir figure).
vignette|250px|droite| Le plus court chemin pour aller de A à C en passant par un point 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 passant par B).
Introduction de calcul différentiel Au , 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 LeibnizVoir l'article « Méthode de Newton ».. 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 , les travaux des mathématiciens Euler et Lagrange mènent au calcul des variations, 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.
Développements, applications et dénomination Le 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 de 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 vers 1947.. 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.
Ainsi, à partir de 1939, le mathématicien Leonid Kantorovitch commence des travaux théoriques sur l'optimisation linéaire afin d'en tirer des applications concrètes à l'optimisation de la production économique planifiée de l'Union soviétique.
L'expression « programmation mathématique », qui requiert la longue explication ci-dessus, tend à être abandonnée. Par exemple, en juin 2010, la société savante internationale qui représente cette discipline a vu son nom précédent changé en . ; pour la même raison, on préfère aujourd'hui utiliser les locutions « optimisation linéaire/quadratique/… » au lieu de « programmation linéaire/quadratique/… »
Définitions vignette|Illustration de l'algorithme de gradient
Minimisation
Plus formellement, l'optimisation est l’étude des problèmes qui s'expriment de la manière suivante.
On dit que l'on cherche à minimiser 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 et que l'on ne veut pas que appartienne au complémentaire ). 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 point est appelé solution du problème d'optimisation (ou minimum ou minimiseur). On l'appelle aussi parfois une solution globale pour le distinguer des notions locales introduites ci-dessous. On dit qu'il s'agit d'un minimum strict si et pour tout .
On peut écrire ce problème de différentes manières :
On note parfois
l'ensemble des solutions du problème.
L'ensemble est une partie de (ou de si est valeurs dans ) et sa borne inférieure (ou infimum) est appelée la valeur optimale du problème. Cette valeur optimale est atteinte (c'est-à-dire qu'il existe un tel que ) si, et seulement si, le problème d'optimisation a une solution. Si , on dit que le problème est borné.
On dit que le problème est convexe si est une partie convexe d'un espace vectoriel et si est une fonction convexe sur .
Maximisation Le problème décrit ci-dessus est un problème de minimisation. Comme on a
un problème de maximisation d'une fonction (à gauche ci-dessus) est équivalent au problème de minimisation de (à droite ci-dessus). L'équivalence veut dire ici que les solutions sont les mêmes et que les valeurs optimales sont opposées. En particulier, une méthode pour analyser/résoudre un problème de minimisation pourra être utilisée pour analyser/résoudre un problème de maximisation.
Solution locale
Sous certaines conditions, le processus d'optimisation trouve le maximum global. Mais dans certains cas d'optimisation - comme les réseaux de neurones artificiels, le résultat peut être une solution locale.
Un maximum local est un point de tel qu'il existe un voisinage où pour tout , . Un minimum local est défini semblablement.
Il est en général facile de déterminer numériquement des maxima locaux avec des algorithmes de descentes - comme avec l'Algorithme du gradient. Pour vérifier que la solution trouvée est un maximum global, il est parfois possible de recourir à des connaissances additionnelles sur le problème. Selon la nature de ou de la fonction , divers théorèmes assurent des propriétés particulières de la solution qui simplifient sa recherche (voir ).
Optimisation combinatoire Le plus souvent, est un sous-ensemble de l’espace euclidien . Lorsque est un sous-ensemble de ou de , constitué des vecteurs satisfaisant un certain nombre de contraintes (de type égalité ou inégalité), on parle d'optimisation combinatoire.
Généralisation Dans un cadre plus général, l'optimisation peut être définie pour des fonctions à valeurs dans un ensemble ordonné, plutôt que seulement l'ensemble des nombres réels.
Dans cette définition, peut être un ensemble de nombres réels, d'espaces vectoriels, de structures ordonnées ou de tout autre ensemble sur lequel une relation d'ordre est définie. La fonction représente la fonction objectif, qui mesure la performance ou la qualité des solutions. L'objectif de l'optimisation est de trouver la meilleure solution qui minimise ou maximise la fonction objectif, selon les critères déterminés par la relation d'ordre.
Quelques classes de problèmes
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), 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, la commande optimale, l' et robuste (présence d'aléas), l'optimisation multicritère (un compromis entre plusieurs objectifs contradictoires est recherché), 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)
vignette|centré|upright=3.5|Classification des problèmes selon la fonction-coût.
vignette|centré|upright=3.5|Classification des problèmes selon l'ensemble admissible (contraintes).
vignette|Fonction-coût différentiable non-convexe avec lignes de niveau pour un espace à deux dimensions.
Cette abondance de disciplines provient du fait que pratiquement toute classe de problèmes modélisables peut conduire à un problème d'optimisation, pourvu que l'on y introduise des paramètres à optimiser. Par ailleurs, les conditions d'optimalité de ces problèmes d'optimisation apportent parfois des expressions mathématiques originales qui, par le mécanisme précédent, conduisent à leur tour à de nouveaux problèmes d'optimisation. L'optimisation linéaire étudie le cas où la fonction objectif et les contraintes caractérisant l’ensemble sont linéaires. C’est une méthode très employée pour établir les programmes des raffineries pétrolières, mais aussi pour déterminer la composition la plus rentable d’un mélange salé, sous contraintes, à partir des prix de marché du moment. L'optimisation linéaire en nombres entiers étudie les problèmes d'optimisation linéaire dans lesquels certaines ou toutes les variables sont contraintes de prendre des valeurs entières. Ces problèmes peuvent être résolus par différentes méthodes : séparation et évaluation, méthode des plans sécants. L'optimisation quadratique étudie le cas où la fonction objectif est une forme quadratique (avec contraintes linéaires pour ) L'optimisation non linéaire étudie le cas général dans lequel l’objectif ou les contraintes (ou les deux) contiennent des parties non linéaires, éventuellement non-convexes. L' étudie le cas dans lequel certaines des contraintes dépendent de variables aléatoires. En optimisation robuste, les aléas sont supposés être situés dans des intervalles autour de positions nominales et on cherche à optimiser le système soumis à de tels aléas, dans le pire des cas. La programmation dynamique utilise la propriété qu’une solution se compose nécessairement de sous-solutions optimales (attention : le contraire n'est pas vrai en général) pour décomposer le problème en évitant l’explosion combinatoire. Elle est utilisable lorsque la fonction objectif est une somme de fonctions monotones croissantes dont les arguments sont des inconnues distinctes. C’est la programmation dynamique qui permet par exemple :