TP méthode de minimisation multi-dimensionnelle

12.2. TP méthode de minimisation multi-dimensionnelle#

Marc Buffat Dpt mécanique, UCB Lyon 1 Minimisation 2D

%matplotlib inline
#algèbre linéaire
import numpy as np
import sympy as sp
import time
#représentation des résultats
import matplotlib.pyplot as plt
from IPython.display import display,Markdown
def printmd(text):
    display(Markdown(text))
plt.rc('font', family='serif', size='18')

from validation.validation import info_etudiant, bib_validation
def printmd(string):
    display(Markdown(string))
# test si numero étudiant spécifier
try: NUMERO_ETUDIANT
except NameError: NUMERO_ETUDIANT = None 
if type(NUMERO_ETUDIANT) is not int :
    printmd("**ERREUR:** numéro d'étudiant non spécifié!!!")
    NOM,PRENOM,NUMERO_ETUDIANT=info_etudiant()
    #raise AssertionError("NUMERO_ETUDIANT non défini")
# parametres spécifiques
_uid_    = NUMERO_ETUDIANT
np.random.seed(_uid_)
printmd("**Login étudiant {} {} uid={}**".format(NOM,PRENOM,_uid_))
# fonctionnelle a minimiser
bib_validation('cours','IntroIA')
from Fonctionnelle import Fonctionnelle
J = Fonctionnelle(_uid_)
printmd("**Fonctionnelle J à minimiser**")
J.info()

ERREUR: numéro d’étudiant non spécifié!!!

Login étudiant Marc BUFFAT uid=137764122

Fonctionnelle J à minimiser

Fonctionnelle J(X) 
dimension de X : 43
minimum   de J : -1.7692176662626187
pour ||X|| < 1.0

12.2.1. Objectifs#

Trouver le vecteur X minimisant la fonction J(X).

Cette fonction J() est implémentée en Python comme un objet (instance de classe):

  • J : nom de l’objet

  • J.dim() : dimension de X, i.e. le nombre de variables dont J dépend

  • J(X) : calcul la valeur de J pour un vecteur X de dimension J.dim()

  • J.grad(X) : calcul le gradient de J en X

  • J.err(X) : calcul la norme de l’erreur ||X-Xe|| où Xe minimise J(X)

  • J.min() : calcul le minimum de J

12.2.2. Minimisation 1D#

Etude de la minimisation de \(J(\mathbf{X})\) dans une direction \(\mathbf{D}\) fixée

On choisit un vecteur \(D\) (imposé), et on cherche à minimiser \(J(\alpha \mathbf{D})\)

Dans les cellules suivantes:

  • calculer \(J(\alpha \mathbf{D})\) pour des valeurs de \(\alpha\) entre -2 et 2

  • tracer la fonction \(J(\alpha)\)

# calcul variation dans une direction D
D = np.zeros(J.dim())
D[NUMERO_ETUDIANT % J.dim()] = 1
Alpha = None
JAlpha = None

### BEGIN SOLUTION
### END SOLUTION

12.2.2.1. Minimisation 1D#

Principe de la méthode de dichotomie pour la minimisation

On considère une fonction continue \(f(x)\) sur un intervalle \([a,b]\). On suppose que \(f(x)\) admet un minimum unique sur cet intervalle.

À chaque itération :

  • On choisit deux points proches du milieu :

\(x_1=m−\delta\) , \(x_2=m+\delta\) , avec \(m=(a+b)/2\)

  • On compare \(f(x_1)\) et \(f(x_2)\)

    • Si \(f(x_1) < f(x_2)\) le minimum est à gauche \(\leadsto\) \(b=x_2\)

    • sinon, le minimum est à droite \(\leadsto\) \(a=x_1\)

On répète jusqu’à ce que \(∣b−a∣\) soit petit (tolérance).

Ecrire la fonction python

         MinDichotomie(f, a, b, tol=1e-5, delta=1e-6, max_iter=1000)

qui minimise par dichotomie la fonction 1D \(f(x)\)

Appliquer la fonction avec les paramètres précédents pour calculer la minimisation de \(J(X)\) dans la direction \(D\) précédente.

Comparer pour vérifier avec la solution scipy calculer dans la section suivante.

# fonction MinDichotomie
### BEGIN SOLUTION
### END SOLUTION

# application

### BEGIN SOLUTION
### END SOLUTION

12.2.2.2. Utilisation bibliothèque scipy#

  • utiliser la fonction minimize_scalar de scipy pour calculer le mimimum en \(\alpha\)

  • mettre le resultat dans la variable alpha_min

from scipy.optimize import minimize_scalar

alpha_min = None
### BEGIN SOLUTION
### END SOLUTION

12.2.3. Minimisation Multi-dimensionnel#

12.2.3.2. Minimisation de type gradient#

On choisit comme direction de descente la direction opposée au gradient:

  • \(\vec{d} = -\vec{\nabla} F(X)\)

Application:

  1. appliquer la méthode de gradient pour minimiser \(J(X)\) à partir de \(X=0\)

  2. on utilisera n (dimension de X) itérations de gradients

  3. afficher la solution \(X\) et l’erreur avec \(J.err(X)\) et comparer avec la méthode précédente

# methode de gradient
### BEGIN SOLUTION
### END SOLUTION

12.2.4. Minimisation multi-dimensionelle avec scipy#

utilisation de la bibliothéque scipy

  • fonction minimize (minimisation locale)

    • méthode de gradients exactes: Gradients Conjugués, Newton GC,

    • méthode de gradients approchées: BFGS,

    • line search Powell, Simplex Nelder-Mead

  • optimisation globale

    • simulated annealing

Dans la cellule suivante, définir 2 nouvelles fonctions

  • F(X) qui calcul J(X)

  • Fgrad(X) qui calcule le gradient

on définit des fonctions python car les méthodes de minimisation n’autorisent pas les méthodes de classe

F = None
Fgrad = None
### BEGIN SOLUTION
### END SOLUTION
X0 = np.zeros(J.dim())

12.2.4.1. Méthode par défaut#

pour chacune des méthodes:

  • on calcule la solution obtenue Xe,

  • la valeur de J

  • l’erreur (qui doit etre inférieure à 1.e-5)

Il faut aussi jouer sur les paramètres optionnels de la fonction

from scipy.optimize import minimize

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.2. Méthode de gradient conjugué#

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.3. Méthode de gradient conjugué avec Newton#

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.4. Méthode BFGS (gradient avec calcul d’un gradient stocastique)#

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.5. Algorithme Powell (line search 2D)#

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.6. Simulated annealing#

from scipy.optimize import dual_annealing

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.4.7. Méthode du Simplex (Nelder-Mead)#

Xe = None
### BEGIN SOLUTION
### END SOLUTION

12.2.5. Analyse#

comparaison des méthodes

  • coût

  • précision

Ecrivez votre analyse en markdown

12.2.6. FIN#

Contenu