Optimisation (mathématiques)

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).

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).

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.

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.

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.

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[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.

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 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/… »

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 ${\displaystyle f}$ sur l'ensemble ${\displaystyle A}$.

La fonction ${\displaystyle f}$ porte divers noms : fonction-coût ou simplement coût, fonction-objectif ou simplement objectif, critère, etc.

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é).

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}}\}}$.

On peut écrire ce problème de différentes manières :

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

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é.

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}$.

Le problème décrit ci-dessus est un problème de minimisation. Comme on a

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.

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].

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.

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 ).

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.

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, ${\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.

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.

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).

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.

Toutes ces méthodes se développent dans le cadre d’un 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 selle), celui-ci peut s’avérer être local.

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).

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 :

• Déplacements le long d’une ligne portée par un gradient.
• 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.

Divers perfectionnements ont été apportés afin d’éviter :

• les stagnations (par exemple méthode du gradient conjugué en optimisation non linéaire (en))
• 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.

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

• la théorie des graphes (chemin optimal dont le problème du voyageur de commerce)
• la théorie des jeux (stratégies performantes)
• la théorie du contrôle, de la régulation et de l’automatique (cf Catégorie:Automatique)
• l’optimisation multidisciplinaire

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.

• le recuit simulé
• la méthode de Nelder-Mead avec recuit simulé
• les algorithmes de colonies de fourmis
• les algorithmes génétiques
• les 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.

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 ordre partiel faisant intervenir des critères de dominance (par exemple en rapport avec la frontière de Pareto). La résolution consiste à trouver un point admissible dont l’objectif n’est dominé par aucun autre.

• (en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal et C. Sagastizábal, Numerical Optimization - Theoretical and Numerical Aspects [détail des éditions]
• (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), Encyclopedia of Optimization, 2^e édition, 2009 (ISBN 978-0-387-74758-3)
• Michel Minoux, Programmation mathématique - théorie et algorithmes, éditions Dunod, 1983 (ISBN 2040154876)

• « La rivière » [PDF], sur ÉducMath : problème du plus court chemin entre deux maisons passant par la rivière
• (en) Guide NEOS
• (en) « Mathematical programming glossary »