Voir la source de Optimisation (mathématiques)

{{homon|Optimisation}}
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 (discipline)|économie]]), dans les [[mathématiques appliquées]] (fondamentales pour l'[[industrie]] et l'[[ingénierie]]), en [[Analyse (mathématiques)|analyse]] et en [[analyse numérique]], en [[statistique]] pour l’estimation du [[maximum de vraisemblance]] d’une [[distribution (mathématiques)|distribution]], pour la recherche de [[stratégie]]s dans le cadre de la [[théorie des jeux]], ou encore en [[théorie du contrôle]] et de la [[Automatique|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 {{s-|III}} avant notre ère, dans son ouvrage historique ''[[Éléments d'Euclide|É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]]<ref>{{lien web | url = http://www.apmep.asso.fr/IMG/pdf/Lu-33-Xhonneux-LaRochelle.pdf | titre = Perception de l’optimisation en mathématiques et en économie au fil des siècles et l’enseignement du théorème de Lagrange | auteur = Sebastian Xhonneux | site =[[APMEP]]| date = 2008-10-27 | consulté le = 2010-03-15}}.</ref> (voir figure).

[[Image:Principe du plus court chemin.png|vignette|250px|droite| Le plus court chemin pour aller de A à C en passant par un point de la [[Droite (mathématiques)|droite]] est obtenu lorsque l'[[angle]] d'incidence est égal à l'angle [[Miroir|réfléchi]] (sur la figure, il s'agit du chemin vert passant par B).]]

=== Introduction de calcul différentiel ===
Au {{s-|XVII}}, l'apparition du [[calcul différentiel]] entraîne l'invention de techniques d'optimisation, ou du moins en fait ressentir la nécessité. [[Isaac Newton|Newton]] met au point une [[méthode itérative]] permettant de trouver les [[Extremum|extrémums]] locaux d'une [[Application (mathématiques)|fonction]] en faisant intervenir la notion de [[dérivée]], issue de ses travaux avec [[Leibniz]]<ref>Voir l'article « [[Méthode de Newton]] ».</ref>.
Cette nouvelle notion permet de grandes avancées dans l'optimisation de fonctions car le problème est ramené à la recherche des [[Racine d'un polynôme|racines]] de la dérivée.

Durant le {{s-|XVIII}}, les travaux des [[mathématicien]]s [[Leonhard Euler|Euler]] et [[Joseph-Louis Lagrange|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 {{s-|XIX}} est marqué par l'intérêt croissant des [[économiste]]s pour les mathématiques. Ceux-ci mettent en place des [[modèle (économie)|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 (mathématiques)|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<ref>{{chapitre | langue = en |auteur=G. B. Dantzig | année = 1951 | titre chapitre = Maximization of a linear function of variables subject to linear inequalities|auteurs ouvrage= Tj. C. Koopmans|titre ouvrage = Activity Analysis of Production and Allocation | passage = 339–347 | éditeur = Wiley | lieu = New York}}.</ref>. 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 [[logistique]]s, 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{{refsou}}.

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 ''{{Lang|en|Mathematical Programming Society}}'' changé en ''{{Lang|en|[[Mathematical Optimization Society]]}}''<ref>{{lien web | url = http://www.mathopt.org | langue = en | titre = Mathematical Optimization Society (MOS) | site = mathopt.org<!--|consulté le=22/05/2017-->}}.</ref> ; 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 ==
[[Fichier:Gradient descent.png|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.

{{Théorème|Problème d'optimisation|Étant donné une [[fonction (mathématiques)|fonction]] <math>f : A \rightarrow \R</math> définie sur un ensemble <math>A</math> à valeurs dans l'ensemble <math>\R</math> des [[nombre réel|nombres réels]] (éventuellement dans la [[droite réelle achevée|droite achevée]] <math>\overline{\R}:=\R\cup\{-\infty,+\infty\}</math>), trouver un élément <math>\bar x</math> de <math>A</math> tel que <math>f(\bar x)\leqslant f(x)</math> pour tous les <math>x</math> dans <math>A</math>.}}

On dit que l'on cherche à ''minimiser'' la fonction <math>f</math> sur l'ensemble <math>A</math>.

La fonction <math>f</math> porte divers noms : ''fonction-coût'' ou simplement ''coût'', ''[[fonction objectif|fonction-objectif]]'' ou simplement ''objectif'', ''critère'', etc.

{{ancre|realisable}}
L'ensemble <math>A</math> est appelé l'''ensemble admissible'' et les points de <math>A</math> sont appelés les ''points admissibles'' du problème (surtout lorsqu'il s'agit d'une partie d'un autre ensemble <math>B</math> et que l'on ne veut pas que <math>\bar x</math> appartienne au complémentaire <math>B\setminus A</math>). On dit que le problème est ''réalisable'' si <math>A</math> 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 <math>\bar x</math> 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 <math>\bar x\in A</math> et <math>f(\bar x)<f(x)</math> pour tout <math>x\in A\setminus\{\bar x\}</math>.

On peut écrire ce problème de différentes manières :
<center>
<math>
\inf_{x\in A}\,f(x)
\quad\mbox{ou}\quad
\inf{\{f(x)\mid x\in A\}}
\quad\mbox{ou}\quad
\inf{f(A)}
\quad\mbox{ou}\quad
\left\{\begin{array}{l}
\inf{f(x)}\\
x\in A.
\end{array}\right.
</math>
</center>

On note parfois
<math>
\operatorname{arg\,min}\,\{f(x)\mid x\in A\}
</math>
l'ensemble des solutions du problème.

{{ancre|borne}}
L'ensemble <math>f(A):=\{f(x)\mid x\in A\}</math> est une partie de <math>\R</math> (ou de <math>\overline{\R}</math> si <math>f</math> est valeurs dans <math>\overline{\R}</math>) et sa [[Borne supérieure et borne inférieure|borne inférieure]] (ou infimum) <math>\inf{f(A)}</math> est appelée la ''valeur optimale'' du problème. Cette valeur optimale est ''atteinte'' (c'est-à-dire qu'il existe un <math>\bar x\in A</math> tel que <math>f(\bar x)=\inf\,f(A)</math>) si, et seulement si, le problème d'optimisation a une solution. Si <math>\inf{f(A)}>-\infty</math>, on dit que le problème est ''borné''.

{{ancre|problème convexe}}
On dit que le problème <math>\inf{\{f(x)\mid x\in A\}}</math> est ''convexe'' si <math>A</math> est une [[Ensemble convexe|partie convexe]] d'un [[espace vectoriel]] et si <math>f</math> est une [[fonction convexe]] sur <math>A</math>.

=== Maximisation ===
Le problème décrit ci-dessus est un problème de ''minimisation''. Comme on a
<center>
<math>
\sup_{x\in A}{f(x)}=-\inf_{x\in A}\left(-f(x)\right),
</math>
</center>
un problème de ''maximisation'' d'une fonction <math>f</math> (à gauche ci-dessus) est ''équivalent'' au problème de minimisation de <math>-f</math> (à 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<ref>{{Article |prénom1=M. |nom1=Gori |prénom2=A. |nom2=Tesi |titre=On the problem of local minima in backpropagation |périodique=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=14 |numéro=1 |date=1992 |issn=0162-8828 |doi=10.1109/34.107014 |lire en ligne=http://dx.doi.org/10.1109/34.107014 |consulté le=2019-08-21 |pages=76–86 }}</ref>.

Un [[maximum local]] <math>a</math> est un point de <math>A</math> tel qu'il existe un [[Voisinage (mathématiques)|voisinage]] <math>V</math> où pour tout <math>x\in V</math>, <math>f(x) \leqslant f(a)</math>. 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 <math>A</math> ou de la fonction <math>f</math>, divers théorèmes assurent des propriétés particulières de la solution qui simplifient sa recherche (voir {{page h|principe du maximum}}).

=== Optimisation combinatoire ===
Le plus souvent, <math>A</math> est un [[sous-ensemble]] de l’[[espace euclidien]] <math>\R^n</math>. Lorsque <math>A</math> est un sous-ensemble de  <math>\N^n</math> ou de <math>\N^p\times\R^q</math>, constitué des vecteurs satisfaisant un certain nombre de [[Contrainte (mathématiques)|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.

{{Théorème|Problème d'optimisation généralisé|Étant donné une [[fonction (mathématiques)|fonction]] <math>f : A \rightarrow B</math> définie sur un ensemble <math>A</math> à valeurs dans un ensemble <math>B</math> muni d'une relation d'ordre (≤), trouver un élément <math>x^*</math> de <math>A</math> tel que <math>f(x^*) \leqslant f(x)</math> pour tous les <math>x</math> dans <math>A</math> (pour un problème de minimisation) ou <math>f(x^*) \geqslant f(x)</math> pour tous les <math>x</math> dans <math>A</math> (pour un problème de maximisation).}}

Dans cette définition, <math>B</math> 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 <math>f</math> 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 <math>x^*</math> qui minimise ou maximise la fonction objectif, selon les critères déterminés par la relation d'ordre.


<!--
== Notation ==

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

:<math>\min_{x\in\R} x^2 + 1</math>

On cherche la valeur minimale pour l’expression <math>x^2+1</math>, où <math>x</math> s’étend sur les [[nombre réel|nombres réels]] <math>\R</math>. La valeur minimale dans ce cas est <math>1</math>, {{Quoi|date=mai 2017|s’occasionnant à}} <math>x=0</math>.

:<math>\max_{x\in\R}2x</math>

On cherche la valeur maximale pour l’expression <math>2x</math>, où <math>x</math> 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 ».

:<math>\arg\min_{x\in\left]-\infty,-1\right]}x^2+1</math>.

On cherche la ou les valeurs de <math>x</math> dans l'[[intervalle (mathématiques)|intervalle]] <math>\left]-\infty,-1\right]</math> qui minimise l'expression <math>x^2+1</math> (la valeur minimale véritable de cette expression n'est pas importante). Dans ce cas, la réponse est <math>x=-1</math>.

:<math>\arg\max_{x\in\left[-5,5\right],y \in\R}x\cos(y)</math>.

On cherche la ou les paires <math>(x,y)</math> qui maximisent la valeur de l'expression <math>x\cos(y)</math>, avec la contrainte ajoutée que la valeur absolue de <math>x</math> 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 <math>(5,2k\pi)</math> et <math>(-5,(2k+1)\pi)</math>, où <math>k</math> s'étend sur tous les entiers.
-->

== 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 [[optimisation combinatoire|combinatoire]] (les variables à optimiser sont discrètes dans ce dernier cas), l'[[optimisation différentiable]] ou [[optimisation non lisse|non lisse]] (on qualifie ici la régularité des fonctions définissant le problème), l'[[optimisation linéaire]] ([[Fonction affine|fonctions affines]]), [[Optimisation quadratique|quadratique]] (objectif quadratique et contraintes affines), [[Optimisation SDP|semi-définie positive]] (la variable à optimiser est une matrice dont on requiert la [[matrice semi-définie positive|semi-définie positivité]]), [[Optimisation copositive|copositive]] (la variable à optimiser est une matrice dont on requiert la [[Matrice copositive|copositivité]]), [[Optimisation conique|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 [[Espace affine|sous-espace affine]]), [[Optimisation convexe|convexe]] ([[fonction convexe|fonctions convexes]]), [[optimisation non linéaire|non linéaire]], la [[commande optimale]], l'{{Lien|langue=en|trad=Stochastic programming|fr=optimisation stochastique}} et [[Optimisation robuste|robuste]] (présence d'aléas), l'[[optimisation multiobjectif|optimisation multicritère]] (un compromis entre plusieurs objectifs contradictoires est recherché), l'[[optimisation algébrique]] ([[Fonction polynomiale|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.}}

[[Fichier:Classification des problemes d optimisation selon fonction cout.svg|vignette|centré|upright=3.5|Classification des problèmes selon la fonction-coût.]]

[[Fichier:Classification des problemes d optimisation selon ensemble admissible.svg|vignette|centré|upright=3.5|Classification des problèmes selon l'ensemble admissible (contraintes).]]

[[Fichier:Surface banane trompette.svg|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é (dimension finie)|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 <math>A</math> sont [[Équation linéaire|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 <math>A</math>)
* 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'{{Lien|langue=en|trad=Stochastic programming|fr=optimisation stochastique}} étudie le cas dans lequel certaines des contraintes dépendent de [[variable aléatoire|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 :
** aux avionneurs de trouver les plans de décollage optimaux de leurs engins,
** aux ingénieurs de bassin de répartir la production minière entre leurs différents puits,
** aux producteurs d’électricité de planifier la marche des usines hydroélectriques,
** aux ''{{Langue|en|media planners}}'' de répartir efficacement un budget de publicité entre différents supports.

== Méthodes numériques ==
Une ''technique de résolution d’un problème d’optimisation mathématique'' désigne ici
* la transformation du problème d’origine en un problème équivalent,
* une méthode théorique dont la description permet l’élaboration d’un [[Algorithmique|algorithme]] numériquement applicable.

Le choix d’une technique appropriée dépend de
* la nature de la fonction objectif <math>f</math>, de sa régularité ([[Continuité (mathématiques)|continuité]], [[Dérivable|dérivabilité]]), de propriétés spécifiques ([[Parité d'une fonction|parité]], [[Fonction convexe|convexité]]), de la connaissance de voisinages de ses extrema,
* des contraintes caractérisant l'ensemble <math>A</math> des points admissibles.

=== Simplifications ===
Pour trouver une solution à l’optimisation, le problème d’origine est remplacé par un problème équivalent. Par exemple, il est possible de faire un [[Changement de variable (simplification algébrique)|changement de variables]] permettant de décomposer le problème en sous-problèmes ou la substitution d’inconnues permettant d’en réduire le nombre.

La technique du [[multiplicateur de Lagrange]] permet de s’affranchir de certaines contraintes ; cette méthode revient en effet à introduire des pénalités croissantes à mesure que le point se rapproche des contraintes. Un [[Hugh Everett#Les multiplicateurs d'Everett|algorithme dû à Hugh Everett]] permet de mettre à jour de façon cohérente les valeurs des multiplicateurs à chaque [[itération]] pour garantir la convergence. Celui-ci a également généralisé l'interprétation de ces multiplicateurs pour les appliquer à des fonctions qui ne sont ni continues, ni dérivables. Le ''lambda'' exprime un ''coefficient de pénalité'' (notion de [[coût marginal]] d’une contrainte en [[économie (discipline)|économie]]).

=== Recherche des zéros du gradient ===
De nombreuses méthodes et [[Algorithme de recherche d'un zéro d'une fonction|algorithmes]] permettent de trouver un zéro de la dérivée de <math>f</math> (certains sont spécifiques aux [[fonction réelle d'une variable réelle|fonctions d’une variable]]) ou de son gradient <math> \mathbf{\nabla} f </math>. Elles s’appliquent valablement dans des situations où les contraintes sur <math>A</math> restent peu actives.

Toutes ces méthodes se développent dans le cadre d’un [[Méthode itérative|procédé itératif]].

Ces approches peuvent souffrir de quelques défauts :
* La fonction doit être assez régulière (au moins localement) pour être dérivable (ou encore deux fois dérivable pour accéder à la [[matrice hessienne]] ou une approximation de celle-ci).
* Il n’est pas toujours possible d’exprimer explicitement le gradient de la fonction objectif.
* Des conditions de départ doivent être fixées avant d’amorcer le processus itératif. Le choix initial peut considérablement influencer le résultat (divergence du procédé itératif). Les méthodes à convergence rapide sont en général plus sensibles de ce point de vue.
* Dans certains cas, la vitesse de convergence peut se révéler désastreuse : les itérations successives cheminent laborieusement (stagnation) le long d’une ''vallée étroite'' ([[fonction de Rosenbrock]]).
* Si la solution obtenue est bien un extremum (après vérification qu’il ne s’agisse pas d’un [[Point col|point selle]]), celui-ci peut s’avérer être local.

Cas particulier :
Lorsque <math>f</math> est polynomiale de degré 2 dans ses arguments ([[forme quadratique]] et [[forme linéaire|linéaire]]) et sans contrainte, annuler le gradient revient à résoudre un [[Système d'équations linéaires|système linéaire]] (cf [[:Catégorie:Analyse numérique matricielle]]).

=== Méthodes analytiques directes ===
Dans cette catégorie, la plupart des algorithmes généraux s’appliquent aux situations où les contraintes sur <math>A</math> restent peu actives. Ils se basent sur quelques idées dominantes :
* Déplacements le long d’une ligne portée par un gradient.
* Approximation de <math>f</math> par une fonction plus simple (par exemple le [[Théorème de Taylor|développement de Taylor]] d’ordre 2), mise à jour au cours des itérations.
Divers perfectionnements ont été apportés afin d’éviter :
* les stagnations (par exemple {{Lien|langue=en|trad=Nonlinear conjugate gradient method|fr=méthode du gradient conjugué en optimisation non linéaire}})
* le calcul explicite ou trop fréquent de la matrice hessienne (par exemple [[BFGS]])

Les mêmes défauts que ceux mentionnés dans la catégorie précédente peuvent aussi se présenter ici.

La [[:Catégorie:Algorithme d'optimisation]] présente une liste et donne accès à ces méthodes.

=== Techniques de l’optimisation combinatoire ===
Les techniques de l’[[optimisation combinatoire]] concernent des problèmes où une partie (au moins) des variables de l’ensemble <math>A</math> prennent des valeurs [[structure discrète|discrètes]]. On les rencontre dans le cadre de
* la [[théorie des graphes]] ([[Problèmes de cheminement|chemin optimal]] dont le [[problème du voyageur de commerce]])
* la [[théorie des jeux]] ([[stratégie]]s performantes)
* la [[théorie du contrôle]], de la [[régulation]] et de l’[[automatique]] (cf [[:Catégorie:Automatique]])
* l’[[optimisation multidisciplinaire]]

=== Heuristiques et métaheuristiques ===
Pour résoudre des problèmes difficiles (par exemple ceux qui présentent de nombreux extrema locaux pauvres), des techniques ont été conçues pour déterminer des points qui ne sont pas rigoureusement optimaux, mais qui s’en approchent. Ces méthodes, appelées [[Heuristique (mathématiques)|heuristiques]] et [[métaheuristique]]s, se basent généralement sur des phénomènes physiques, biologiques, socio-psychologiques ou font appel au hasard. Les domaines d’application sont vastes et s’étendent souvent bien au-delà des problèmes pour lesquels elles ont été initialement conçues.
* le [[recuit simulé]]
* la [[méthode de Nelder-Mead]] avec recuit simulé
* les [[algorithme de colonies de fourmis|algorithmes de colonies de fourmis]]
* les [[algorithme génétique|algorithmes génétiques]]
* les [[algorithme évolutionniste|algorithmes évolutionnistes]]
* les méthodes d’[[optimisation par essaims particulaires]]

La [[:Catégorie:Métaheuristique]] présente une liste et donne accès à ces méthodes.

=== Techniques de l’optimisation multiobjectif ===
Les problèmes d’[[optimisation multiobjectif]] sortent du cadre strict de la définition donnée plus haut : à un point admissible, la fonction objectif n’associe pas une valeur numérique, mais un point d’un ensemble qui sera le plus souvent associé à un vecteur. L'objectif est alors d'optimiser simultanément l'ensemble des composantes de ce vecteur. On peut aussi voir l’[[optimisation multiobjectif]] comme un ensemble de problèmes d'optimisation dépendant des mêmes paramètres, ayant des objectifs éventuellement contradictoires, et que l'on cherche à résoudre au mieux.

En général, l'espace dans lequel est exprimé le vecteur solution est muni d’un [[Relation d'ordre|ordre partiel]] faisant intervenir des ''critères de dominance'' (par exemple en rapport avec la [[Optimum de Pareto|frontière de Pareto]]). La résolution consiste à trouver un point admissible dont l’objectif n’est ''dominé'' par aucun autre.

== Domaines d’application ==
Ils sont extrêmement variés : optimisation d’un [[Problème du voyageur de commerce|trajet]], de la [[Conception assistée par ordinateur|forme d’un objet]], d’un [[prix|prix de vente]], d’une [[réaction chimique]], du [[contrôle aérien]], du [[rendement]] d’un appareil, du fonctionnement d'un [[moteur]], de la gestion des lignes ferroviaires, du choix des investissements économiques, de la [[Construction navale|construction d’un navire]], etc. L’optimisation de ces systèmes permet de trouver une configuration idéale, d’obtenir un gain d’effort, de temps, d’argent, d’énergie, de matière première, ou encore de satisfaction.

Les problèmes de la [[dynamique (physique)|dynamique]] des [[modèle du solide indéformable|solides indéformables]] (surtout la dynamique des corps rigides articulés) ont souvent besoin de techniques d'optimisation mathématique, puisqu'on peut voir la dynamique des corps rigides comme résolution d'une [[équation différentielle ordinaire]] sur une variété contrainte ; les contraintes sont diverses contraintes géométriques non linéaires telles que « ces deux points doivent toujours coïncider », ou « ce point doit toujours être sur cette courbe ». Aussi, le problème de calculer les forces de contact peut être achevé en résolvant un problème de [[complémentarité linéaire]], qui peut aussi être vu comme un problème d'optimisation quadratique.

Plusieurs problèmes de conception peuvent aussi être exprimés sous forme de problèmes d’optimisation. Cette application est appelée l’optimisation de forme. Un sous-ensemble récent et croissant de ce domaine s’appelle l’[[Optimisation multidisciplinaire]] qui, bien qu’utile en plusieurs problèmes, a été particulièrement appliquée aux problèmes d'[[ingénierie et technologie spatiale]].

Un autre domaine qui utilise les techniques d’optimisation est la [[recherche opérationnelle]].

L’optimisation est un des outils centraux de la [[microéconomie]] qui est basée sur le principe de la [[rationalité]] et de l’optimisation des comportements, le [[profit]] pour les [[entreprise]]s, et l’[[Utilité (économie)|utilité]] pour les [[consommateur]]s.

En [[mécanique (science)|mécanique]] on distingue trois formes d'optimisation<ref>{{Lien web|url=https://www.unit.eu/Members/cvayssade/learningfolder/learningfolder.2004-11-20.9956165298/optimtopol/attachment_download/file|titre=Optimisation mécanique, Optimisation topologique|auteur=Catherine Vayssade|année=2004|consulté le=24 décembre 2008}}.</ref> :
* l'optimisation de taille ou [[optimisation paramétrique]], qui consiste à optimiser des dimensions (longueur, épaisseur, diamètre…) de la structure mécanique ;
* l'[[optimisation de forme]], qui consiste à optimiser l'enveloppe d'une pièce sans changer la [[topologie]], c'est-à-dire sans ajouter de trous dans la pièce ;
* l'[[optimisation topologique]], qui consiste à faire varier la répartition de matière au sein d'un volume de départ donné.


Très loin de constituer une liste exhaustive, ces quelques exemples attestent de la variété des formulations et préfigure la diversité des outils mathématiques susceptibles de résoudre ces problèmes.

== Notes et références ==
{{Traduction/Référence|en|Optimization (mathematics)|5552960|type=n}}
{{Références}}

== Voir aussi ==

=== Articles connexes ===
{{Colonnes|nombre=3|
* [[Active set]]
* [[Ajustement de courbe]]
* [[Analyse numérique]]
* [[Complémentarité]]
* [[Conditions d'optimalité (dimension finie)]]
* [[Fonction objectif]]
* [[Inéquation variationnelle]]
* [[Liste des algorithmes]]
* [[Logique floue]]
* [[Métaheuristique]]
* [[Multiplicateur de Lagrange]]
* [[Optimisation aléatoire]]
* [[Optimisation convexe]]
* [[Optimisation de code]] ([[compilateur]]s et [[langages de programmation]])
* [[Optimisation linéaire]]
* [[Optimisation non linéaire]]
* [[Optimisation quadratique]]
* [[Recherche opérationnelle]]
* [[Relaxation dynamique]]
* [[Théorie des jeux]]
}}

=== Ouvrages généraux ===
* {{en}} J. F. Bonnans, J. Ch. Gilbert, [[Claude Lemaréchal|C. Lemaréchal]] et C. Sagastizábal, ''Numerical Optimization - Theoretical and Numerical Aspects'' {{détail des éditions|Référence:Optimisation (Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006)}}
* {{en}} J. F. Bonnans et A. Shapiro, ''Perturbation analysis of optimization problems'', Springer, 2000 {{ISBN|978-0-387-98705-7}}
* {{en}} Christodoulos A. Floudas et Panos M. Pardalos (éditeurs), ''[https://www.springer.com/math/book/978-0-387-74758-3 Encyclopedia of Optimization]'', {{2e|édition}}, 2009 {{ISBN|978-0-387-74758-3}}
* Michel Minoux, ''Programmation mathématique - théorie et algorithmes'', [[éditions Dunod]], 1983 {{ISBN|2040154876}}

=== Liens externes ===
* {{lien web
 | url = http://educmath.ens-lyon.fr/applet/exprime/sylari.pdf
 | titre = La rivière
 | site = ÉducMath
 | format = pdf
}} : problème du plus court chemin entre deux maisons passant par la rivière
* {{en}} [http://archive.wikiwix.com/cache/?url=http%3A%2F%2Fwww-fp.mcs.anl.gov%2Fotc%2FGuide%2Findex.html Guide NEOS]
* {{Lien web|lang=en|url=http://glossary.computing.society.informs.org/second.php|titre=Mathematical programming glossary}}
{{Palette|optimisation}}
{{portail|mathématiques}}

[[Catégorie:Optimisation| ]]
[[Catégorie:Branche des mathématiques]]