Résolution analytique
Conditions d'existence d'un extremum
Un problème d'optimisation sans contrainte s'écrit sous forme générale : \(Min\) \(f(x)\)
\(x^*\) sera dit minimum global de \(f(x)\) si \(\forall x \in \mathbb{R^n}, f(x^*) < f(x)\)
\(x^*\) sera dit minimum local de \(f(x)\) si \(\forall x \in V(x^*), f(x^*) < f(x)\), où \(V(x^*)\) désigne un voisinage autour de \(x^*\).
Dans le cas où la fonction \(f\) est continûment différentiable (deux fois) autour de la solution, notée \(x^*\), alors le gradient de \(f\) en \(x^*\) est nul : \(\nabla f(x^*)=0\)
Cette condition est appelée condition du premier ordre. Cependant, cette condition du premier ordre est vérifiée pour tout les extrema, c'est à dire tous les maxima et minima. En fait, cette condition du premier ordre est également vérifiée pour les les points d'inflexion ou points-selles ! Tous les points vérifiant cette condition sont appelés points stationnaires ou critiques. C'est la raison pour laquelle on dit que la condition du premier ordre est une condition nécessaire d'existence d'un minimum (local) mais qu'elle n'est pas suffisante. On peut le vérifier aisément avec des exemples comme \(f(x)=x^3\) ou pour \(f(x_1,x_2)=x_1^2-x_2^2\).
Si \(x^*\) est un point critique de \(f\) et si \(H(x)\) désigne la matrice Hessienne alors on montre que \(H(x^*)\) est définie positive dans le cas où \(x^*\) est un minimum. La condition sur la matrice Hessienne est appelée condition du second ordre. La condition du second ordre est une condition suffisante d'existence d'un extremum local. De même, si \(x^*\) est un point critique de \(f\) et si \(H(x^*)\) est définie négative alors \(x^*\) est un maximum.
Résolution analytique en pratique
La résolution analytique d'un problème d'optimisation sans contrainte est principalement basée sur la condition du premier ordre.
Pour une fonction objectif à une seule variable de décision, il va falloir trouver l'ensemble des zéros de la fonction dérivée première, puis chercher le minimum global parmi ces zéros. Pour cela, on sélectionne l'ensemble des minima, ce sont les valeurs de \(x^*\) pour lesquelles la dérivée seconde est positive ; le minimum global est déterminé comme celui parmi les minima qui donne la valeur de f la plus petite.
Pour une fonction objectif à plusieurs variables de décision, il va falloir expliciter l'ensemble des composantes du vecteur gradient et résoudre le système d'équations algébriques correspondant à ce que chaque composante soit nulle pour déterminer l'ensemble des points critiques. Puis vérifier pour quels points critiques, la matrice hessienne est définie positive. Ceci devient vite laborieux, c'est une raison pour laquelle des méthodes numériques ont été développées.
Remarque : Méthode graphique
Si la fonction objectif ne dépend que d'une ou de deux variables de contrôle et si sa formulation mathématique est explicite alors tracer graphiquement la fonction objectif est un bon moyen pour identifier le nombre d'extrema et avoir une idée assez précise des valeurs de \(x^*\).
Remarque : Résolution numérique pour trouver les zéros d'une fonction
Même dans le cadre d'une résolution analytique d'un problème d'optimisation, il peut être nécessaire de passer par une étape numérique. C'est le cas par exemple, où il n'est pas possible de trouver analytiquement le zéro de la dérivée de la fonction objectif (cas d'une fonction à plusieurs variables de contrôle) ou de résoudre analytiquement le système d'équations correspondant au gradient nul de la fonction objectif (cas d'une fonction à plusieurs variables de contrôle).
L'algorithme de Newton-Raphson permet de trouver le zéro d'une fonction à une variable. C'est une méthode itérative. Nous rappelons juste ici sa formule itérative dans le cas de la recherche du zéro de la fonction \(g(x)\) pour passer de la valeur de \(x\) à l'itération \(k\) à sa valeur à l'itération \(k+1\) :
\(x_{k+1}=x_k - \frac{g(x_k)}{g'(x_k)}\).
Appliquée à un problème d'optimisation, \(g(x)\) représenterait donc la dérivée de la fonction objectif. Cet algorithme est très efficace s'il est initialisé dans un voisinage assez proche de la solution. La convergence est alors de type quadratique près de la solution ; ce qui signifie que le nombre de décimales correctes doublent à chaque itération. Par contre la convergence de la méthode ne se fait pas obligatoirement vers l'extremum global et elle peut aussi bien converger vers un minimum ou un maximum.