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").
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 |
|
2 Techniques 3 Utilisations 4 Historique 5 Voir aussi 6 Liens externes |
Les problèmes d'optimisation sont souvent exprimés avec une notation spéciale.
Voici quelques exemples:
Notation
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.
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 :
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:
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.
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.)
Techniques
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.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).Historique
Voir aussi
Liens externes
