Annexe E — Optimisation

L’optimisation consiste à recherche le minimum (ou le maximum) d’une fonction d’une ou plusieurs variables, éventuellement sujettes à des contraintes.

E.1 Optimisation sans contrainte

E.1.1 Descente de gradient

E.1.1.1 Pour minimiser une fonction d’une seule variable

À partir d’un point x\in\mathbb{R} quelconque, la dérivée f'(x) donne toute l’information nécessaire pour minimiser la fonction f(x) :

  • f'(x) > 0 indique que la fonction est croissante \Rightarrow il faut reculer pour descendre ;
  • f'(x) < 0 indique que la fonction décroissante \Rightarrow il faut avancer pour descendre ;
  • f'(x) = 0 indique un point critique (minimum ou maximum).

Ainsi, l’algorithme suivant permet de converger vers la solution x^* = \arg\min_{x\in\mathbb{R}} f(x) : x \leftarrow x - \mu f'(x) \qquad \text{tant que } f'(x)\neq 0 où \mu \in(0,1] est un paramètre réglant la taille du pas effectué dans la direction opposée à la dérivée.

Cependant, la convergence n’est garantie que si \mu est choisi suffisamment petit, comme illustré dans l’exemple ci-dessous.

Exemple qui ne convergence pas avec mu=1

Soit f(x) = 1 + x^2, de dérivée \frac{\text{d} f(x)}{\text{d} dx} = 2x.

Si l’algorithme est initialisé à x=4, alors \frac{\text{d} f(x)}{\text{d} x} = 8, ce qui amène pour \mu=1 à x\leftarrow 4 - 8 = -4 et à \frac{\text{d} f(x)}{\text{d} x} = -8. Les itérations suivantes alternent donc entre x=4 et x=-4 indéfiniment.

def f(x):
    return 1 + x**2

def df_dx(x):
    return 2 * x

# initialisation 
x = 4
print(f"x = {x:.5f}, f(x) = {f(x):.5f}, df_df(x) = {df_dx(x):.5f}")

# taille du pas
mu = 0.7

while abs(df_dx(x)) > 1e-3:
    x -= mu * df_dx(x)
    print(f"x = {x:.5f}, f(x) = {f(x):.5f}, df_df(x) = {df_dx(x):.5f}")
x = 4.00000, f(x) = 17.00000, df_df(x) = 8.00000
x = -1.60000, f(x) = 3.56000, df_df(x) = -3.20000
x = 0.64000, f(x) = 1.40960, df_df(x) = 1.28000
x = -0.25600, f(x) = 1.06554, df_df(x) = -0.51200
x = 0.10240, f(x) = 1.01049, df_df(x) = 0.20480
x = -0.04096, f(x) = 1.00168, df_df(x) = -0.08192
x = 0.01638, f(x) = 1.00027, df_df(x) = 0.03277
x = -0.00655, f(x) = 1.00004, df_df(x) = -0.01311
x = 0.00262, f(x) = 1.00001, df_df(x) = 0.00524
x = -0.00105, f(x) = 1.00000, df_df(x) = -0.00210
x = 0.00042, f(x) = 1.00000, df_df(x) = 0.00084

x = 4.00000, f(x) = 17.00000, df_df(x) = 8.00000
x = -3.20000, f(x) = 11.24000, df_df(x) = -6.40000
x = 2.56000, f(x) = 7.55360, df_df(x) = 5.12000
x = -2.04800, f(x) = 5.19430, df_df(x) = -4.09600
x = 1.63840, f(x) = 3.68435, df_df(x) = 3.27680
x = -1.31072, f(x) = 2.71799, df_df(x) = -2.62144
x = 1.04858, f(x) = 2.09951, df_df(x) = 2.09715
x = -0.83886, f(x) = 1.70369, df_df(x) = -1.67772
x = 0.67109, f(x) = 1.45036, df_df(x) = 1.34218
x = -0.53687, f(x) = 1.28823, df_df(x) = -1.07374
x = 0.42950, f(x) = 1.18447, df_df(x) = 0.85899
x = -0.34360, f(x) = 1.11806, df_df(x) = -0.68719
x = 0.27488, f(x) = 1.07556, df_df(x) = 0.54976
x = -0.21990, f(x) = 1.04836, df_df(x) = -0.43980
x = 0.17592, f(x) = 1.03095, df_df(x) = 0.35184
x = -0.14074, f(x) = 1.01981, df_df(x) = -0.28147
x = 0.11259, f(x) = 1.01268, df_df(x) = 0.22518
x = -0.09007, f(x) = 1.00811, df_df(x) = -0.18014
x = 0.07206, f(x) = 1.00519, df_df(x) = 0.14412
x = -0.05765, f(x) = 1.00332, df_df(x) = -0.11529
x = 0.04612, f(x) = 1.00213, df_df(x) = 0.09223
x = -0.03689, f(x) = 1.00136, df_df(x) = -0.07379
x = 0.02951, f(x) = 1.00087, df_df(x) = 0.05903
x = -0.02361, f(x) = 1.00056, df_df(x) = -0.04722
x = 0.01889, f(x) = 1.00036, df_df(x) = 0.03778
x = -0.01511, f(x) = 1.00023, df_df(x) = -0.03022
x = 0.01209, f(x) = 1.00015, df_df(x) = 0.02418
x = -0.00967, f(x) = 1.00009, df_df(x) = -0.01934
x = 0.00774, f(x) = 1.00006, df_df(x) = 0.01547
x = -0.00619, f(x) = 1.00004, df_df(x) = -0.01238
x = 0.00495, f(x) = 1.00002, df_df(x) = 0.00990
x = -0.00396, f(x) = 1.00002, df_df(x) = -0.00792
x = 0.00317, f(x) = 1.00001, df_df(x) = 0.00634
x = -0.00254, f(x) = 1.00001, df_df(x) = -0.00507
x = 0.00203, f(x) = 1.00000, df_df(x) = 0.00406
x = -0.00162, f(x) = 1.00000, df_df(x) = -0.00325
x = 0.00130, f(x) = 1.00000, df_df(x) = 0.00260
x = -0.00104, f(x) = 1.00000, df_df(x) = -0.00208
x = 0.00083, f(x) = 1.00000, df_df(x) = 0.00166
x = -0.00066, f(x) = 1.00000, df_df(x) = -0.00133
x = 0.00053, f(x) = 1.00000, df_df(x) = 0.00106
x = -0.00043, f(x) = 1.00000, df_df(x) = -0.00085

x = 4.00000, f(x) = 17.00000, df_df(x) = 8.00000
x = 3.20000, f(x) = 11.24000, df_df(x) = 6.40000
x = 2.56000, f(x) = 7.55360, df_df(x) = 5.12000
x = 2.04800, f(x) = 5.19430, df_df(x) = 4.09600
x = 1.63840, f(x) = 3.68435, df_df(x) = 3.27680
x = 1.31072, f(x) = 2.71799, df_df(x) = 2.62144
x = 1.04858, f(x) = 2.09951, df_df(x) = 2.09715
x = 0.83886, f(x) = 1.70369, df_df(x) = 1.67772
x = 0.67109, f(x) = 1.45036, df_df(x) = 1.34218
x = 0.53687, f(x) = 1.28823, df_df(x) = 1.07374
x = 0.42950, f(x) = 1.18447, df_df(x) = 0.85899
x = 0.34360, f(x) = 1.11806, df_df(x) = 0.68719
x = 0.27488, f(x) = 1.07556, df_df(x) = 0.54976
x = 0.21990, f(x) = 1.04836, df_df(x) = 0.43980
x = 0.17592, f(x) = 1.03095, df_df(x) = 0.35184
x = 0.14074, f(x) = 1.01981, df_df(x) = 0.28147
x = 0.11259, f(x) = 1.01268, df_df(x) = 0.22518
x = 0.09007, f(x) = 1.00811, df_df(x) = 0.18014
x = 0.07206, f(x) = 1.00519, df_df(x) = 0.14412
x = 0.05765, f(x) = 1.00332, df_df(x) = 0.11529
x = 0.04612, f(x) = 1.00213, df_df(x) = 0.09223
x = 0.03689, f(x) = 1.00136, df_df(x) = 0.07379
x = 0.02951, f(x) = 1.00087, df_df(x) = 0.05903
x = 0.02361, f(x) = 1.00056, df_df(x) = 0.04722
x = 0.01889, f(x) = 1.00036, df_df(x) = 0.03778
x = 0.01511, f(x) = 1.00023, df_df(x) = 0.03022
x = 0.01209, f(x) = 1.00015, df_df(x) = 0.02418
x = 0.00967, f(x) = 1.00009, df_df(x) = 0.01934
x = 0.00774, f(x) = 1.00006, df_df(x) = 0.01547
x = 0.00619, f(x) = 1.00004, df_df(x) = 0.01238
x = 0.00495, f(x) = 1.00002, df_df(x) = 0.00990
x = 0.00396, f(x) = 1.00002, df_df(x) = 0.00792
x = 0.00317, f(x) = 1.00001, df_df(x) = 0.00634
x = 0.00254, f(x) = 1.00001, df_df(x) = 0.00507
x = 0.00203, f(x) = 1.00000, df_df(x) = 0.00406
x = 0.00162, f(x) = 1.00000, df_df(x) = 0.00325
x = 0.00130, f(x) = 1.00000, df_df(x) = 0.00260
x = 0.00104, f(x) = 1.00000, df_df(x) = 0.00208
x = 0.00083, f(x) = 1.00000, df_df(x) = 0.00166
x = 0.00066, f(x) = 1.00000, df_df(x) = 0.00133
x = 0.00053, f(x) = 1.00000, df_df(x) = 0.00106
x = 0.00043, f(x) = 1.00000, df_df(x) = 0.00085

E.1.1.2 Pour minimiser une fonction de plusieurs variables

À partir d’un point \boldsymbol{x}\in\mathbb{R}^n quelconque, le gradient donne toute l’information nécessaire pour minimiser la fonction, car le gradient \frac{\text{d} f(\boldsymbol{x})}{\text{d} \boldsymbol{x}} correspond à la direction de la plus grande pente. Ainsi, la direction opposée au gradient indique la plus grande pente descendante et l’algorithme \boldsymbol{x} \leftarrow \boldsymbol{x} - \mu \frac{\text{d} f(\boldsymbol{x})}{\text{d} \boldsymbol{x}} \qquad \Leftrightarrow \quad x_k \leftarrow x_k - \mu \frac{\partial f(\boldsymbol{x})}{\partial x_k},\quad k=1,\dots,n converge vers l’optimum à \boldsymbol{x}^*, où le gradient est nul : \frac{\text{d} f(\boldsymbol{x}^*)}{\text{d} \boldsymbol{x}} = \boldsymbol{0}

E.1.2 Optimisation locale vs globale

La descente de gradient permet de se rapporcher d’un minimum de la fonction objectif. Cependant, seule la convergence vers un minimum local est garantie, c’est-à-dire qu’aucun point dans un voisinnage de la solution ne peut être meilleur : \exists \epsilon>0,\ \forall \boldsymbol{x},\ tel\ que\ \|\boldsymbol{x} - \boldsymbol{x}^*\|\leq \epsilon,\quad f(\boldsymbol{x})\geq f(\boldsymbol{x}^*)

Un minimum global localisé en \boldsymbol{x}^* est tel que \forall \boldsymbol{x},\quad f(\boldsymbol{x})\geq f(\boldsymbol{x}^*) et garantie donc qu’aucune autre solution n’est meilleure.

Cas particulier : tous les minima locaux d’une fonction convexe sont aussi des minima globaux (et inversement, tous les maxima locaux d’une fonction concave sont aussi globaux).

E.1.3 Fonctions convexes et concaves

Une fonction f : \mathbb{R}^d\to \mathbb{R} est convexe si, pour tout \boldsymbol{x}\in\mathbb{R}^d, \boldsymbol{x}'\in\mathbb{R}^d, et \lambda\in[0,1], f(\lambda\boldsymbol{x} + (1-\lambda)\boldsymbol{x}') \leq \lambda f(\boldsymbol{x}) + (1-\lambda)f(\boldsymbol{x}') Cela signifie que tout segment entre deux points du graphique de f se situe au-dessus du graphique de f.

Inversement, une fonction f : \mathbb{R}^d\to \mathbb{R} est concave si tout segment entre deux points du graphique de f se situe en-dessous du graphique de f, ou encore, si -f est convexe.

Exemples de fonctions convexes et concaves :

  • les fonctions linéaires ou affines qui sont à la fois convexes et concaves ;
  • les normes, \|\boldsymbol{x}\|_p pour p\geq 1, sont convexes ;
  • la norme d’une fonction linéaire, \|\boldsymbol{A}\boldsymbol{x} + \boldsymbol{b}\|, est convexe ;
  • la somme de deux fonctions convexes est convexe ;
  • le maximum point à point de deux fonctions f_1 et f_2 convexes, f(\boldsymbol{x}) = \max\{f_1(\boldsymbol{x}), f_2(\boldsymbol{x})\}, est convexe ;
  • la racine carrée est concave.

Les fonctions quadratiques sont soit convexe, soit concave.

Plus de détails sur l’optimisation de fonctions convexes peuvent être trouvés dans Boyd et Vandenberghe (2004).

E.1.3.1 Malédiction de la dimension

Le problème des minima locaux peut être résolu en lançant de multiples initialisations à partir d’intialisations différentes. Cependant, le nombre d’initialisations nécessaires croît rapidement avec la dimension d du problème.

Pour le voir, imaginons que le domaine de recherche de la solution soit limité au cube unité : \boldsymbol{x} \in [0,1]^d. Dans ce cas, pour d=1, il suffit de choisir 1/\epsilon initialisations équiréparties entre 0 et 1 pour être sûr de lancer l’optimisation à une distance inférieure à \epsilon de la solution globale, et si le bassin d’attraction de cette solution (l’ensemble des initialisations qui convergent vers elle) est plus large que \epsilon, alors elle sera trouvée. Donc si \epsilon =0.1, il suffit de choisir N=10 initialisations.

Si d=2, alors l’ensemble des initialisations devient une grille en 2D, avec N=1/\epsilon^2 = 100 points. Pour d=3, la grille comprend N=1/\epsilon^3 = 1000 points.

Pour d> 4, les choses sont en fait pires, dans le sens où N=1/\epsilon^d ne suffit plus. En effet, une telle grille garantie uniquement d’avoir une distance 1/\epsilon entre deux coins d’un petit hypercube délimité par la grille. Mais la solution du problème recherchée pourrait se trouver au centre de l’hypercube.

Pour d=1, cela ne change rien. Pour d=2, le centre d’un petit carré de côté \epsilon est à une distance \epsilon\sqrt{2} / 2 < \epsilon des coins, car la diagonale du carré mesure \sqrt{\epsilon^2 + \epsilon^2}.

Pour d=3, la diagonale du cube mesure \sqrt{\epsilon^2 + diagonale(face\ carree)^2} = \sqrt{3\epsilon^2} et la distance devient \epsilon\sqrt{3} / 2, ce qui est encore inférieur à \epsilon. Mais pour d>4, la distance au centre est \epsilon\sqrt{d} / 2 > \epsilon. Il est donc nécessaire de choisir une grille plus fine avec une distance entre deux coins valant 2\epsilon/\sqrt{d}. Ainsi, la distance au centre sera 2\epsilon/\sqrt{d} \times \sqrt{d} / 2 = \epsilon.

Pour d>4, il faut donc N = \left(\frac{\sqrt{d}}{2\epsilon}\right)^d pour garantir une distance maximale de \epsilon entre la solution recherchée et une intialisation. Pour d=10, ce nombre est déjà proche de 10 milliards.

Notons que cette formule est en fait valable pour tout d\geq 1. Par exemple, pour d=1, il aurait suffit de choisir 5 points espacés de 0.2 pour garantir d’avoir une initialisation à une distance maximale de 0.1 de la solution.

E.2 Optimisation sous contraintes

Considérons maintenant le problème d’optimisation soumis à des contraintes suivant \begin{align*} \min_{\boldsymbol{x}\in\mathbb{R}^d}\ & f(\boldsymbol{x})\\ \text{s.c. } & g(\boldsymbol{x}) \geq 0 \end{align*}

TODO…