II. OPTIMISATION SANS CONTRAINTE min f(x) avec x ε R

II.  OPTIMISATION SANS CONTRAINTE

min f(x) avec x ε Rn

– Méthodes de recherche unidimensionnelle

– Méthodes du gradient

– Méthodes des directions conjuguées

– Méthode de Newton et méthode de Levenberg-Marquardt

– Méthodes quasi-Newton

– Méthodes sans calcul du gradient

– Résolution d’équations non linéaires

II.1 Méthodes de recherches unidimensionnelles (1)

II.1.1 Méthode du nombre d’or

II.  OPTIMISATION SANS CONTRAINTE

Hypothèse: f unimodulable sur

<=> ∃ un seul minimisant f

• • • • • •

f(x) f(x) • • • •

• •


Principes de la méthode du nombre d’or

II. OPTIMISATION SANS CONTRAINTE

f(x)

• • •

• • • •

• • • • •



•  Choisir un des points de l’étape précédente :

Principes de la méthode du nombre d’or (suite) •  Répéter



=> Facteur de réduction à chaque itération:

= NOMBRE D’OR

Calcul de la valeur de ρ dans la méthode du nombre d’or:


II.1.2 Méthode des suites de Fibonacci


ρ est variable pour optimiser la convergence • • • •


Sélection optimale des facteurs de réduction:


Si N itérations sont permises :

est la suite de Fibonacci : où


II.1.3 Méthode de Newton


Approximation de f(x) par une forme quadratique autour d’un point :

Minimiser q(x)

=> x =


II.1.3 Méthode de Newton (suite)


Méthode efficace si > 0 ∀ x ⇒ convergence quadratique

f(x)

q(x)

• • • •

q(x)




Par contre la méthode ne converge pas nécessairement si f’’(x) < 0 pour certaines valeurs de x

f(x) g(x)

• •




La méthode de Newton peut être vue comme une méthode de recherche de zéro d’une fonction g(x) si on pose

• •

•

•

g(x)


II.1.4 Méthode de la sécante


La dérivée n’est pas toujours disponible => approximation

Cette méthode amène la dérivée de f(x) à zéro


II.1.4 Méthode de la sécante (suite)


• •

•

•

g(x)

Si f’(x) = g(x) cette méthode trouve la racine de g(x)

•


II.1.5 Méthodes unidirectionnelles « Line search »


= solution d’un problème unidimensionnel

Exemple: méthode de la sécante



Il n’est pas nécessaire de calculer précisément α* si de manière significative

• If faut distinguer 2 cas : f dérivable et f non dérivable

• La recherche de α* se fait souvent en deux étapes: 1. Déterminer un intervalle contenant α* 2. Réduire cet intervalle

II.1.5 Méthodes unidirectionnelles (suite)

!


Déterminer un intervalle contenant α*


1° Trouver un intervalle [a,b] où la pente change de signe

• • • • • •

•

a b

pente

!

II.1.5.1 La fonction f est dérivable Soit une direction de décroissance de f


2° Algorithme de Fletcher


•

• •

A B

pente

α max

pente

α

Conditions de Wolfe-Powell



1.  Utiliser des différences finies au lieu des dérivées. 2.  Méthode du nombre d’or ou des suites de Fibonacci si un

intervalle [0, αmax] a été identifié. 3.  Interpolation quadratique en 3 points avec recherche de minimum:

méthode souvent utilisée (e.g.. MATLAB).

II.1.5.2. La fonction f est non dérivable

II.2 Méthode du Gradient (1)


Indique la direction avec le plus grand taux de décroissance de f au point

=> Algorithme du Gradient:

Soit



II.2.1 Méthode de Cauchy ou méthode de la plus grande pente

• •

•

• •

•

•

Propriétés : 1° 2°



II.2.2 Evaluation du Gradient

Problèmes possibles: * *

*

, mais calcul du ∇f trop complexe

∇f connu, mais nécessite trop de calculs

Si => différences finies:

Si => autres méthodes sans calcul du gradient



II.2.3 Critères d’arrêt

En théorie si En pratique avant car convergence trop lente

Critères :



II.2.4 Convergence

Cas d’une fonction quadratique



II.2.4 Convergence

Cas d’une fonction quadratique (suite)

Convergence linéaire qui dépend du conditionnement de Q



Exemple 1°

=> Convergence en une itération

Exemple 2°

=> 15 itérations

Critère d’arrêt :







Exemple 3°

=> 4 itérations Avec le même critère d’arrêt





II.3 Méthode des directions conjuguées (1)


• Résout les problèmes quadratiques en n itérations • Convergence plus rapide que le gradient

Définition : Directions Q-conjuguées

Soit Les directions sont Q-conjuguées si

et linéairement indépendantes si Q > 0



II.3.1 Algorithme des directions conjuguées

Soit

Soient n directions conjuguées

Propriétés: converge vers

en n itérations

En effet :



II.3.1 Algorithme des directions conjuguées (suite)

Démonstration :

€

∃ n coefficients βi x∗ − x0 = βidii=0

n−1

∑

⇒ dkT Q(x∗ − x0) = βkdk

T Q dk ⇒ βk =dkT Q(x∗ − x0)dkT Q dk

xk = x0 +α0d0 +α1d1 +…+αk−1dk−1xk − x0 = α0d0 +…+αk−1dk−1x∗ − x0 = x∗ − xk + xk − x0⇒ dk

T Q(x∗ − x0) = dkT Q(x∗ − xk ) = −dk

T (Q xk − b) = −dkT∇f (xk )

⇒ βk = −dkT∇f (xk )dkT Q dk

= αk ⇒ xn−1 = x∗



II.3.2 Algorithme du gradient conjugué

Soit

Principe : Construire les directions conjuguées au fur et à mesure



II.3.2 Algorithme du gradient conjugué (suite)

Algorithme: choisir

Si => arrêt

Propriétés: converge vers en n itérations



Exemple 1°



Exemple 1° (suite)



Exemple 2°



II.3.3 Gradients conjugués pour les fonctions non quadratiques

Le Hessien de f(x) ≠ Q => éliminer Q dans l’algorithme

Par recherche unidirectionnelle

A. Formule de Hestenes-Stiefel

NB:




C. Formule de Fletcher-Reeves

B. Formule de Polak-Ribière




Algorithme de Fletcher-Reeves: choisir

Convergence après n itérations => re-initialiser de temps en temps

II.4 Méthode de Newton (1)


=> une seule itération !

Exemple:

Soit

II.4 Méthode de Newton (2)


Calcul du Hessien très lourd ! Propriété locale

=> Mauvaise direction :

fonction pas vraiment quadratique

=> Introduire optimisation unidirectionnelle

!

II.5 Algorithme de Levenberg-Marquardt


Combiner Gradient et Newton

terme de régularisation tel que

Algorithme:

€

soit x0 ν0 ∇f (x0) H0(x0)1° Hk = H(xk ) +νkI2° si Hk / > 0⇒νk = c0νk ⇒1°

3° xk+1 = xk −αkHk−1∇f (xk )

4° calculer f (xk+1)5° si f (xk+1) ≥ f (xk ) νk = c1νk xk+1 = xk ⇒1°

si non νk+1 =νkc2

et k = k +1 ⇒1°

II.6 Méthodes Quasi-Newton (1)


est remplacé par une approximation

Propriété

Condition quasi-Newton



II.6.1 Formule de correction de rang 1

=> Formule de correction de rang 2 :



II.6.2 Formule de correction de rang 2

Propriétés : * si f(x) est quadratique => convergence en n itérations * si f(x) quelconque

A. Davidson-Fletcher-Powell (DFP)

B. Broyden-Fletcher-Goldfarb-Shanno (BFGS)

=> Propriété de descente garantie !

II.7 Méthodes sans calcul du gradient (1)


1° Minimisation par rapport à 2° Minimisation par rapport à …

Méthode simple mais ne converge pas toujours

• P

Convergence ralentie en P

II.7.1 Méthode univariable alternée

II.7 Méthode sans calcul du gradient (2)


Définition : Forme géométrique avec n+1 sommets dans un espace à n dimensions = simplexe

Simplexe régulier si les sont équidistants

n=2 n=3

Principe de l’algorithme :

Déplacement constitué de réflexions, expansions et contractions

II.7.2 Méthode du simplexe (Nelder-Mead)



A. Réflexion

n=2 n=3

• •

•

•

•

• •

•

• •

•

•



A. Réflexion

Cycles limites possibles

⇒  *Sélectionner autre *Contraction

•

•

•

•

!



B. Contraction

• •

•

• •

•

• •

• •

•



C. Expansion

• •

•

•

•

•

II.8 Sommes de carrés – Equations non linéaires (1)


II.8.1 Moindres carrés non linéaires



II.8.1.1 Méthode de Gauss-Newton

Méthode de Newton :

Gauss- Newton :

Convergence quadratique si et non singulier

Problèmes si J(x) singulier ou mal conditionné



II.8.1.2 Algorithme de Levenberg-Marquardt

II.8.1.3 Méthodes quasi-Newton

Problèmes



II.8.2 Résolution d’équations non-linéaires

Méthode de Newton-Raphson : Approximation du premier ordre

€

⇒ xk+1 = xk − J(xk )−1F(xk ) J(x) =

∇f1(x)T

∇fn (x)T

⎡

⎣

⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ≠ 0

ó Gauss-Newton pour minimiser

∃ Autres méthodes par intervalles

⇒ Utilisation possible des méthodes de moindres carrés non linéaires

Méthode locale avec J(x) non singulier

Objectif:

!

II.9 Exemple comparatif (1)


Fonction de Rosenbrock:

Méthode # itérations # évaluations

Gradient Simplexe Gauss-Newton Levenberg-Marquardt Quasi-Newton (DFP) Quasi-Newton (BFGS)

68 + arrêt 109 13 21 25 25

302 + arrêt 201 55 92 109 105



Méthode du Gradient



Méthode du Simplexe



Méthode de Gauss-Newton



Méthode de Levenberg-Marquardt



Méthode Quasi-Newton (DFP)



Méthode Quasi-Newton (BFGS)

Documents

II. OPTIMISATION SANS CONTRAINTE min f(x) avec x ε R