Optimisation (mathématiques)

Présentation

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Histoire et dénomination

Antiquité

Les premiers problèmes d'optimisation auraient été formulés par Euclide, au III^e siècle 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^[1] (voir figure).! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Introduction de calcul différentiel

Au XVII^e 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^[2]. 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Durant le XVIII^e siècle, 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Développements, applications et dénomination

Le XIX^e 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Historiquement, le premier terme introduit fut celui de « programmation linéaire », inventé par George Dantzig vers 1947^[3]. 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^{[réf. souhaitée]}.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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 Mathematical Programming Society changé en Mathematical Optimization Society^[4] ; 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/… »! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Définitions

Minimisation

Plus formellement, l'optimisation est l’étude des problèmes qui s'expriment de la manière suivante.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Problème d'optimisation — Étant donné une fonction {\displaystyle f:A\rightarrow \mathbb {R} } définie sur un ensemble {\displaystyle A} à valeurs dans l'ensemble {\displaystyle \mathbb {R} } des nombres réels (éventuellement dans la droite achevée {\displaystyle {\overline {\mathbb {R} }}:=\mathbb {R} \cup \{-\infty ,+\infty \}}), trouver un élément {\displaystyle {\bar {x}}} de {\displaystyle A} tel que {\displaystyle f({\bar {x}})\leqslant f(x)} pour tous les {\displaystyle x} dans {\displaystyle A}.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

On dit que l'on cherche à minimiser la fonction {\displaystyle f} sur l'ensemble {\displaystyle A}.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

La fonction {\displaystyle f} porte divers noms : fonction-coût ou simplement coût, fonction-objectif ou simplement objectif, critère, etc.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

L'ensemble {\displaystyle A} est appelé l'ensemble admissible et les points de {\displaystyle A} 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 {\displaystyle A} 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é).! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Le point {\displaystyle {\bar {x}}} 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 {\displaystyle {\bar {x}}\in A} et {\displaystyle f({\bar {x}})<f(x)} pour tout {\displaystyle x\in A\setminus \{{\bar {x}}\}}.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

On peut écrire ce problème de différentes manières :! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

{\displaystyle \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.}! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×

On note parfois {\displaystyle \operatorname {arg\,min} \,\{f(x)\mid x\in A\}} l'ensemble des solutions du problème.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

L'ensemble {\displaystyle f(A):=\{f(x)\mid x\in A\}} est une partie de {\displaystyle \mathbb {R} } (ou de {\displaystyle {\overline {\mathbb {R} }}} si {\displaystyle f} est valeurs dans {\displaystyle {\overline {\mathbb {R} }}}) et sa borne inférieure (ou infimum) {\displaystyle \inf {f(A)}} est appelée la valeur optimale du problème. Cette valeur optimale est atteinte (c'est-à-dire qu'il existe un {\displaystyle {\bar {x}}\in A} tel que {\displaystyle f({\bar {x}})=\inf \,f(A)}) si, et seulement si, le problème d'optimisation a une solution. Si {\displaystyle \inf {f(A)}>-\infty }, on dit que le problème est borné.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

On dit que le problème {\displaystyle \inf {\{f(x)\mid x\in A\}}} est convexe si {\displaystyle A} est une partie convexe d'un espace vectoriel et si {\displaystyle f} est une fonction convexe sur {\displaystyle A}.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Maximisation

Le problème décrit ci-dessus est un problème de minimisation. Comme on a! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

{\displaystyle \sup _{x\in A}{f(x)}=-\inf _{x\in A}\left(-f(x)\right),}! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×

un problème de maximisation d'une fonction {\displaystyle f} (à gauche ci-dessus) est équivalent au problème de minimisation de {\displaystyle -f} (à 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.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

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^[5].! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Un maximum local {\displaystyle a} est un point de {\displaystyle A} tel qu'il existe un voisinage {\displaystyle V} où pour tout {\displaystyle x\in V}, {\displaystyle f(x)\leqslant f(a)}. Un minimum local est défini semblablement.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

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 {\displaystyle A} ou de la fonction {\displaystyle f}, divers théorèmes assurent des propriétés particulières de la solution qui simplifient sa recherche (voir principe du maximum ).! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Optimisation combinatoire

Le plus souvent, {\displaystyle A} est un sous-ensemble de l’espace euclidien {\displaystyle \mathbb {R} ^{n}}. Lorsque {\displaystyle A} est un sous-ensemble de {\displaystyle \mathbb {N} ^{n}} ou de {\displaystyle \mathbb {N} ^{p}\times \mathbb {R} ^{q}}, constitué des vecteurs satisfaisant un certain nombre de contraintes (de type égalité ou inégalité), on parle d'optimisation combinatoire.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Problème d'optimisation généralisé — Étant donné une fonction {\displaystyle f:A\rightarrow B} définie sur un ensemble {\displaystyle A} à valeurs dans un ensemble {\displaystyle B} muni d'une relation d'ordre (≤), trouver un élément {\displaystyle x^{*}} de {\displaystyle A} tel que {\displaystyle f(x^{*})\leqslant f(x)} pour tous les {\displaystyle x} dans {\displaystyle A} (pour un problème de minimisation) ou {\displaystyle f(x^{*})\geqslant f(x)} pour tous les {\displaystyle x} dans {\displaystyle A} (pour un problème de maximisation).! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Dans cette définition, {\displaystyle B} 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 {\displaystyle f} 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 {\displaystyle x^{*}} qui minimise ou maximise la fonction objectif, selon les critères déterminés par la relation d'ordre.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

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'optimisation stochastique (en) 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), etc.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• L'optimisation linéaire étudie le cas où la fonction objectif et les contraintes caractérisant l’ensemble {\displaystyle A} 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.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×
• 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• L'optimisation quadratique étudie le cas où la fonction objectif est une forme quadratique (avec contraintes linéaires pour {\displaystyle A})! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×
• 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• L'optimisation stochastique (en) é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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• 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 : ! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
  • aux avionneurs de trouver les plans de décollage optimaux de leurs engins,! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×
  • aux ingénieurs de bassin de répartir la production minière entre leurs différents puits,! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×
  • aux producteurs d’électricité de planifier la marche des usines hydroélectriques,! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×
  • aux media planners de répartir efficacement un budget de publicité entre différents supports.! Non vérifiéNon vérifié Ce contenu affiché ne dispose pas encore d’un contrôle factuel correspondant.×

Méthodes numériques

Une technique de résolution d’un problème d’optimisation mathématique désigne ici! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• la transformation du problème d’origine en un problème équivalent,! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• une méthode théorique dont la description permet l’élaboration d’un algorithme numériquement applicable.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Le choix d’une technique appropriée dépend de! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• la nature de la fonction objectif {\displaystyle f}, de sa régularité (continuité, dérivabilité), de propriétés spécifiques (parité, convexité), de la connaissance de voisinages de ses extrema,! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×
• des contraintes caractérisant l'ensemble {\displaystyle A} des points admissibles.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

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 variables permettant de décomposer le problème en sous-problèmes ou la substitution d’inconnues permettant d’en réduire le nombre.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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 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).! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Recherche des zéros du gradient

De nombreuses méthodes et algorithmes permettent de trouver un zéro de la dérivée de {\displaystyle f} (certains sont spécifiques aux fonctions d’une variable) ou de son gradient {\displaystyle \mathbf {\nabla } f}. Elles s’appliquent valablement dans des situations où les contraintes sur {\displaystyle A} restent peu actives.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Toutes ces méthodes se développent dans le cadre d’un procédé itératif.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Ces approches peuvent souffrir de quelques défauts :! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• 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).! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Il n’est pas toujours possible d’exprimer explicitement le gradient de la fonction objectif.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• 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).! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Si la solution obtenue est bien un extremum (après vérification qu’il ne s’agisse pas d’un point selle), celui-ci peut s’avérer être local.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Cas particulier : Lorsque {\displaystyle f} est polynomiale de degré 2 dans ses arguments (forme quadratique et linéaire) et sans contrainte, annuler le gradient revient à résoudre un système linéaire (cf Catégorie:Analyse numérique matricielle).! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Méthodes analytiques directes

Dans cette catégorie, la plupart des algorithmes généraux s’appliquent aux situations où les contraintes sur {\displaystyle A} restent peu actives. Ils se basent sur quelques idées dominantes :! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

• Déplacements le long d’une ligne portée par un gradient.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Approximation de {\displaystyle f} par une fonction plus simple (par exemple le développement de Taylor d’ordre 2), mise à jour au cours des itérations.! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

Divers perfectionnements ont été apportés afin d’éviter :! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• les stagnations (par exemple méthode du gradient conjugué en optimisation non linéaire (en))! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• le calcul explicite ou trop fréquent de la matrice hessienne (par exemple BFGS)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Les mêmes défauts que ceux mentionnés dans la catégorie précédente peuvent aussi se présenter ici.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

La Catégorie:Algorithme d'optimisation présente une liste et donne accès à ces méthodes.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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 {\displaystyle A} prennent des valeurs discrètes. On les rencontre dans le cadre de! À revérifierÀ revérifier Le contrôle conservé ne couvre pas précisément le texte et le contexte actuellement affichés.×

• la théorie des graphes (chemin optimal dont le problème du voyageur de commerce)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• la théorie des jeux (stratégies performantes)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• la théorie du contrôle, de la régulation et de l’automatique (cf Catégorie:Automatique)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• l’optimisation multidisciplinaire! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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 heuristiques et métaheuristiques, 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• le recuit simulé! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• la méthode de Nelder-Mead avec recuit simulé! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• les algorithmes de colonies de fourmis! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• les algorithmes génétiques! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• les algorithmes évolutionnistes! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• les méthodes d’optimisation par essaims particulaires! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

La Catégorie:Métaheuristique présente une liste et donne accès à ces méthodes.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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. Cet espace est muni d'une relation d'ordre souvent partiel.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

La solution d'un problème peut être suivant le contexte l'identification d'un Élément maximal ou de l'ensemble de ces éléments appelée frontière de Pareto.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Par exemple dans un système de navigation chercher a minimiser en même temps la durée et la distance parcourue peut aboutir a un seul trajet optimal des deux points de vue, ou a un ensemble de trajets offrant différent compromis suivant le réseau routier.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Domaines d’application

Ils sont extrêmement variés : optimisation d’un trajet, de la forme d’un objet, d’un 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 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Les problèmes de la dynamique des 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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Un autre domaine qui utilise les techniques d’optimisation est la recherche opérationnelle.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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 entreprises, et l’utilité pour les consommateurs.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Un domaine qui utilise de plus en plus l’optimisation pour la gestion de ses opérations est celui des soins de santé. L’optimisation sert notamment à améliorer l’accès aux soins, la qualité des services offerts ainsi que l’utilisation de ressources limitées. Elle est surtout utilisée au niveau de la planification des horaires du personnel, de l'affectation des salles d’opération et de la prise de rendez-vous. Les problèmes d’optimisation en santé sont particulièrement complexes en raison du grand nombre de contraintes et de l’incertitude associée, par exemple, à l’arrivée des patients ou à la durée des interventions. Ils peuvent être modélisés et résolus à l’aide de la programmation linéaire, de méthodes heuristiques ou encore de l’optimisation stochastique.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

En mécanique on distingue trois formes d'optimisation^[6] :! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• l'optimisation de taille ou optimisation paramétrique, qui consiste à optimiser des dimensions (longueur, épaisseur, diamètre…) de la structure mécanique ;! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• 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 ;! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• l'optimisation topologique, qui consiste à faire varier la répartition de matière au sein d'un volume de départ donné.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

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.! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Optimization (mathematics) » (voir la liste des auteurs).! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Voir aussi

Articles connexes

• Active set! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Ajustement de courbe! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Analyse numérique! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Complémentarité! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Conditions d'optimalité (dimension finie)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Fonction objectif! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Inéquation variationnelle! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Liste des algorithmes! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Logique floue! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Métaheuristique! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Multiplicateur de Lagrange! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation aléatoire! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation convexe! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation de code (compilateurs et langages de programmation)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation linéaire! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation non linéaire! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Optimisation quadratique! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Recherche opérationnelle! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Relaxation dynamique! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Théorie des jeux! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Ouvrages généraux

• (en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal et C. Sagastizábal, Numerical Optimization - Theoretical and Numerical Aspects [détail des éditions]! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• (en) J. F. Bonnans et A. Shapiro, Perturbation analysis of optimization problems, Springer, 2000 (ISBN 978-0-387-98705-7)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• (en) Christodoulos A. Floudas et Panos M. Pardalos (éditeurs), Encyclopedia of Optimization, 2^e édition, 2009 (ISBN 978-0-387-74758-3)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• Michel Minoux, Programmation mathématique - théorie et algorithmes, éditions Dunod, 1983 (ISBN 2040154876)! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

Liens externes

• « La rivière » [PDF], sur ÉducMath : problème du plus court chemin entre deux maisons passant par la rivière! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• (en) Guide NEOS! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×
• (en) « Mathematical programming glossary »! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×

• Portail des mathématiques ! Non vérifiéNon vérifié Ce passage ne dispose pas encore de vérification factuelle exploitable.×