1. Formulation du problème d'optimisation

\(\newcommand{\R}{\mathbb R} \newcommand{\ve}{\varepsilon} \renewcommand{\P}{\mathcal P} \DeclareMathOperator{\argmin}{argmin} \) La formulation du problème d'optimisation (non-linéaire) est:

Soient une fonction \(f:\R^n \to \R\) et \(S\) un sous-ensemble (non vide) de \(\R^n\), \(S \subset \R^n\), résoudre

Cela signifie trouver \(x_* \in S\) qui satisfait \(f(x_*) \leq f(y)\) quelque soit \(y \in S\).

Dans ce cours, on propose des méthodes (numériques) pour résoudre ce problème. A priori, il n'y a pas unicité de la solution. En général, on ne peut trouver des minimums globaux qu'à une précision donnée \(\varepsilon>0\). En toute généralité, il est impossible résoudre ce problème pour \(f\) ou \(S\) quelconques, même numériquement.

De plus, les méthodes développées s'appliquent à des classes de fonctions (et non à une fonction en particulier...). On cherche donc à évaluer la performance de la m'ethode sur une classe de fonctions.

Considérons par exemple le cas \(S = [0,1]^n\), et \(C:= \{ f:S \to \R \, \, \big| \,\, f \text{ Lipschitzienne de constante } L\}\), i.e. \(f:S \to \R\) appartient à \(C\) si \(|f(x) - f(y)| \leq \, L \, |x-y|\) pour tout \(x,y \in S\).

On considère la méthode d'optimisation suivante:

Afin d'évaluer la performance de cette méthode, on définit la complexité de cette méthode comme le nombre d'évaluations de la fonction nécessaires pour terminer dans le pire des cas. Terminer signifie trouver \(x_*\) tel que \(f(x_*) \leq \min f + \ve\).

  1. [TD] Quelle est la complexité de la méthode pour \(\varepsilon>0\) donné?
  2. [TD] Généraliser en dimension \(n\) quelconque pour \(S = [0,1]^n\).
  3. [TD] Peut-on espérer localiser un minimimum global à \(\ve\) près?
  4. [TP] Implémenter cette méthode en dimension \(1\) et l'appliquer sur \(x \to (x-\frac{1}{\sqrt{2}})^2\) sur \([0,1]\).

Pour la question 3, définir une fonction MethodeSimple qui prend \(\varepsilon\) en paramètre et la fonction \(f\) à optimiser. MethodeSimple retourne le minimum trouvé \(x_*\) et sa valeur \(f(x_*)\).

In []:
def MethodeSimple(f,p):
    # f est la fonction et p le parametre reel.
    # code a ecrire
    #.....
    #.....
    return (0,f(0))

2. Approximation numérique des dérivées

Soit \(f:\R \mapsto \R\) une fonction dérivable. Si \(f\) admet un extremum local en un point \(a \in \R\), alors \(f'(a)=0\). [en donner une preuve]

Cette condition nécessaire d'optimalité peut être vérifiée numériquement en approximant la dérivée au point considéré par une méthode de différence finies:

On considère une fonction \(f:\R^n \mapsto \R\) de classe \(C^1\).

  1. [TD] Justifier l'approximation
  2. [TD] Quel est l'ordre de cette approximation?
  3. [TD] On suppose la fonction \(f\) de classe \(C^2\). Etudier le cas de la différence finie centrée:
  4. [TD] Comparer les ordres d'approximation obtenus.

On s'intéresse au choix numérique de la valeur du paramètre \(\ve\). On rappelle que Python ou Matlab représente les réels sous la forme de nombre à virgule flottante: en double précision, \(64\) bits sont alloués à un nombre donné: \(1\) bit est alloué au signe, \(11\) à l'exposant et les \(52\) bits restant sont alloués à la mantisse (chiffres significatifs). La conséquence directe de cette approximation est que les calculs sont ne sont pas nécessairement exacts. Par exemple, \(1.0e30+1-1.0e30\) donne un résultat nul.

  1. [TD] Pour choisir \(\ve\), il faut prendre en compte cet approximation: théoriquement, il faut faire tendre \(\ve\) vers \(0\). Pourquoi choisir \(\ve\) 2. On suppose que l'évaluation numérique de \(f\) est donnée par \(\hat{f}\) vérifiant \(\| f(x) - \hat{f}(x)\| \leq \eta \| f \|_\infty\) avec \(\eta\) de l'ordre de \(10^{-p}\).En utilisant une inégalité triangulaire, comparer la différence finie (Formule 1) appliquée à \(\hat{f}\) et la valeur de la dérivée de \(f\) au point \(x\).
  2. [TD] En minimisant le majorant précédent en \(\ve\), proposer une valeur de \(\ve\) offrant un bon compromis.
  3. [TD] Mêmes questions (2 et 3) pour l'approximation par différences finies centrées (Formule 2).
On considère la fonction \(f:\R^n \mapsto \R\) définie par

et le point \(a = [i]_{i=1,\ldots,n}\).

  1. [TD] Calculer analytiquement la dérivée partielle de \(f\) par rapport à \(x_1\).
  2. [TP] Implémenter deux fonctions DifferencesFinies et DifferencesFiniesCentrees qui prend une fonction \(f:\R^n \to \R\) et \(\ve\) et qui renvoie le gradient de \(f\), c'est à dire le vecteur \((\partial_1 f(x),\ldots,\partial_n f(x))\).
  3. [TP] Utiliser la différence finie à droite (Formule 1) pour calculer une valeur approchée de la dérivée partielle par rapport à \(x_1\) au point \(a\), pour différentes valeurs de \(n\) et différentes valeurs de \(\ve\). On choisira \(n=10^i\) pour \(3\leq i \leq 8\).
  4. [TP] Etudier le cas de la différence finie centrée:
  5. [TP] Comparer et discuter les approximations obtenues. Comment expliquer ces résultats?
Attention, ce code d'estimation numérique des dérivées sera probablement utilisé dans les prochains TP.

3. Optimisation en dimension 1

Définition: Une fonction \(f: [0,T] \mapsto \R\) est dite unimodale sur \([0,T]\) s'il existe un minimum strict \(t^* \in ]0,T[\) tel que \(f\) est strictement décroissante sur \([0,t^*]\) et strictement croissante sur \([t^*,T]\).

La minimisation en dimension 1 intervient dans les algorithmes de descente pour la minimisation de fonctionnelles sur \(\R^n\). Lorsque le minimum est recherché exactement, on appelle ces méthodes. En pratique, Il est intéressant de proposer des méthodes faisant seulement appel à l'évaluation de la fonction à minimiser. La méthode la plus simple pour localiser le minimum à \(M \ve\) près d'une fonction lipschitzienne de constante \(M\), \(f:[a,b] \to \R\) est d'évaluer \(f\) sur une grille de pas \(\ve\) (voir l'exercice 1). Vous pourrez l'utiliser en TP pour confirmer les résultats des autres méthodes. On rappelle que les méthodes sont souvent basée sur la méthode générique de dichotomie suivante:

Méthode de dichotomie:

  1. [TD] Montrer que la recherche du triplet de point dans l'algorithme précédent termine pour une fonction unimodale.
  2. [TD] Proposer une méthode de réduction du triplet basée sur le polyn^ome d'interpolation de Lagrange pour ce triplet de point.
  3. [TD] Montrer la convergence de la méthode pour une fonction unimodale \(C^1\) dont la dérivée s'annule uniquement au minimum.
  4. [TD - optionnel] Montrer que l'ordre de convergence est super-linéraire si cet algorithme converge si on suppose la fonction suffisamment régulière.
  5. [TP] Implémenter l'algorithme en faisant bien attention aux cas de boucles infinies.

4. Applications

Trajectoire optimale:

Un véhicule doit se rendre d'un point \(a \in \R^2\) à un point \(b \in \R^2\) en un minimum de temps. Sa vitesse est \(v_1\) dans un domaine \(D\) convexe contenant \(a\) et \(v_2>v_1\) sur \(D^c\) le complémentaire de \(D\). On suppose que \(D= \left\{ (x,y) \, | \, y \leq f(x) \right\}\) pour \(f\) une fonction concave que vous choisirez.

  1. [TD] Formuler ce probléme d'optimisation et le résoudre pour retrouver la loi de Snell dans le cas d'une fonction \(f\) constante.
  2. [TP] Implémenter une méthode d'optimisation simple pour trouver numériquement l'optimum et tracer la trajectoire optimale pour différentes valeurs de \(v_1\) et \(v_2\).

Séparation de sources:

On cherche à appliquer les algorithmes codés précedemment au problème de la séparation de sources dans le cas particulier de deux enregistrements. Télécharger les données micro1_1 et micro1_2 sur http://www.ceremade.dauphine.fr/~vialard/ et le fichier python OutilsSons.py. Pour charger les fichiers son dans python, on utlisera le module scipy scipy.io.wavfile. Pour chaque signal \(D_i\), soustraire la moyenne et normaliser par la déviation standard. On notera \(E[X]\) la moyenne du vecteur \(X\).

  1. [TD] On définit la fonction \(f: \R^2 \to \R\) par \((x,y) \to E[(xD_1 + yD_2)^4]\). Comment se ramener un problème d'optimisation unidimensionnel pour minimiser \(f\) sous la contrainte (*) \(x^2 + 2c\,xy + y^2 =1\) avec \(c=E[D_1D_2]\)?
  2. [TP] Tracer la fonction unidimensionnelle obtenue.
  3. []TP Utiliser une méthode d'optimisation implémentée précédemment et écouter le signal optimal obtenu pour l'optimum \((x_0,y_0)\) ainsi que le signal associé à l'orthogonal de \((x_0,y_0)\) pour la forme quadratique définissant la contrainte (*).

Méthode de la section dorée:

  1. [TP] Implémenter la méthode de la section dorée.
  2. [TP] Comparer sur différents exemples la robustesse des deux méthodes unidimensionnelles implémentées (interpolation quadratique et section dorée).
  3. [TP] Proposer un algorithme plus robuste profitant de la convergence superlinéaire de l'algorithme d'interpolation quadratique.
Le code de la méthode de la section dorée pourra être réutilisé dans les autres TP.
In []: