Optimisation non linéaire

Optimisation non linéaire

En optimisation, vue comme branche des mathématiques, l'optimisation non linéaire (en anglais : nonlinear programming – NLP) s'occupe principalement des problèmes d'optimisation dont les données, i.e., les fonctions et ensembles définissant ces problèmes, sont non linéaires (bien sûr), mais sont aussi différentiables autant de fois que nécessaire pour l'établissement des outils théoriques, comme les conditions d'optimalité, ou pour la bonne marche des algorithmes de résolution qui y sont introduits et analysés. Cette sous-discipline de l'optimisation, à la frontière mal définie et dont l'introduction est un peu artificielle, a aussi son existence liée à la communauté de chercheurs qui se sont spécialisés sur ces sujets et au type de résultats qui ont pu être obtenus.

Elle complémente l'optimisation non lisse (ou non différentiable), elle aussi liée à une communauté de chercheurs spécialisés. Ces deux disciplines se rassemblent pour former ce que l'on appelle l'optimisation continue, qui jouxte, quant à elle, d'autres sous-disciplines telles que l'optimisation combinatoire (ou discrète), l'optimisation stochastique, etc.

Sommaire

Formulation mathématique

On a une fonction f: X \to R, avec X \subseteq R^n. L'objectif est de déterminer le vecteur x défini par :

x \in X;\, f(x) = \min_{y \in X}f(y) .

De façon équivalente, on peut rechercher la valeur pour laquelle f est maximale :

x \in X;\, f(x) = \max_{y \in X}f(y) .

Méthodes de résolution

Si la fonction est convexe ou concave, et l'ensemble des contraintes est convexe, alors il existe des méthodes spécialisées, appelées méthodes d'optimisation convexe.

Sinon, il existe plusieurs solutions. Par exemple, utilisant le principe de séparation et évaluation pour diviser et traiter séparément plusieurs paramètres.

L'algorithme peut également être arrêté avant d'aboutir, si on peut prouver qu'aucune solution ultérieure ne sera meilleure à un certain seuil de tolérance près. Les conditions de Karush-Kuhn-Tucker (KKT) garantissent qu'une solution ainsi obtenue est optimale.

Exemples

En dimension 2

L'intersection d'une ligne avec l'ensemble des contraintes représente la solution.

Un problème simple peut être posé ainsi :

x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2

où l'on cherche à maximiser la fonction

f(x) = x1 + x2

avec x = (x1, x2)

En dimension 3

L'intersection de la surface avec l'espace des contraintes au centre représente la solution.

On peut formuler un problème ainsi :

x12x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10

où l'on cherche à maximiser la fonction :

f(x) = x1x2 + x2x3

avec x = (x1, x2, x3)

Quelques thèmes de l'optimisation non linéaire

  • L'étude des conditions d'optimalité.
  • Les algorithmes de résolution tels que : Newton, quasi-Newton, le gradient conjugué, la recherche linéaire, les régions de confiance, etc.

Voir aussi

Articles connexes

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Nonlinear programming » (voir la liste des auteurs)
  • (en) Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • (en) Bazaraa, Mokhtar et Shetty (1979), Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
  • (en) Bertsekas, Dimitri (1999), Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
  • (en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006), Numerical Optimization - Theoretical and Numerical Aspects [détail des éditions]
  • (en) Bonnans, J. F et Shapiro, A. (2000), Perturbation analysis of optimization problems. Springer. ISBN 978-0-387-98705-7.
  • (en) Nocedal, Jorge et Wright, Stephen (1999), Numerical Optimization. Springer. ISBN 0-387-98793-2.

Liens externes

Documentation

Implémentations


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Programmation non linéaire — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   Wikipédia en Français

  • Programmation non-lineaire — Programmation non linéaire En informatique, la programmation non linéaire (ou NLP, de l anglais : nonlinear programming) est une méthode permettant de résoudre de nombreuses équations et inéquations dépendant d un ensemble de paramètres on… …   Wikipédia en Français

  • Programmation non-linéaire — En informatique, la programmation non linéaire (ou NLP, de l anglais : nonlinear programming) est une méthode permettant de résoudre de nombreuses équations et inéquations dépendant d un ensemble de paramètres on parle de… …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

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

  • 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 d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   Wikipédia en Français

  • Programmation lineaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programmation linéaire — En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l… …   Wikipédia en Français

  • Programmation linéaire en nombre entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

Share the article and excerpts

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