Eclats de vers : Matemat : Algorithme d’optimisation contrainte
Table des matières
\( \newenvironment{Eqts} { \begin{equation*} \begin{gathered} } { \end{gathered} \end{equation*} } \newenvironment{Matrix} {\left[ \begin{array}} {\end{array} \right]} \)
\label{chap:algocont}
1. Introduction
Nous allons présenter des algorithmes permettant de résoudre approximativement des problèmes de minimisation d'une fonction \(\varphi\) sur un ensemble \(\Omega \subseteq \setR^n\). Ces algorithmes partent d'un point initial \(x_0 \in \Omega\) et itèrent schématiquement comme suit :
\[x_{k + 1} = I(x_k) = x_k + p_k\]
pour un certain \(p_k \in \setR^n\). On espère bien entendu que la suite converge et que :
\[x_N \approx \lim_{k \to \infty} x_k = \arg\min_{x \in \Omega} \varphi(x)\]
pour \(N\) assez grand. Nous adoptons les notations :
\[J = \partial \varphi\]
pour le gradient, de taille \((n,1)\) et :
\[H = \partial^2 \varphi\]
pour la hessienne, de taille \((n,n)\). On note également :
\[\Phi_k = \Phi(x_k)\]
pour toute fonction \(\Phi\) (par exemple, \(\Phi \in \{\varphi,J,H\}\)).
2. Contraintes linéaires
Nous considérons le cas de contraintes linéaires :
\[\Omega = \{ x \in \setR^n : A \cdot x = b \}\]
où \(A\) est une matrice de taille \((m,n)\) et \(b\) un vecteur de taille \((m,1)\). On choisit généralement \(x_0 = 0\). L'itération \(k\) part d'un \(x_k\) satisfaisant les contraintes :
\[A \cdot x_k = b\]
Si on veut que \(x_{k + 1} = x_k + s_k \in \Omega\), il est nécessaire et suffisant que \(A \cdot (x_k + s_k) = b\), ou que :
\[A \cdot s_k = A \cdot (x_k + s_k) - A \cdot x_k = b - b = 0\]
On doit donc avoir \(s_k \in \noyau A\). Soit les \(u_i \in \setR^m\), \(v_i \in \setR^n\) et \(\sigma_i \in \setR\) constituant la décomposition en valeurs singulières de \(A\). On forme une matrice à partir des vecteurs de base de \(\noyau A\) :
\[V = [v_{r + 1} \ ... \ v_n]\]
On a alors :
\[s_k = \sum_{i = r + 1}^n p_{k,i} \cdot v_i = V \cdot p_k\]
où \(p_k = [p_{k, r + 1} ... p_{k,n}]^\dual\).
2.1. Newton projeté
Il s'agit de l'adaptation de la méthode de Newton :
\[x_{k + 1} = x_k + V \cdot p_k\]
On minimise le développement d'ordre deux :
\[\varphi_{k+1} \approx \varphi_k + J_k^\dual \cdot V \cdot p_k + \unsur{2} \cdot p_k^\dual \cdot V^\dual \cdot H_k \cdot V \cdot p_k\]
L'annulation du gradient par rapport à \(p_k\) nous donne :
\[V^\dual \cdot J_k + V^\dual \cdot H_k \cdot V \cdot p_k = 0\]
et donc :
\[p_k = - (V^\dual \cdot H_k \cdot V)^{-1} \cdot V^\dual \cdot J_k\]
3. Contraintes d'inégalité
Examinons à présent le cas où :
\[\Omega = \{ x \in \setR^n : \omega(x) \le 0 \}\]
Nous laissons à présent tomber le \(k\) des itérations, afin d'alléger les notations.
3.1. Méthodes de penalité
La méthode de pénalité consiste à ajouter une fonction positive à \(\varphi\) lorsque \(x\) sort de \(\Omega\). Si l'on augmente la valeur de la fonction pénalité, on rapproche alors le minimum global de \(\Omega\). La solution à notre problème contraint devrait donc être approchée en faisant tendre l'amplitude de la pénalité vers l'infini. Soit la fonction \(\varpi : \setR^n \mapsto \setR^m\) définie par :
\[\varpi_i(x) = \max\{\omega_i(x),0\}\]
On a par construction \(\varpi(x) = 0\) pour tout \(x \in \Omega\) et \(\varpi(x) \strictsuperieur 0\) pour tout \(x \notin \Omega\). On ajoute la somme des carrés \(\varpi(x)^\dual \cdot \varpi(x) = \sum_i \varpi_i(x)^2\) multipliée par un paramètre réel \(k \ge 0\) à la fonction objectif pour obtenir l'objectif modifié :
\[\psi_k(x) = \varphi(x) + k \cdot \varpi(x)^\dual \cdot \varpi(x)\]
On utilise ensuite un algorithme de minimisation libre pour évaluer le minimum global :
\[\mu(k) = \arg\min_{x \in \setR^n} \psi_k(x)\]
On espère que \(\mu\) converge à l'infini et que :
\[\lim_{k \to \infty} \mu(k) = \arg\min_{x \in \Omega} \varphi(x)\]
Il suffit dans ce cas de choisir \(k\) assez grand pour obtenir une estimation de la solution du problème contraint.