Optimisation numérique

Le problème d'optimisation avec contraintes (NLP) s'écrit :

\(Min~~~ f(x_1,x_2,...,x_n)\)

\(h_k(x_1,x_2)=0~~~~~~ k=1,2,... K\)

\(g_j(x_1,x_2)≤0~~~~~~ j=1,2,... J\)

\(x_i^l≤x_i≤x_i^u~~~~~~ i=1,2,... N\)

Le problème est transformé en un problème sans contrainte grâce à l'introduction d'une fonction de pénalisation :

\(Min~~~ f(x_1,x_2,...,x_n)+P(x_1,x_2,...,x_n,r_E,r_I)\)

\(x_i^l≤x_i≤x_i^u~~~~~~ i=1,2,... N\)

La fonction de pénalisation P s'écrit :

\(P(x_1,x_2,...,x_n,r_E,r_I) = r_E \sum_{k=1}^K h_k(x_1,x_2,...,x_n)^2 + r_I \sum_{j=1}^J \max(0,g_j(x_1,x_2,...,x_n)^2\)

La fonction prend en compte les contraintes égalité en élevant leur valeur au carré et en les multipliant par un coefficient \(r_E\) ; le même traitement est réservé aux contraintes inégalité par l'intermédiaire de \(r_I\). Les contraintes non satisfaites sont donc prises en compte par l'intermédiaire de la fonction de pénalisation. Le réel inconvénient reste le choix à chaque itération des coefficients rE et rI, la convergence vers la solution étant très sensible à ces deux coefficients.

En pratique, la fonction de pénalisation choisie est calculée différemment ; la méthode de type fonction de pénalisation la plus connue est la méthode du Multiplicateur de Lagrange Augmenté. Le problème s'écrit alors :

\(Min~~~ f(x_1,x_2,...,x_n)+P(x_1,x_2,...,x_n,r_h,r_g,\alpha,\beta)\)

\(x_i^l≤x_i≤x_i^u~~~~~~ i=1,2,... N\)

avec

\(P(x_1,x_2,...,x_n,r_h,r_g,\alpha,\beta) = r_h \sum_{k=1}^K h_k(x_1,x_2,...,x_n)^2 + r_g \sum_{j=1}^J \max(\frac{\beta_j}{2r_I},g_j(x_1,x_2,...,x_n)^2+\sum_{k=1}^K \lambda_k h_k(x_1,x_2,...,x_n)^2+\sum_{j=1}^J \beta_j \max(\frac{\beta_j}{2r_I},g_j(x_1,x_2,...,x_n))\)

Il est nécessaire de définir des heuristiques pour ajuster les valeurs de \(r_h,r_g,\alpha,\beta\) à chaque itération. A l'usage, la méthode du Multiplicateur de Lagrange Augmenté présente un certain nombre d'avantages numériques qui lui permettent d'avoir une certaine robustesse ; on citera en particulier que la méthode n'est pas sensible au choix initial des multiplicateurs.

Ces méthodes sont basées sur la linéarisation des différentes fonctions intervenant dans le problème d'optimisation. La linéarisation est réalisée via un développement en série de Taylor de la fonction.

Dans les méthodes dites de programmation linéaire séquentielle, toutes les fonctions, c'est à dire la fonction objectif et les contraintes égalité et inégalité, sont développées au premier ordre. Le problème d'optimisation non-linéaire est alors transformé en un problème linéaire ; un algorithme de résolution des problèmes linéaires avec contraintes peut être employé (méthode du simplexe, cf. cours de recherche opérationnelle). En pratique, cet algorithme calculera une direction de recherche, puis une longueur de déplacement suivant cette direction sera choisie pour satisfaire au mieux les contraintes.

Toutefois, une des méthodes les plus reconnues est la programmation quadratique séquentielle (SQP), dans laquelle la fonction objectif est développée au second ordre du développement en série de Taylor alors que les fonctions définissant les contraintes restent développées au premier ordre.

Le problème d'optimisation avec contraintes est ainsi modifié :

\(Min~~~ f^*(\Delta x) = f(x) +\nabla f^T(x) \Delta x + \frac{1}{2} \Delta x^T H(x) \Delta x\)

avec :

\(h_k^*(\Delta x) = h_k(x) +\nabla h_k^T(x) \Delta x =0~~~~~~ k=1,2,... K\)

\(g_j^*(\Delta x) = g_j(x) +\nabla g_j^T(x) \Delta x ≤0~~~~~~ j=1,2,... J\)

\(\Delta x_i^l≤\Delta x_i≤\Delta x_i^u~~~~~~ i=1,2,... N\)

\(\Delta x\)

L'optimisation porte donc sur des fonctions approximées (avec une étoile). On cherche l'accroissement (\(\Delta x\)) qui va permettre de minimiser cette nouvelle fonction objectif tout en respectant les contraintes. Dans l'idéal, le terme de second ordre devrait être la matrice hessienne mais comme son évaluation à chaque itération va être trop coûteuse en termes de temps de calcul, c'est une matrice approchée qui sera utilisée selon les mises en œuvre pratiques.

La fonction objectif est de nature quadratique et est donc convexe ; pour une telle formulation, on peut démontrer qu'un minimum unique peut être trouvé. Des algorithmes très efficaces, basés sur des méthodes de résolution de systèmes linéaires, ont été mis au point pour déterminer des directions de recherche. Ensuite, plusieurs variantes existent pour déterminer une longueur qui va permettre de vérifier les contraintes selon la direction de recherche choisie. Des variantes existent aussi sur la manière dont est calculée la « pseudo-matrice hessienne ».