Optimisation non linéaire

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.