02_optimisation.md



Optimisation

La régression linéaire
Lors d'une régression linéaire, le but est de trouver la droite, 
 $y(x)=a\cdot x + b$ 
, qui passe au mieux au travers d'un nuage de  $N$ 
 points  $(x_i, y_i)$ ,
 $i=1,...,N$ 
 (voir @fig:reg).

Pour déterminer l'équation de cette droite, nous devons donc trouver les coefficients 
 $a$ 
 et  $b$  tels que la droite
passe au plus proche des points. Nous devons d'abord définir ce que signifie mathématiquement "passe au mieux par au travers du nuage de points".
Une façon de mesurer la "qualité" d'une droite est de mesurer la somme des distances au carré entre les points  $(x_i,y_i)$  et
la droite  $y(x)=a\cdot x + b$ 
 pour des valeurs de  $a$ 
 et  $b$  données, soit
 $E(a,b)=\sum_{i=1}^N (y(x_i)-y_i)^2.$ 
Nous cherchons par conséquent à minimiser  $E(a,b)$ 
 sous la contrainte que  $y(x)$  est une droite. Pour simplifier encore plus le problème mathématique,
nous pouvons rajouter comme contrainte que la droite  $y(x)$ 
 passe par le point  $(0,0)$ 
, on a donc que  $y(x)=a\cdot x$ 
 (l'ordonnée à l'origine est nulle,  $b=0$ ) et que
 $E(a)=\sum_{i=1}^N (y(x_i)-y_i)^2,$ 
est indépendant de  $b$ . En résumé nous cherchons à résoudre le problème mathématique
\begin{align}
&\min_{a\in\real} E(a) = \min_{a \in\real} \sum_{i=1}^N (y(x_i)-y_i)^2,\
&\mbox{où }y(x)=a\cdot x, \quad \mbox{(contrainte)}.
\end{align}
On peut réécrire la fonction  $E(a)$  comme
\begin{align}
E(a)&=\sum_{i=1}^N \left(y^2(x_i)-2\cdot y_i\cdot y(x_i)+y_i^2\right)=\sum_{i=1}^N \left(a^2\cdot x_i^2-2\cdot a\cdot x_i\cdot y_i+y_i^2\right),\nonumber\
&=a^2\sum_{i=1}^Nx_i^2 + 2a\sum_{i=1}^Nx_iy_i+\sum_{i=1}^Ny_i^2.
\end{align}
Les  $x_i$ 
 et  $y_i$ 
 étant connus, nous cherchons  $a$ 
, tel que E(a)
 soit minimal. E(a) est en fait l'équation d'une parabole: elle a la forme

E(a)=B\cdot a^2-2C\cdot a + D,

avec B=\sum_{i=1}^Nx_i^2
, C=\sum_{i=1}^Nx_iy_i
, et D=\sum_{i=1}^N y_i^2
. B
 étant forcément positif cette parabole sera convexe et donc
nous sommes assurés qu'il existe un minimum pour E(a)
. Une façon de déterminer a
, tel que E(a) est minimal est d'utiliser la dérivée.
On a l'équation E'(a)=0 à résoudre:
\begin{align}
E'(a)&=0,\nonumber\
2\cdot B\cdot a-2\cdot C&=0,\nonumber\
a &= \frac{C}{B}=\frac{\sum_{i=1}^Nx_iy_i}{\sum_{i=1}^Nx_i^2}.
\end{align}


Exemple {-}
Soient les 4 points 
(0, 0.1)
, (1, 0.3)
, (2, 0.3)
 et (3, 0.4)
. La fonction d'erreur E(a) s'écrit

E(a)=14\cdot a^2-4.2\cdot a + 0.35.

On peut la représenter comme sur la @fig:e_a et on constate qu'elle possède un minimum proche de a=0
.

En résolvant 
E'(a)=0
, on obtient a=4.2/28=0.15
. On a que l'équation de la droite passant par (0,0) et au plus proche de nos 4 points est

y(x)=0.15\cdot x.

On peut observer le résultat de la régression sur la @fig:regression_ex, où on voit les 4 points (en noir), ainsi que la droite obtenue (en trait bleu).


La régression linéaire est un problème d'optimisation continu (par opposition aux problèmes d'optimisation discrets).
Ce genre de problème, bien que possédant un espace de recherche infini,
est bien souvent plus simple à résoudre que les problèmes d'optimisation discrets, car il possède un cadre théorique mieux défini.
Pour le résoudre, nous avons commencé par construire un modèle mathématique.
Nous avons défini une fonction à minimiser, 
E(a)
, et ajouté une contrainte, la forme de y(x)
. Puis, il a suffi de trouver le minimum de E(a)
sous la contrainte et le tour était joué.

L'optimisation mathématique
Suite à ces deux exemples, nous allons essayer de définir de façon assez théorique comment formuler mathématiquement un problème d'optimisation.
Il existe deux types distincts de problèmes d'optimisation:

L'optimisation continue.
L'optimisation discrète (souvent appelée optimisation combinatoire).

Dans ce chapitre nous ne parlerons que de l'optimisation continue.

L'optimisation continue
L'optimisation continue ou programme mathématique continu est un programme d'optimisation soumis à certaines contraintes.
On peut l'exprimer de la façon suivante.
Soit 
f:\real^n\rightarrow\real
 une fonction objectif (ou fonction de coût), on cherche \vec x_0\in\real^n
, tel que f(\vec x_0)\leq f(\vec x) pour \vec x certaines conditions: les contraintes. Celles-ci sont en général des égalités strictes ou des inégalités qui peuvent s'exprimer de la façon suivante.
Soient m fonctions g_i:\real^n\rightarrow\real
\begin{align}
&g_i(\vec x)\leq 0,\quad i=1,...,m.
\end{align}
Si m=0 on a à faire à un problème d'optimisation sans contraintes. On peut résumer tout cela comme
\begin{align*}
&\min_{\vec x\in\real^n}f(\vec x),\
&g_i(\vec x)\leq 0,\quad i=1,...,m,\
&\mbox{pour }m\geq 0.
\end{align*}
Les contraintes limitent l'espace des solutions et forment un sous-ensemble, noté A, de \real^n (A\subseteq\real^n).
Une des difficultés pour déterminer le minimum d'une fonction coût est l'existence de plusieurs minima locaux.
Un minimum local, \vec x^\ast\in A, est tel que pour une région proche de \vec x^\ast, on a que f(\vec x)\geq f(\vec x^\ast).
Un exemple d'une telle fonction, est une fonction de Ackley. En une dimension, elle est de la forme (voir la @fig:ackley)

f(x)=-20e^{-0.2*\sqrt{0.5x^2}}-e^{0.5(\cos(2\pi x))}+e+20.


On constate la présence d'un grand nombre de minima locaux qui rendent la recherche du minimum global (se trouvant en x=0) particulièrement compliqué à déterminer.
L'optimisation continue est très communément utilisée en apprentissage automatique (machine learning), en particulier pour
optimiser les poids des réseaux de neurones.

Optimisation continue
Dans cette section, nous allons considérer des problèmes purement continus.
Nous allons dans un premier temps considérer une fonction objectif, f,

f:D\rightarrow\real,\quad D\subseteq \real,

dont nous allons chercher le minimum (pour autant qu'il existe). Nous allons supposer que
f est une fonction continue et dérivable.

Minimum local/global
Comme vous le savez, le minimum (ou le maximum) d'une fonction, se situe à un endroit où sa dérivée est nulle.
On recherche donc, x, tel que

f'(x)=0.

Mais cette contrainte sur f'(x) n'est pas suffisante pour garantir de trouver un minimum.
En effet, si f'(x)=0, peut également vouloir dire qu'on se trouve sur un point d'inflexion
ou sur un maximum.
On peut assez facilement, discriminer ces deux cas, en considérant la deuxième dérivée de f.
En effet, nous avons à faire à un minimum seulement si

f''(x)>0.

Les cas où f''(x)=0 est un point d'inflexion et f''(x)<0 est un maximum.
Un autre problème beaucoup plus compliqué à résoudre est de déterminer un minimum global.
En effet, comme pour la fonction de Ackley (voir la @fig:ackley), une fonction peut posséder un grand nombre de minima locaux (où
f'(x)=0 et f''(x)>0) mais qui n'est pas un minimum global.
Mathématiquement un minimum local se définit comme x^\ast tel qu'il existe \delta>0 et que f(x^\ast)\leq f(x), pour
x\in[x^\ast-\delta,x^\ast+delta]. Un minimum global est un x^\ast tel que \forall x\in D, f(x^\ast)\leq f(x).
En fait, il n'existe pas de méthode pour déterminer un minimum global, pour n'importe quelle fonction.
Nous somme assurés de le trouver, uniquement si f est une fonction convexe partout (f''(x)>0 \ \forall x).

Algorithmes de recherche des zéros d'une fonction
Comme nous venons de le voir, lors de la recherche d'un minimum, il est nécessaire de trouver le point x^\ast
où f'(x^\ast)=0. Le problème est donc de déterminer les zéros de la fonction f'(x). Pour avoir un maximum de généralité,
nous allons considérer une fonction g(x) et chercher ses zéros, soit

\{x\in\real|g(x)=0\}.

Dans des cas simples (des fonctions polynomiales de degré 2 ou 3, ou des fonctions inversibles) on peut trouver
analytiquement les zéros. En revanche, pour des fonctions plus complexes, ou "implicites" (on ne peut pas mettre
l'équation g(x)=0 sous la forme x=...) la détermination des zéros est beaucoup plus difficile et nécessite l'utilisation
de méthodes itératives. Nous allons en voir quelques unes.

Méthodes par raffinement d'intervalles

Méthode de la bissection

Afin de déterminer le zéro d'une fonction, une des méthodes les plus simple est la méthode de la bissection.
Il s'agit de choisir deux points, a_1 et b_1, b_1>a_1, tels que le signe de g(a_1) et g(b_1) est différent.
Si cela est le cas, nous sommes assurés de l'existence d'au moins un zéro si la fonction g(x) est continue
(en vertu du théorème de la valeur intermédiaire). Ensuite, nous allons calculer la valeur se situant "au milieu"
entre a_1 et b_1

c_1=\frac{b_1+a_1}{2}.

Puis, nous évaluons g(c_1) et si ce n'est pas un zéro, étudions son signe. Si le signe g(c_1) est différent de celui de g(a_1), nous remplaçons
b_1 par c_1 et recommençons. Si le signe de g(c_1) est différent de celui de g(b_1), nous remplaçons a_1 par c_1.
Nous itérons cette méthode jusqu'à ce que nous ayons atteint une valeur "suffisamment proche" (nous avons une précision acceptable pour nous)
de zéro. Une façon d'exprimer "proche" est de considérer la taille de l'intervalle b_1-a_1 et de le comparer avec une précision \varepsilon>0 que nous
aurons choisie

b_1-a_1<\varepsilon.

Au pire des cas, cette méthode nous rapproche de (b_1+a_1)/2 du zéro à chaque itération. Après n itération, nous somme donc à une
distance maximale du zéro de (b_1+a_1)/2^n. On dit que cette méthode est d'ordre 1 (on divise l'intervalle de recherche par 2 et la précision par 2
à chaque itération).


Exercice (Racine de polynôme) {-}
Déterminer la racine du polynôme x^4+x^3+x^2-1 avec a_1=0.5 et b_1=1 (faire au maximum 6 itérations).


Méthode de la fausse position (regula falsi)

Une méthode un peu plus avancée est la méthode de la fausse position (voir la @fig:false_position_method). Dans cette méthode qui est relativement similaire à celle de la bissection,
mais au lieu de diviser l'intervalle en deux parts égales à chaque itération on va choisir les point c, comme étant le point
où la droite reliant g(a_1) et g(b_1) coupe l'axe horizontal (le zéro de la droite entre g(a_1) et g(b_1)). Le reste de l'algorithme reste exactement le même.
On choisit deux points, a_1 et b_1, où le signe de f est différent, puis ont construit la droite passant par g(a_1) et g(b_1)

y=\frac{g(b_1)-g(a_1)}{b_1-a_1}(x-a_1) + g(a_1).

On cherche le point, c, où y(c)=0

\frac{g(b_1)-g(a_1)}{b_1-a_1}(c-a_1) + g(a_1)=0.

Cette équation s'inverse aisément et on obtient

c_1=a_1-\frac{b_1-a_1}{g(b_1)-g(a_1)}g(a_1).

Puis, comme pour la méthode de la bissection, on compare les signes de g(c_1) avec g(a_1) et g(b_1) et on remplace a_1 ou b_1 par c_1
si g(c_1) a un signe différent de g(b_1) ou g(a_1) respectivement.
Il est important de noter que si la fonction est continue, et que a_1 et b_1 sont choisis tels que g(a_1) et g(b_1) sont de signes opposés,
alors cette méthode convergera toujours.
La méthode de la fausse position est plus efficace que la méthode de la bissection, elle est superlinéaire (d'ordre plus grand que un).


Exercice {-}
Déterminer le zéro positif de la fonction

x^2-25=0,

à l'aide de la méthode de la fausse position.


Méthode de la sécante

La méthode de la sécante (voir la @fig:secant_method) est très similaire à la méthode de la fausse position. La seule différence se situe dans la dernière étape de l'algorithme.
Plutôt que choisir de remplacer a_1 ou b_1 par c_1, on remplace toujours la dernière valeur calculée.
Ainsi après avoir choisi a < b, avec g(a) et g(b) avec des signes différents, on calcule
une suite de x_i, avec x_0=a, x_1=b, tels que

x_{i+1}=x_{i-1}-\frac{x_i-x_{i-1}}{g(x_i)-g(x_{i-1})}g(x_{i-1}), \quad  i\geq 2.

La méthode de la sécante ne garantit pas la convergence, contrairement à la méthode de la bissection et de la fausse position.
En revanche elle est plus efficace, lorsque qu'elle converge, que ces deux méthodes.


Exercice {-}
Déterminer le zéro positif de la fonction

x^2-25=0,

à l'aide de la méthode de la sécante.


Recherche de la fourchette initiale
Dans les méthodes ci-dessus, nous avons supposé que nous avions une fonction g(x) continue, ainsi qu'un intervalle, [a,b],
avec
\begin{equation}
g(a)<0,\quad g(b)>0.
\end{equation}
Mais, nous n'avons pas encore vu de méthode pour déterminer les valeur de la fourchette a,b.


Remarque {-}
On peut procéder de façon très similaire pour [a,b] tel que
\begin{equation}
g(a)>0,\quad g(b)>0.
\end{equation}
Il suffit de prendre remplacer g(x)\rightarrow -g(x).

Les méthodes pour déterminer la fourchette initiales sont également des méthodes itératives.
La plus simple qu'on puisse imaginer est de partir d'un point initial a (choisi aus hasard par exemple).
On suppose que g(a)<0 (sinon voir la remarque ci-dessus).
Puis on choisir deux hyperparamètres: \delta x et k[^10]. Ensuite on calcule b=a+k\cdot \delta x.
Si f(b)>0, on a terminé. Sinon on recommence avec k\rightarrow 2\cdot k et b\rightarrow k\cdot b.

Méthodes de descentes locales
L'idée de ce type de méthodes est, contrairement aux méthodes de la section précédente, d'utiliser des
connaissances locales que nous pouvons avoir sur la fonction. Cette connaissance locale
a en général comme effet une convergence plus rapide de l'algorithme de recherche de zéros.

Méthode de Newton (ou Newton-Raphson)
La méthode de Newton est également une méthode itérative, qui nécessite que la fonction g(x) soit non seulement continue mais également dérivable.
Revenons sur la méthode de la sécante. Il s'agissait de choisir deux points, a < b, et de déterminer la droite, y(x), passant par g(a) et g(b),
\begin{equation*}
y=\frac{g(b)-g(a)}{b-a}(x-a) + g(a).
\end{equation*}
Il se trouve que g(b)-g(a)/(b-a) n'est autre qu'une approximation avec une formule de différences finies
de la dérivée de g et a, g'(a). Si la fonction g est dérivable, on peut simplement remplacer ce terme par g'(a)
et on obtient

y=g'(a)(x-a) + g(a).

Puis on détermine c, tel que y(c)=0

0=g'(a)(c-a) + g(a),

et on obtient

c=a - \frac{g(a)}{g'(a)}.

On peut donc généraliser l'algorithme. En partant d'un point x_0=a, on construit la suite

x_{i+1}=x_n-\frac{g(x_i)}{g'(x_i)}, \ i\geq 0.

On s'arrête lorsque le zéro est déterminé avec une précision suffisante, ou que la variation entre deux itérations successives est assez petite. Ce qui revient à choisir un \varepsilon>0, tel que

|g(x_n)| < \varepsilon,\quad |x_n-x_{n-1}| < \varepsilon.

Lorsque qu'elle converge la méthode de Newton est la plus efficace de toutes celles que nous avons vues. On dit qu'elle est d'ordre 2.
En revanche les contraintes pour sa convergence sont plus strictes que pour les méthodes vues précédemment.


Remarque (non-convergence ou convergence lente) {-}
Il y a un certain nombre de cas où la méthode de Newton ne converge pas.

S'il existe un n tel que g'(x_n)=0 alors la suite diverge.
La suite peut entrer dans un cycle.
La dérivée est mal définie proche du zéro (ou sur le zéro).
Elle peut converger très lentement si la dérivée de la fonction est nulle sur le zéro.
A chaque point de départ ne correspond qu'un zéro. Si la fonction possède plusieurs zéros, il n'y a pas moyen de le savoir avec un seul point de départ. Il faut alors en essayer plusieurs.


Exercice {-}
Déterminer le zéro de la fonction

x^2-25=0,

à l'aide de la méthode de Newton.


Résumé
A l'aide des méthodes vues ci-dessus, on peut déterminer un zéro d'une fonction (s'il existe).
Ces méthodes sont également utilisables pour calculer le minimum d'une fonction comme nous l'avons discuté plus haut.
Il suffit de remplacer g(x) par f'(x) et le tour est joué.


Exercice {-}
Écrire l'algorithme de Newton pour le cas de la minimisation d'une fonction f(x) quelconque, mais continûment dérivable 2 fois.


En plusieurs dimensions
Quand notre fonction de coût dépend de plusieurs arguments, on dit que c'est une fonction multivariée, f(\vec x), avec \vec x\in\real^n.

On peut également l'écrire de façon plus explicite (et aussi plus longue) comme
\begin{equation}
f(\vec x)=f(x_1, x_2, ..., x_n).
\end{equation}
Bien que la fonction de coût prenne en argument plusieurs variables, elle retourne uniquement un réel
\begin{equation}
f:\real^n\rightarrow \real.
\end{equation}


Exemple (Régression linéaire) {-}
Dans le cas de la régression linéaire, si la droite ne passe pas par l'origine, nous avons que
la fonction de coût qui dépend de deux variables, a, et b (et plus uniquement de a)
\begin{equation}
f(a,b)=\frac{1}{N}\sum_{i=1}^N \left(a\cdot x_i+b - y_i\right)^2.
\end{equation}


Les dérivées en plusieurs dimensions
La dérivé d'une fonction à une seule variable peut se représenter comme
\begin{equation}
f'(a)=\frac{\dd f}{\dd x}(a)=\lim_{\dd x\rightarrow 0}\frac{f(a+\dd x)-f(a)}{\dd x}.
\end{equation}
La notation ici n'est pas tout à fait usuelle. L'idée est de se rappeler que ce \dd x est une toute petite variation
de x, et \dd f, une toute petite variation de f en a. On voit immédiatement que cette quantité est la pente
de f en a. Lorsque nous étudions une fonction à plusieurs variables, nous pouvons faire le même raisonnement pour chaque variable indépendamment.
Ainsi, nous calculons sa dérivée dans chacune des directions x, y, ...
Cette vision de la dérivée comme une variation de f, \dd f, divisée par une petite variation de x, \dd x, permet
d'avoir une interprétation sur la variation locale de f(x). En effet, la variation de f(a) est donnée par

\dd f=f'(a)\dd x,

ou encore

f(a+\dd x)=f(a)+f'(a)\dd x.


Les dérivées partielles
Pour une fonction à deux variable, f(x,y), dont le domaine de définition est
\begin{equation}
f:\real^2\rightarrow \real,
\end{equation}
on définit la dérivée partielle de f par rapport à x ou à y
\begin{align}
\frac{\partial f}{\partial x}(x,y)&=\lim_{h\rightarrow 0}\frac{f(x+h,y)-f(x,y)}{h},\
\frac{\partial f}{\partial y}(x,y)&=\lim_{h\rightarrow 0}\frac{f(x,y+h)-f(x,y)}{h}.
\end{align}
Comme on le voit ici, pour chaque dérivée partielle, on ne fait varier qu'une seule variable, les autres sont considérées comme des constantes.


Exemple (Dérivée partielle) {-}
Les dérivée partielles de la fonction

f(x,y)=x^2\cdot y+3,

sont données par
\begin{align}
\frac{\partial f}{\partial x}(x,y)&=2xy,\
\frac{\partial f}{\partial y}(x,y)&=x^2.
\end{align}

Pour une fonction f dépendant d'un nombre n de variables, la notation est la suivante.
Soit f(\vec x) avec \vec x=\{x_i\}_{i=1}^n, ou \vec x\in\real^n, on définit la dérivée
par rapport à la i-ème composante de \vec x comme

\frac{\partial f}{\partial x_i}(x_1,x_2,...,x_i,...,x_n)=\lim_{h\rightarrow 0}\frac{f(x_1,x_2,...,x_i+h,...,x_n)-f(x_1,x_2,...,x_i,...,x_n)}{h}.


Remarque {-}
Pour une fonction à une seule variable, f(x), on a que

f'(x)=\frac{\dd f}{\dd x}(x)=\frac{\partial f}{\partial x}(x).


De façon similaire à ce qui se passe pour les fonction à une seule variables, nous pouvons définir les dérivées secondes
pour les façon à une seule variable. Pour une fonction à deux variables, on a en fait quatre dérivées secondes
\begin{align}
&\frac{\partial}{\partial x}\frac{\partial f}{\partial x}(x,y)=\frac{\partial^2 f}{\partial x^2}(x,y),\
&\frac{\partial}{\partial x}\frac{\partial f}{\partial y}(x,y)=\frac{\partial^2 f}{\partial x\partial y}(x,y),\
&\frac{\partial}{\partial y}\frac{\partial f}{\partial x}(x,y)=\frac{\partial^2 f}{\partial y\partial x}(x,y),\
&\frac{\partial}{\partial y}\frac{\partial f}{\partial y}(x,y)=\frac{\partial^2 f}{\partial y^2}(x,y).
\end{align}


Remarque {-}
Si f est dérivable en x et y, on a que

\frac{\partial^2 f}{\partial x\partial y}(x,y)=\frac{\partial^2 f}{\partial y\partial x}(x,y).


Exemple (Dérivées partielles deuxièmes) {-}
Pour la fonction f(x,y)=x^2-y^2, on a
\begin{align}
\frac{\partial^2 f}{\partial x^2}(x,y)=\frac{\partial (2\cdot x)}{\partial x}(x,y)=2,\
\frac{\partial^2 f}{\partial x\partial y}(x,y)=\frac{\partial (-2\cdot y)}{\partial x}(x,y)=0,\
\frac{\partial^2 f}{\partial y\partial x}(x,y)=\frac{\partial (2\cdot x)}{\partial y}(x,y)=0,\
\frac{\partial^2 f}{\partial y^2}(x,y)=\frac{\partial (-2\cdot y)}{\partial y}(x,y)=-2.
\end{align}

On peut également généraliser pour des fonction à n variables où la deuxième dérivée partielle
par rapport aux variables x_i, x_j s'écrit

\frac{\partial^2 f}{\partial x_i\partial x_j}(x,y).


Le gradient
Pour une fonction à deux variables, f(x,y), on a vu qu'on peut calculer ses dérivées partielles par rapport à x et y

\frac{\partial f}{\partial x}, \quad \frac{\partial f}{\partial y}.

Une construction mathématique possible est d'écrire un vecteur avec ces deux quantités

\grad f(x,y)=\vec \nabla f(x,y)=\left(\frac{\partial f}{\partial x}(x,y), \frac{\partial f}{\partial y}(x,y)\right)^\mathrm{T}.

Le symbole nabla, \vec \nabla, est une notation un peu étrange. Il représente un vecteur contenant toutes les
dérivées partielles

\vec \nabla = \left(\frac{\partial}{\partial x}, \frac{\partial}{\partial y}\right)^\mathrm{T}.

Cette notation est très utile pour se souvenir de ce qu'est un gradient, car on peut l'écrire un peu comme le "produit" entre
l'opérateur \vec \nabla et f

\vec \nabla f= \left(\frac{\partial}{\partial x}, \frac{\partial}{\partial y}\right)^\mathrm{T}f=\left(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right)^\mathrm{T}.

On peut généraliser cette notation pour n variables à

\vec \nabla=\left(\frac{\partial}{\partial x_1}, \frac{\partial}{\partial x_2}, ..., \frac{\partial}{\partial x_n}\right)^\mathrm{T}.

et

\vec \nabla f=\left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, ..., \frac{\partial f}{\partial x_n}\right)^\mathrm{T}.


Exemple (Gradient d'une fonction à deux variables) {-}
Pour la fonction f(x,y)=x^2-y^2, le gradient est donné par

\vec \nabla f=\left(2x, -2y\right)^\mathrm{T}.

Graphiquement, ceci est un champs de vecteur est peut se représenter comme


Revenons à nos fonctions à deux variables. Le gradient d'une fonction a une très grande utilité pratique. En effet, il nous donne la variation de f
dans chacun des direction de l'espace. On peut donc (un peu comme on avait fait pour les fonctions à une dimensions)
se poser la question de la variation de f dans une direction particulière, \vec v. Comme nous connaissons le taux de variation
de f dans chacune des directions, nous pouvons définir la dérivée directionnelle de f en un point (a,b), comme

(\vec \nabla_{\vec v} f)(a,b)=(\vec \nabla f)(a,b)\cdot \vec v,

où \vec v=(v_1,v_2)^\mathrm{T}.
Cette grandeur représente la variation de f(a,b) dans une direction particulière, \vec v. Comme pour les fonctions à une variable on peut écrire
que

f(a + v_1, b + v_2)=f(a,b)+\vec v\cdot (\vec \nabla f(a,b)).

Cette dérivée directionnelle va nous permettre d'interpréter ce que représente le gradient d'une fonction.
En fait, le gradient a une interprétation très intéressante. Ce n'est rien d'autre que la direction de la pente la plus élevée
sur chaque point de la fonction. C'est la direction, si vous faites de la randonnée en montagne,
qui vous permettra de monter le long de la pente la plus raide en chaque point.
A l'inverse, imaginez que vous êtes un skieur et que votre montagne est décrite par la fonction f(\vec x). Le vecteur -\vec \nabla f
est la direction dans laquelle vous descendez si vous suivez tout droit la pente la plus raide.
Pour s'en convaincre essayons de prendre le problème à l'envers. On cherche la dérivée directionnelle \vec \nabla_{\vec v} f, telle que celle ci-soit maximale,
pour tous les vecteur \vec v de longueur 1. En d'autres termes

\max_{||\vec v||=1} \vec v\cdot \vec \nabla f.

Il faut à présent se rappeler que le produit scalaire de deux vecteurs peut s'écrire

\vec a\cdot\vec b=||a||\cdot ||b||\cdot \cos\theta,

avec \theta l'angle entre \vec a et \vec b. De ceci, on déduit que
la valeur maximale de \vec v\cdot \vec \nabla f est atteinte quand \vec v est aligné avec
\nabla f, ce qui ne se produit que quand \vec v a la valeur

\vec v^\ast=\frac{\nabla f}{||\nabla f||}.

La variation maximale est donc atteinte quand on suit le vecteur pointé par
\nabla f. Par ailleurs, la dérivée directionnelle dans la direction
de \vec v^\ast, on a
\begin{align}
\vec\nabla_{\vec v^\ast}\cdot (\vec \nabla f)=\frac{\nabla f \cdot f}{||\vec \nabla f||}=||\vec\nabla f||.
\end{align}
Le taux de variation maximal est donc la longueur du vecteur \vec \nabla f.


Remarque (Généralisation) {-}
Tout ce que nous venons d'écrire ici se généralise à un nombre arbitraire de dimensions.


Le lien avec les problème d'optimisation
Un cas qui nous intéresse particulièrement ici, est lorsque que le gradient d'une fonction est nul

\nabla f(x,y)=\vec 0.

Cela veut dire que si nous trouvons un tel point (x,y) la variation de la fonction localement (sa "pente") sera nulle.
Exactement comme pour le cas à une seule variable cela ne suffit pas pour déterminer si nous avons à faire à
un minimum, un maximum, ou un point d'inflexion. Un exemple typique est la fonction

f(x,y)=x^2-y^2.

Bien que \nabla f(0,0)=\vec 0, nous voyons sur la @fig:selle que bien que nous ayons un minimum
dans la direction x, nous avons un maximum dans la direction y. On se retrouve dans un cas où nous avons un point-selle.
Pour pouvoir en dire plus il nous faut étudier les deuxièmes dérivées de f(x,y) comme pour
le cas unidimensionnel.
Prenons un exemple, où (voir @fig:cubic_multi pour voir à quoi elle ressemble)

f(x,y)=x^2+4y^3-12y-2.


Le gradient de f(x,y) est donné par
\begin{align}
\frac{\partial f}{\partial x}&=2x,\
\frac{\partial f}{\partial y}&=12y^2-12.
\end{align}
Les coordonnées (x,y) où \vec \nabla f=\vec 0 sont données par
\begin{align}
2x=0\Leftrightarrow x = 0,\
12y^2-12=0\Leftrightarrow y_\pm=\pm 1.
\end{align}
On a donc deux points (x,y_{-})=(0,-1) et (x,y_{+})=1 qui satisfont \vec\nabla f=0.
Essayons de connaître la nature de ces points. Sont-il des maxima, minima, ou des point-selle?
Sur la @fig:cubic_multi, on voit que le point (0, -1) est un point selle, et le point
(0,1) est un minimum. Nous allons à présent essayer de voir ce que cela veut dire mathématiquement
sans avoir besoin de regarder le graphe de cette fonction.
Inspirés par ce que nous savons des points critiques en une dimensions, nous allons étudier
les deuxièmes dérivées
\begin{align}
\frac{\partial^2 f}{\partial x^2}&=2,\
\frac{\partial^2 f}{\partial x\partial y}&=0,\
\frac{\partial^2 f}{\partial y^2}&=24y.
\end{align}
En substituant les valeur (0, -1) et (0, 1) dans les deuxièmes dérivées,
on obtient
\begin{align}
&\frac{\partial^2 f}{\partial x^2}(0,1)=\frac{\partial^2 f}{\partial x^2}(0,-1)=2,\
&\frac{\partial^2 f}{\partial x\partial y}(0,1)=\frac{\partial^2 f}{\partial x\partial y}(0,-1)=0,\
&\frac{\partial^2 f}{\partial y^2}(0,1)=24,\quad\frac{\partial^2 f}{\partial y^2}(0,-1)=-24.
\end{align}
On voit ici, que pour les deux points \frac{\partial^2 f}{\partial x^2}>0, on a donc que
dans la direction x ces deux points sont des minimas. Mais cela ne suffit pas pour en faire
des minimas locaux. Il faut également étudier ce qui se passe dans la direction y. Dans ce
cas précis, on a qu'en (0,1) nous avons une valeur positive (c'est donc un minimum) et en
(0,-1) la valeur est négative (c'est donc un maximum).
Pour récapituler:

En (0,1) c'est un minimum pour x et un minimum pour y. Et donc c'est un minimum local.
En (0,-1) c'est un minimum pour x et un maximum pour y. Et donc c'est un point-selle.

Globalement, pour avoir un min/max, il faut que les deuxièmes dérivées dans chacune des
directions donnent la même interprétation pour pouvoir conclure à un minimum/maximum. Sinon
c'est un point-selle.

La descente de gradient
Revenons à présent à l'optimisation d'une fonction de coût f(\vec x). Pour simplifier considérons
la fonction

f(x,y)=x^2+y^2.

Nous pouvons facilement nous convaincre que cette fonction possède un minimum en (0,0) en la dessinant.
On peut aussi aisément vérifier que \nabla f(0,0)=\vec 0. En effet,

\nabla f(x,y)=(2x, 2y),

et donc

\nabla f(0,0)=(0, 0).

Même si cela ne suffit pas à prouver mathématique que \vec 0 est le minimum de cette fonction nous nous en satisferons.


Question {-}
Avec ce qui précède, voyez-vous une façon de trouver le minimum de la fonction f(x,y)?

Une méthode pour trouver le minimum de f(x,y) est la méthode de la descente de gradient. Cette méthode
correspond intuitivement à la méthode que suivrait un skieur pour arriver le plus vite possible en bas d'une montagne. Pour ce faire, il suivrait toujours la pente
la plus raide possible.
La méthode de la descente de gradient est une méthode
itérative. Soient donnés un point de départ \vec x_0,
et une fonction objectif f(\vec x), on va approximer
le zéro itérativement avec une suite \vec x_1, \vec x_2, ... telle que
\begin{align}
\vec x_1&=x_0-\lambda\cdot \nabla f(\vec x_0),\
\vec x_2&=x_1-\lambda\cdot \nabla f(\vec x_1),\
\cdots
\vec x_{n+1}&=x_n-\lambda\cdot f(\vec x_n),
\end{align}
où \lambda\in \real^+ est un coefficient positif.
On peut assez facilement se convaincre que si \lambda est suffisamment petit, alors f(\vec x_{n+1})\leq f(\vec x_n) (on ne fait que descendre la pente jusqu'à atteindre un minimum). Une illustration de ce processus
peut se voir dans la @fig:gradient.


Exemple (quelques itérations) {-}
Prenons la fonction objectif f(x,y) suivante

f(x,y)=x^2+y^2,

et son gradient

\nabla f(x,y)=2x+2y.

Si on prend comme point de départ \vec x_0=(1,0.5) et \lambda=0.25, on a
\begin{align}
\vec x_1=\vec x_0-\lambda\cdot \nabla f(\vec x_0)=(1,0.5)-0.25\cdot (2\cdot 1, 2\cdot 0.5)=(0.5, 0.25),\
\vec x_2=\vec x_1-\lambda\cdot \nabla f(\vec x_1)=(0.5,0.25)-0.25\cdot (2\cdot 0.5, 2\cdot 0.25)=(0.25, 0.125),\
\cdots
\end{align}
En changeant \lambda=0.5, on voit qu'on arrive sur le zéro de la fonction en une itération
\begin{align}
\vec x_1=\vec x_0-\lambda\cdot \nabla f(\vec x_0)=(1,0.5)-0.5\cdot (2\cdot 1, 2\cdot 0.5)=(0, 0).
\end{align}

Comme pour les fonction à une seule variable, il est nécessaire de spécifier une condition d'arrêt pour
la descente de gradient. En général, on choisit une tolérance, \varepsilon>0, et la condition d'arrêt s'écrit

\mbox{Si }||\vec x_{n+1}-\vec x_n|| < \varepsilon, 

alors \vec x_{n+1} est le zéro de f(\vec x).
Dépendant de la valeur de \lambda la convergence de la méthode peut varier grandement. Si \lambda est trop petit
il faut une énorme quantité d'itérations pour atteindre le minimum. A l'inverse, en choisissant un \lambda trop grand,
nous ne somme pas sûrs que nous convergerons un jour. En effet, on pourrait s'éloigner de plus en plus
du minimum plutôt que de sen approcher. En général, on choisit \lambda\in[0,1) mais il n'y a pas de méthode générale pour en choisir une valeur "optimale".
Cela signifie que pour une fonction quelconque, \lambda est choisi de façon empirique.