Optimisation (mathematiques)

Optimisation (mathematiques)

Optimisation (mathématiques)

En mathématiques, l'optimisation est l’étude des problèmes qui sont de la forme :

Étant donné : une fonction f : A \rightarrow \mathbb R d’un ensemble A dans l'ensemble des nombre réels
Rechercher : un élément x0 de A tel que f(x_0) \ge f(x) pour tous les x en A (« maximisation ») ou tel que f(x_0) \le 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 utilisé 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.

Étant donné que la maximisation de f est équivalente à la minimisation de − f, une méthode pour trouver le minimum (ou le maximum) suffit à résoudre le problème d'optimisation.

Il arrive fréquemment que A soit un sous-ensemble donné de l’espace euclidien \mathbb R^n, souvent spécifié par un ensemble de contraintes, des égalités ou des inégalités que les éléments de A doivent satisfaire. Les éléments de A sont appelées les solutions admissibles et la fonction f est appelée la fonction objectif. Une solution possible qui maximise (ou minimise, si c’est le but) la fonction objectif est appelée une solution optimale. Dans le cas particulier où A est un sous-ensemble de \mathbb N^n ou de \mathbb N^p\times \mathbb R^q, on parle d'optimisation combinatoire.

Un minimum local x * est défini comme un point tel qu'il existe un voisinage V de x * tel que pour tout x\in V, f(x) \ge f(x^*) ; c’est-à-dire que dans une voisinage de x * toutes les valeurs de la fonction sont plus grandes que la valeur en ce point. Lorsque A est un sous-ensemble de \mathbb R^n, ou plus généralement un espace vectoriel normé, cela s'écrit : pour un δ > 0 donné et tous les x tels que ||x - x^*|| \le \delta on a f(x) \ge f(x^*). Les maximums locaux sont définis semblablement. En général, il est facile de trouver les minimums (maximums) locaux, qui sont parfois nombreux. Pour vérifier que la solution trouvée est un minimum (maximum) global, il est nécessaire de recourir à des connaissances additionnelles sur le problème (par exemple la convexité de la fonction objectif).

Sommaire

Notation

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

\min_{x \in \mathbb{R}} x^2 + 1

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

\max_{x \in \mathbb{R}} 2x

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

\arg \min_{x \in ]-\infty, -1]} x^2 + 1

On cherche la ou les valeurs de x dans l'intervalle ]-\infty, -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.

\arg \max_{x \in [-5, 5], y \in \mathbb{R}} x \cos(y)

On cherche la ou les paires (x,y) qui maximisent la valeur de l'expression xcos(y), avec la contrainte ajoutée que la valeur absolue de x 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 (5,2kπ) 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 objectif de l'ensemble contraint. Les sous-domaines majeurs suivants existent :

  • la programmation linéaire étudie les cas où la frontière de l’ensemble A et la fonction objectif 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.
  • la programmation linéaire en nombres entiers étudie les programmes linéaires dans lesquels certaines ou toutes les variables sont contraintes à prendre des valeurs entières. Ces problèmes peuvent être résolus par différentes méthodes: séparation et évaluation, plans sécants.
  • la programmation quadratique permet à la fonction objectif d’avoir des termes quadratiques, tout en conservant une description de l’ensemble A à partir d'égalités/inégalités linéaires
  • la programmation 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
  • la programmation stochastique étudie le cas dans lequel certaines des contraintes dépendent de variables aléatoires
  • la programmation dynamique utilise la propriété qu’une solution optimale 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 n’est utilisable que lorsque la fonction objectif est monotone croissante. 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 media planners de répartir efficacement un budget de publicité entre différents supports

Pour les fonctions dérivables deux fois, des problèmes sans contraintes peuvent être résolus en trouvant les lieux où le gradient de la fonction est 0 (par exemple les points stationnaires) et en utilisant la matrice hessienne pour classer 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 « point-col ».

Si la fonction est convexe sur l’ensemble des solutions admissibles (définies par les contraintes) alors tout minimum local est aussi un minimum global. Des techniques numériques robustes et rapides existent pour optimiser des fonctions convexes doublement dérivables. En dehors de ces fonctions, des techniques moins efficaces 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 : cette méthode revient en effet à introduire des pénalités croissantes à mesure qu’on 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 devient alors juste un coefficient de pénalité.

De nombreuses techniques existent pour trouver un bon minimum local dans les problèmes d’optimisation non-linéaires avec plusieurs minimums locaux pauvres, elles sont généralement considérées comme des métaheuristiques.

Utilisations

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, 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 PPQ (problème de programmation quadratique).

Plusieurs problèmes de conception peuvent aussi être exprimés sous forme de programmes 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é aux problèmes du génie aérospatial.

Un autre domaine qui utilise les techniques de l’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 entreprises, et l’utilité pour les consommateurs.

En mécanique on distingue trois formes d'optimisation[1] :

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

Historique

Historiquement, le premier terme introduit fut celui de programmation linéaire, 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 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.

Notes et références

  1. ↑ Catherine Vayssade, « Optimisation mécanique, Optimisation topologique », 2004. Consulté le 24 décembre 2008

Voir aussi

Articles connexes

Bibliographie

  • (fr) Michel Minoux, Programmation mathématique - théorie et algorithmes, éditions Dunod, 1983 (ISBN 2040154876)
  • (en) Encyclopedia of Optimization, Floudas, Christodoulos A.; Pardalos, Panos M. (éditeurs), 2e édition, 2009 (ISBN 978-0-387-74758-3)

Liens externes

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Optimisation (math%C3%A9matiques) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Optimisation (mathematiques) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient …   Wikipédia en Français

  • Optimisation topologique — L optimisation topologique consiste à trouver la répartition de matière idéale dans un volume donné soumis à des contraintes. Elle se distingue de l optimisation de forme qui ne fait varier que la frontière de la pièce[1]. Mise en œuvre En… …   Wikipédia en Français

  • Optimisation (informatique) — Optimisation de code En programmation informatique, l optimisation est la pratique qui consiste généralement à réduire le temps d exécution d une fonction, l espace occupé par les données et le programme, ou la consommation d énergie. La règle… …   Wikipédia en Français

  • Optimisation du code — Optimisation de code En programmation informatique, l optimisation est la pratique qui consiste généralement à réduire le temps d exécution d une fonction, l espace occupé par les données et le programme, ou la consommation d énergie. La règle… …   Wikipédia en Français

  • Mathematiques — Mathématiques Les mathématiques constituent un domaine de connaissances abstraites construites à l aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques… …   Wikipédia en Français

  • Optimisation multi-objectif — L optimisation multiobjectif est branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire classique).… …   Wikipédia en Français

  • OPTIMISATION ET CONTRÔLE — L’avènement du calcul différentiel, au XVIIe siècle, a permis de caractériser le minimum d’une fonction f par l’équation f (x ) = 0. On résolvait ainsi d’un coup une foule de problèmes pratiques, tout en soulevant de grandes questions théoriques …   Encyclopédie Universelle

  • MATHÉMATIQUES (DIDACTIQUE DES) — Les problèmes posés par l’enseignement des mathématiques ne sont pas nouveaux. Au début du siècle, Henri Lebesgue était préoccupé par les conditions de l’enseignement et de la formation des professeurs. Des efforts plus récents se sont déployés… …   Encyclopédie Universelle

  • Mathematiques appliquees — Mathématiques appliquées Les mathématiques appliquées sont une branche des mathématiques qui s intéresse à l application du savoir mathématique aux autres domaines. L analyse numérique, les mathématiques de l ingénierie; la programmation linéaire …   Wikipédia en Français

  • Mathématiques Appliquées — Les mathématiques appliquées sont une branche des mathématiques qui s intéresse à l application du savoir mathématique aux autres domaines. L analyse numérique, les mathématiques de l ingénierie; la programmation linéaire, la programmation… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”