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, 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 l'introduction 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.[réf. souhaitée]
On a une fonction , avec . L'objectif est de déterminer le vecteur x défini par :
.
De façon équivalente, on peut rechercher la valeur pour laquelle f est maximale :
.
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.
On utilise des algorithmes de résolution tels que :
Si les contraintes s'expriment sous la forme d'inégalités
on peut utiliser la méthode de la « barrière logarithmique »[1]. Si ƒ est la fonction à minimiser, alors on définit la fonction
ainsi, lorsque x se rapproche de la frontière, la valeur de ln(h) tend vers –∞, ce qui pénalise la zone. On effectue plusieurs recherches en faisant tendre μ vers 0.
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 (x1, x2) = x1 + x2
En dimension 3
L'intersection de la surface avec l'espace des contraintes au centre représente la solution.
(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. (ISBN978-0-387-98705-7).