Accueil |

Optimisation (mathématiques)

En mathématiques, on nomme optimisation l'étude des problèmes qui sont de la forme :
Étant donné: une fonction f : A -> R d'un ensemble A aux nombre réels
Recherché: un élément x0 en A tel que f(x0) ≥ f(x) pour tous les x en A ("maximisation") ou tel que f(x0) ≤ f(x) pour tous les x en A ("minimisation").

Une telle formulation est parfois appelée programme mathématique (terme non directement lié à  la programmation informatique, mais usité par exemple pour la programmation linéaire - voir l'historique ci-dessous). Plusieurs problèmes théoriques et pratiques peuvent être étudiés dans cet encadrement général.

Typiquement, A est un sous-ensemble donné de l'espace euclidien Rn, souvent spécifié par un ensemble de contraintes, des égalités ou des inégalités que les membres de A doivent satisfaire. Les éléments de A sont appelées les solutions possibles et la fonction f est appelée la fonction objective. Une solution possible qui maximise (ou minimise, si c'est le but) la fonction objective est appelée une fonction optimale .

En général il y aura plusieurs maximums ou minimums locaux, o๠un minimum local x * est défini comme un point tel que pour un δ > 0 donné et tous les x tel que ||x - x* || ≤ δ la formule f(x) ≥ f(x*) tient bon ; c'est-à -dire sur une balle autour de x* toutes les valeurs des fonctions sont plus grandes qu'aux valeurs que la valeur en ce point. Les maximums locaux sont définis semblablement. En général, il est facile de trouver les maximums locaux, cependant des connaissances additionnelles sur le problème (par exemple la fonction étant convexe) sont nécessaires pour vérifier que la solution trouvée est un minimum global. Il n'existe pas de méthode connue assurant quel que soit le type de fonction que l'on trouvera un extremum global.

Sommaire
1 Notation
2 Techniques
3 Utilisations
4 Historique
5 Voir aussi
6 Liens externes

Notation

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

On cherche la valeur minimale pour l'expression x2+1, o๠x s'étend sur les nombres réels R. La valeur minimale dans ce cas est 1, s'occasionnant à  x=0.

On cherche la valeur maximale pour l'expression 2x, o๠s'étend sur les réels. Dans ce cas, il n'y a pas de tel maximum puisque l'expression n'est pas limitée, donc la réponse est "l'infinité" ou "indéfini".

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

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

Techniques

Les techniques pour résoudre les problèmes mathématiques dépendent de la nature de la fonction objective de l'ensemble contraint. Les sous-domaines majeurs suivants existent :

Pour les fonctions dérivables deux fois, des problèmes sans contraintes peuvent être résous en trouvant les lieux o๠le gradient de la fonction est 0 (par exemple les points stationnaires) et en utilisant la matrice hessienne pour classifier le type de point. Si le hessien est défini positif, le point est un minimum local ; s'il est un défini négatif, un maximum local et s'il est indéfini c'est un genre de col.

Devrait-ce qu'une fonction soit convexe sur une région d'intérêt (tel que défini par les contraintes) alors quelque minimum local sera aussi un minimum global. Des techniques numériques robustes et rapides pour optimiser des fonctions convexes doublement dérivables. En dehors de ces fonctions, des techniques moins idéales doivent être employées.

Les problèmes à  contraintes peuvent souvent être transformés en des problèmes sans contraintes à  l'aide du multiplicateur de Lagrange.

De nombreuses techniques existent pour trouver un bon minimum local dans les problèmes d'optimisation nonlinéaires avec plusieurs minimums locaux pauvres:

Utilisations

De plus, les problèmes de la dynamique à  corps rigides (surtout la dynamique des corps rigides articulée) ont souvent besoin de techniques de programmation mathématique, puisque vous pouvez voir la dynamique des corps rigides comme tentant de résoudre une équation différentielle ordinaire sur une variété contrainte; les contraintes sont diverses contraintes géométriques nonliné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 PQ (problème de programmation quadratique).

Plusieurs problèmes de dessin peuvent aussi être exprimés sous forme de programmes d'optimisation. Cette application est appelée l'optimisation de dessin. Un sous-ensemble récent et croissant de ce domaine s'appelle l'optimisation du dessin multidisciplinaire qui, bien qu'utile en plusieurs problèmes, a été particulièrement appliqué aux problèmes du génie aérospatial.

Un autre domaine qui utilise les techniques de l'optimisation est la recherche opérationnelle.

Historique

Historiquement, le premier terme à  être introduit fut la programmation linéaire, lequel fut inventé par George Dantzig dans les années 1940. Le terme programmation dans ce contexte ne réfère pas à  la programmation informatique (bien que les ordinateurs sont largement utiisés de nos jours pour résoudre des programmes mathématiques). Au lieu, le terme vient de l'usage programme par les forces armées américaines pour faire référence à  des horaires proposés de formation et de logistique, qui étaient les programmes que Dantzig étudiaient à  l'époque. (De plus, par après, l'aemploi du terme "programmation" était apparemment important pour le financement gouvernemental, car il était associé avec des lieux de recherche de la haute technologie qui étaient considérés importants.)

Voir aussi

Liens externes