Eclats de vers : Matemat : Algorithmes d’optimisation libre
Table des matières
\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\left] #1 , #2 \right[} \newcommand{\intervallesemiouvertgauche}[2]{ \left] #1 , #2 \right]} \newcommand{\intervallesemiouvertdroite}[2]{\left[ #1 , #2 \right[ } \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \DeclareMathOperator*{\strictinferieur}{\ < \ } \DeclareMathOperator*{\strictsuperieur}{\ > \ } \DeclareMathOperator*{\ensinferieur}{\eqslantless} \DeclareMathOperator*{\enssuperieur}{\eqslantgtr} \DeclareMathOperator*{\esssuperieur}{\gtrsim} \DeclareMathOperator*{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \DeclareMathOperator*{\pgcd}{pgcd} \DeclareMathOperator*{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \vert #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \vert #2 \vert #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \vert #3 \vert #5 \right\rangle_{#2,#4}} \DeclareMathOperator*{\major}{major} \DeclareMathOperator*{\minor}{minor} \DeclareMathOperator*{\maxim}{maxim} \DeclareMathOperator*{\minim}{minim} \DeclareMathOperator*{\argument}{arg} \DeclareMathOperator*{\argmin}{arg\ min} \DeclareMathOperator*{\argmax}{arg\ max} \DeclareMathOperator*{\supessentiel}{ess\ sup} \DeclareMathOperator*{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \DeclareMathOperator*{\adh}{adh} \DeclareMathOperator*{\interieur}{int} \newcommand{\frontiere}{\partial} \DeclareMathOperator*{\image}{im} \DeclareMathOperator*{\domaine}{dom} \DeclareMathOperator*{\noyau}{ker} \DeclareMathOperator*{\support}{supp} \DeclareMathOperator*{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \DeclareMathOperator*{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \DeclareMathOperator*{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\PD}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \DeclareMathOperator*{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \DeclareMathOperator*{\composante}{comp} \DeclareMathOperator*{\bloc}{bloc} \DeclareMathOperator*{\ligne}{ligne} \DeclareMathOperator*{\colonne}{colonne} \DeclareMathOperator*{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \DeclareMathOperator*{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \DeclareMathOperator*{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)
\( \newenvironment{Eqts} { \begin{equation*} \begin{gathered} } { \end{gathered} \end{equation*} } \newenvironment{Matrix} {\left[ \begin{array}} {\end{array} \right]} \)
\label{chap:algoptim}
1. Introduction
Nous allons présenter des algorithmes permettant de résoudre approximativement des problèmes de minimisation d'une fonction \(\varphi\) sur \(\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)^\dual\]
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. Minimum dans une direction
Soit l'itération :
\[x_{k+1} = x_k - \alpha_k \cdot p_k\]
où \(\alpha_k \in \setR\) et \(p_k \in \setR^n\). On choisit généralement le paramètre \(\alpha_k\) de façon à minimiser le développement d'ordre deux :
\[\varphi_{k + 1} \approx \varphi_k - \alpha_k \cdot J_k^\dual \cdot p_k + \frac{\alpha_k^2}{2} \cdot p_k^\dual \cdot H_k \cdot p_k\]
En imposant l'annulation de la dérivée de ce développement par rapport à \(\alpha_k\), on en déduit que :
\[- J_k^\dual \cdot p_k + \alpha_k \cdot p_k^\dual \cdot H_k \cdot p_k = 0\]
La valeur optimale de \(\alpha_k\) s'écrit :
\[\alpha_k = \frac{J_k^\dual \cdot p_k}{p_k^\dual \cdot H_k \cdot p_k}\]
3. Méthode de la plus grande descente
La méthode de la plus grande pente consiste à partir à chaque itération du point \(x^{(k)}\) et à suivre la direction \(\delta_k\) où \(\varphi\) descend le plus rapidement dans le voisinage immédiat. En première approximation, si :
\[x_{k + 1} = x_k + \alpha_k \cdot \delta_k\]
pour un certain \(\alpha_k \in \setR\), on a :
\[\varphi_{k+1} \approx \varphi_k + \alpha_k \cdot J_k^\dual \cdot \delta_k\]
Nous choisissons le vecteur \(\delta_k\) qui minimise \(J_k^\dual \cdot \delta_k = \scalaire{J_k}{\delta_k}\) sur \(\boule(0,\norme{J_k})\), c'est-à-dire :
\[\delta_k = - J_k\]
On a alors :
\[x_{k + 1} = x_k - \alpha_k \cdot J_k\]
La valeur optimale de \(\alpha_k\) s'écrit donc :
\[\alpha_k = \frac{J_k^\dual \cdot J_k}{J_k^\dual \cdot H_k \cdot J_k}\]
4. Newton
Il s'agit ici d'optimiser le pas \(s_k\) :
\[x_{k + 1} = x_k + s_k\]
pour minimiser le développement :
\[\varphi_{k+1} \approx \varphi_k + J_k^\dual \cdot s_k + \unsur{2} \cdot s_k^\dual \cdot H_k \cdot s_k\]
Mais comme \(H = H^\dual\), l'annulation du gradient par rappord à \(s_k\) nous donne :
\[J_k + H_k \cdot s_k \approx 0\]
On en déduit la valeur optimale :
\[s_k = - H_k^{-1} \cdot J_k\]
5. Gradients conjugués
Soit l'itération :
\[x_{k + 1} = x_k - \alpha_k \cdot p_k\]
où \(\alpha_k \in \setR\) et \(p_k \in \setR^n\). On a comme d'habitude :
\[\alpha_k = \frac{J_k^\dual \cdot p_k}{p_k^\dual \cdot H_k \cdot p_k}\]
Lorsque \(k = 0\), on prend le gradient comme direction :
\[p_0 = J_0\]
Pour \(k \ge 1\), on choisit \(p_k\) comme combinaison linéaire du gradient \(J_k\) et du pas précédent \(p_{k - 1}\) :
\[p_k = J_k - \beta_k \cdot p_{k-1}\]
où \(\beta_k \in \setR\). L'idée des gradients conjugué est de construire une suite de \(p_k\) orthogonaux entre-eux afin de minimiser la fonction dans toutes les directions. Au bout de \(n\) itérations, on espère avoir construit une base de \(\setR^n\) et être très proche du minimum global. En fait, nous n'allons pas vérifier que toutes les directions sont orthogonales, mais seulement que deux directions successives le sont. On demande donc l'orthogonalité au sens du produit scalaire défini par \(H\) :
\[p_k^\dual \cdot H_k \cdot p_{k - 1} = J_k^\dual \cdot H_k \cdot p_{k - 1} - \beta_k \cdot p_{k - 1}^\dual \cdot H_k \cdot p_{k - 1} = 0\]
On en déduit la valeur de \(\beta_k\) :
\[\beta_k = \frac{J_k^\dual \cdot H_k \cdot p_{k - 1}}{p_{k - 1}^\dual \cdot H_k \cdot p_{k - 1}}\]
Nous allons à présent obtenir une valeur approximative de \(\beta_k\) en fonction des variations du gradient. Le développement d'ordre un de \(J\) s'écrit :
\[J_k - J_{k - 1} \approx H_k \cdot (x_k - x_{k - 1}) = - \alpha_k \cdot H_k \cdot p_{k - 1}\]
On en déduit que :
\[\beta_k \approx \frac{J_k^\dual \cdot (J_k - J_{k - 1})}{p_{k - 1}^\dual \cdot (J_k - J_{k - 1})}\]
6. Moindres carrés
Soit la fonction \(f : \setR^n \mapsto \setR^m\). On cherce à minimiser la fonction \(\varphi = f^\dual \cdot f / 2\). Le problème de minimisation s'écrit alors :
\[\arg\min_x \unsur{2} f(x)^\dual \cdot f(x)\]
Dans ce cas, si on définit :
\[D = \partial f\]
le gradient s'écrit :
\[J = D^\dual \cdot f\]
Si on suppose que les dérivées secondes de \(f\) sont négligeables par rapport aux dérivées premières, on a :
\[H \approx D^\dual \cdot D\]
La méthode de Newton devient dans ce cas :
\[x_{k+1} = x_k + s_k\]
avec :
\[s_k = -[D_k^\dual \cdot D_k]^{-1} \cdot D_k^\dual \cdot f_k\]
6.1. Zéros
Si \(S = \noyau f \ne \emptyset\), soit \(\gamma \in S\). On a alors :
\[0 \le \min \unsur{2} f(x)^\dual \cdot f(x) \le \unsur{2} f(\gamma)^\dual \cdot f(\gamma) = 0\]
On en déduit que tout \(x \in \setR^n\) minimisant \(\varphi\) vérifiera \(f(x) = 0\). La méthode de minimisation nous fournit donc une approximation d'un tel \(x\).
7. Levenberg-Marquardt
C'est une variante de la méthode des moindres carrés, utile dans les cas où \(D_k^\dual \cdot D_k\) est numériquement proche d'une matrice non inversible. On ajoute alors la matrice identité multipliée par un scalaire \(\lambda\) sur la diagonale :
\[s_k = -[D_k^\dual \cdot D_k+ \lambda_k \cdot I]^{-1} \cdot D_k^\dual \cdot f_k\]