Programmation non-linéaire

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

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 ses l'ensemble de ses paramètres peuvent être non-linéaires.

Sommaire

1 Formulation mathématique
2 Méthodes de résolution
3 Exemples
- 3.1 En dimension 2
- 3.2 En dimension 3
4 Voir aussi

[modifier] Formulation mathématique

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

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

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

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

[modifier] 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.

[modifier] Exemples

[modifier] En dimension 2

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

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

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

où l'on cherche à maximiser la fonction

f(x) = x₁ + x₂

avec x = (x₁, x₂)

[modifier] 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 :

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

où l'on cherche à maximiser la fonction :

f(x) = x₁x₂ + x₂x₃

avec x = (x₁, x₂, x₃)

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Références

(en) Cet article est partiellement ou en totalité issu d’une traduction de l’article en anglais : « 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: 2^nd Edition. Athena Scientific. ISBN 1-886529-00-0.

[modifier] Liens externes

[modifier] Documentation

(en) Nonlinear programming FAQ
(en) Mathematical Programming Glossary
(en) Nonlinear Programming Survey OR/MS Today

[modifier] Implémentations

(en) AIMMS Optimization Modeling AIMMS — include nonlinear programming in industry solutions ;
(en) AMPL solver software ;
(en) GAMS General Algebraic Modeling System.

Portail de l'informatique – Accédez aux articles de Wikipédia concernant l’informatique.

Récupérée de « http://fr.wikipedia.org../../../p/r/o/Programmation_non-lin%C3%A9aire.html »

Catégories : Wikipédia:ébauche informatique • Algorithme d'optimisation • Intelligence artificielle • Recherche opérationnelle