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, 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.

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.

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

${\displaystyle 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 :

${\displaystyle x\in X;\,f(x)=\max _{y\in X}f(y)}$.

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 :

• la méthode de Newton,
• la méthode de quasi-Newton,
• la méthode du gradient conjugué,
• la recherche linéaire,
• les régions de confiance,
• la méthode de Nelder-Mead,
• …

Si les contraintes s'expriment sous la forme d'inégalités

${\displaystyle h_{1}(x)\geq 0,\ h_{n}(x)\geq 0}$

on peut utiliser la méthode de la « barrière logarithmique »^[1]. Si ƒ est la fonction à minimiser, alors on définit la fonction

${\displaystyle B(x)=f(x)-\mu \ln(h)}$

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.

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₁ + x₂

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₂ + x₂x₃

• Conditions d'optimalité (dimension finie)
• Méthode des moindres carrés
• Optimisation

• (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: 2^d 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).

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

• (en) AIMMS Optimization Modeling AIMMS — include nonlinear programming in industry solutions ;
• (en) AMPL solver software ;
• (en) Artelys Knitro - solveur spécialisé dans la résolution de problèmes d'optimisation non linéaire de grande dimension (version d'essai disponible);
• (en) GAMS General Algebraic Modeling System.

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l'informatique théorique
• Portail des mathématiques