Programmation non-linéaire

Programmation non-linéaire

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 « contraintes » - sous la forme d'une fonction à maximiser ou à minimiser. Cette fonction ou l'ensemble de ses paramètres peuvent être non-linéaires.

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)

Voir aussi

Articles connexes

Références

  • (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Nonlinear programming ».
  • Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • Bazaraa, Mokhtar et Shetty (1979), Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
  • Nocedal, Jorge et Wright, Stephen (1999), Numerical Optimization. Springer. ISBN 0-387-98793-2.
  • Bertsekas, Dimitri (1999), Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.

Liens externes

Documentation

Implémentations

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Programmation non-lin%C3%A9aire ».

Wikimedia Foundation. 2010.

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

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

Regardez d'autres dictionnaires:

  • 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 — 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 linéaire — netiesinis programavimas statusas T sritis automatika atitikmenys: angl. nonlinear programming vok. nichtlineare Programmierung, f rus. нелинейное программирование, n pranc. programmation non linéaire, f …   Automatikos terminų žodynas

  • Programmation mathématique — 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

  • Programmation linéaire en nombres 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

  • linéaire — [ lineɛr ] adj. et n. m. • XVe; lat. linearis, de linea → ligne 1 ♦ Qui a rapport aux lignes, se traduit par des lignes. Mesure linéaire : mesure de longueur. Dessin linéaire, où le trait seul est utilisé (cf. Au trait). Perspective linéaire… …   Encyclopédie Universelle

  • PROGRAMMATION MATHÉMATIQUE — La programmation mathématique consiste à chercher, parmi tous les points x vérifiant certaines conditions du type: celui ou ceux qui rendent minimal (ou maximal, suivant le cas) un certain critère f (x ), qui sera interprété comme un gain dans le …   Encyclopédie Universelle

Share the article and excerpts

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