II.

OPTIMISATION SANS CONTRAINTE

min f(x) avec x Rn

Mthodes de recherche unidimensionnelle

Mthodes du gradient
Mthodes des directions conjugues
Mthode de Newton et mthode de Levenberg-Marquardt
Mthodes quasi-Newton
Mthodes sans calcul du gradient
Rsolution dquations non linaires
 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (1)
II.1.1 Mthode du nombre dor

Hypothse: f unimodulable sur

<=> un seul minimisant f

f(x)

f(x)

II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (2)
Principes de la mthode du nombre dor

f(x)

II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (3)
Principes de la mthode du nombre dor (suite)
Rpter
Choisir un des points de ltape prcdente :
II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (4)
Calcul de la valeur de dans la mthode du nombre dor:

=> Facteur de rduction chaque itration:

= NOMBRE DOR
 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (5)
II.1.2 Mthode des suites de Fibonacci
est variable pour optimiser la convergence
II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (6)
Slection optimale des facteurs de rduction:
Si N itrations sont permises :

o est la suite de Fibonacci :

II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (7)
II.1.3 Mthode de Newton

Approximation de f(x) par une forme quadratique autour

dun point :

Minimiser q(x)

=> x =
II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (8)
II.1.3 Mthode de Newton (suite)

Mthode efficace si >0 x

convergence quadratique

q(x)
q(x)
f(x)


II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (9)
II.1.3 Mthode de Newton (suite)

Par contre la mthode ne converge pas

ncessairement si f(x) < 0 pour certaines valeurs de x

f(x)
g(x)
II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (10)
II.1.3 Mthode de Newton (suite)

La mthode de Newton peut tre vue comme une mthode

de recherche de zro dune fonction g(x) si on pose

g(x)

II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (11)
II.1.4 Mthode de la scante

La drive nest pas toujours disponible

=> approximation

Cette mthode amne la drive de f(x) zro

II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (12)
II.1.4 Mthode de la scante (suite)

Si f(x) = g(x) cette mthode trouve la racine de g(x)

g(x)

 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (13)
II.1.5 Mthodes unidirectionnelles Line search

= solution dun problme unidimensionnel

Exemple: mthode de la scante

 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (14)
II.1.5 Mthodes unidirectionnelles (suite)

Il nest pas ncessaire de calculer prcisment *

! si de manire significative

If faut distinguer 2 cas : f drivable et f non drivable

La recherche de * se fait souvent en deux tapes:

1. Dterminer un intervalle contenant *
2. Rduire cet intervalle
 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (15)
II.1.5.1 La fonction f est drivable
Soit une direction de dcroissance de f

Dterminer un intervalle contenant *

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

pente

a b

!
 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (16)

2 Algorithme de Fletcher

pente

pente

A B max

Conditions
de Wolfe-Powell
 II. OPTIMISATION SANS CONTRAINTE
II.1 Mthodes de recherches unidimensionnelles (17)
II.1.5.2. La fonction f est non drivable

1. Utiliser des diffrences finies au lieu des drives.

2. Mthode du nombre dor ou des suites de Fibonacci si un
intervalle [0, max] a t identifi.
3. Interpolation quadratique en 3 points avec recherche de minimum:
mthode souvent utilise (e.g.. MATLAB).
II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (1)

Soit

Indique la direction avec le plus grand taux de

dcroissance de f au point

=> Algorithme du Gradient:

 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (2)
II.2.1 Mthode de Cauchy ou mthode de la plus grande pente

Proprits :
1
2
 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (3)
II.2.2 Evaluation du Gradient
Problmes possibles: * , mais calcul du f trop complexe

* f connu, mais ncessite trop de calculs

*
Si => diffrences finies:

Si => autres mthodes sans calcul du gradient

 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (4)
II.2.3 Critres darrt
En thorie si
En pratique avant car convergence trop lente

Critres :
 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (5)
II.2.4 Convergence

Cas dune fonction quadratique

 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (6)
II.2.4 Convergence

Cas dune fonction quadratique (suite)

Convergence linaire qui dpend du conditionnement de Q

II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (7)

Exemple 1

=> Convergence en une itration

Exemple 2

Critre darrt :

=> 15 itrations
II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (8)
II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (9)
II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (10)

Exemple 3

=> 4 itrations Avec le mme critre darrt

II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (11)
II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode du Gradient (12)
 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (1)
Rsout les problmes quadratiques en n itrations
Convergence plus rapide que le gradient

Dfinition : Directions Q-conjugues

Soit
Les directions sont Q-conjugues si

et linairement indpendantes si Q > 0

 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (2)
II.3.1 Algorithme des directions conjugues
Soit

Soient n directions conjugues

En effet :

Proprits:
converge vers
en n itrations
 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (3)
II.3.1 Algorithme des directions conjugues (suite)
Dmonstration : n 1

n coefficients i x x 0 = i di
i=0

T T dkT Q(x x 0 )
d Q(x x 0 ) = d Q dk
k k k k =
dkT Q dk
x k = x 0 + 0 d0 + 1d1 + + k 1dk 1
x k x 0 = 0 d0 + + k 1dk 1
x x0 = x xk + xk x0
dkT Q(x x 0 ) = dkT Q(x x k ) = dkT (Q x k b) = dkT f (x k )
dkT f (x k )
k = T = k x n 1 = x
dk Q dk
 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (4)
II.3.2 Algorithme du gradient conjugu
Soit

Principe : Construire les directions conjugues au fur et mesure

 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (5)
II.3.2 Algorithme du gradient conjugu (suite)

Algorithme: choisir

Si => arrt

Proprits: converge vers

en n itrations
II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (6)
Exemple 1
II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (7)
Exemple 1 (suite)
 II. OPTIMISATION SANS CONTRAINTE
II.2 Mthode des directions conjugues (8)
Exemple 2
II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (9)
II.3.3 Gradients conjugus pour les fonctions non quadratiques

Le Hessien de f(x) Q => liminer Q dans lalgorithme

Par recherche unidirectionnelle

A. Formule de Hestenes-Stiefel

NB:
II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (10)
II.3.3 Gradients conjugus pour les fonctions non quadratiques
B. Formule de Polak-Ribire

C. Formule de Fletcher-Reeves
 II. OPTIMISATION SANS CONTRAINTE
II.3 Mthode des directions conjugues (11)
II.3.3 Gradients conjugus pour les fonctions non quadratiques
Algorithme de Fletcher-Reeves: choisir

Convergence aprs n itrations

=> re-initialiser de temps en temps
II. OPTIMISATION SANS CONTRAINTE
II.4 Mthode de Newton (1)
Soit

Exemple:

=> une seule itration !

II. OPTIMISATION SANS CONTRAINTE
II.4 Mthode de Newton (2)

! fonction pas vraiment quadratique

=> Mauvaise direction :

=> Introduire optimisation unidirectionnelle

Calcul du Hessien trs lourd !

Proprit locale
II. OPTIMISATION SANS CONTRAINTE
II.5 Algorithme de Levenberg-Marquardt
Combiner Gradient et Newton

terme de rgularisation tel que

Algorithme: soit x 0 0 f (x 0 ) H 0 (x 0 )
1 H k = H(x k ) + k I
2 si H k >/ 0 k = c 0 k 1
3 x k +1 = x k k H k1f (x k )
4 calculer f (x k +1 )
5 si f (x k +1 ) f (x k ) k = c1 k x k +1 = x k 1
k
si non k +1 = et k = k +1 1
c2
 II. OPTIMISATION SANS CONTRAINTE
II.6 Mthodes Quasi-Newton (1)

est remplac par une approximation

Proprit

Condition quasi-Newton
 II. OPTIMISATION SANS CONTRAINTE
II.6 Mthodes Quasi-Newton (2)
II.6.1 Formule de correction de rang 1

=> Formule de correction de rang 2 :

II. OPTIMISATION SANS CONTRAINTE
II.6 Mthodes Quasi-Newton (3)
II.6.2 Formule de correction de rang 2
A. Davidson-Fletcher-Powell (DFP)

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

Proprits :
* si f(x) est quadratique => convergence en n itrations
* si f(x) quelconque
=> Proprit de descente garantie !
 II. OPTIMISATION SANS CONTRAINTE
II.7 Mthodes sans calcul du gradient (1)
II.7.1 Mthode univariable alterne

1 Minimisation par rapport

2 Minimisation par rapport

Mthode simple mais
ne converge pas toujours

P
Convergence ralentie en P
 II. OPTIMISATION SANS CONTRAINTE
II.7 Mthode sans calcul du gradient (2)
II.7.2 Mthode du simplexe (Nelder-Mead)
Dfinition : Forme gomtrique avec n+1 sommets dans
un espace n dimensions = simplexe
n=2 n=3

Simplexe rgulier si les sont quidistants

Principe de lalgorithme :

Dplacement constitu de rflexions, expansions et contractions

II. OPTIMISATION SANS CONTRAINTE
II.7 Mthode sans calcul du gradient (3)
A. Rflexion

n=2
n=3

 II. OPTIMISATION SANS CONTRAINTE
II.7 Mthode sans calcul du gradient (4)
A. Rflexion

! Cycles limites possibles

*Slectionner autre
*Contraction
II. OPTIMISATION SANS CONTRAINTE
II.7 Mthode sans calcul du gradient (5)
B. Contraction

II. OPTIMISATION SANS CONTRAINTE
II.7 Mthode sans calcul du gradient (6)
C. Expansion

II. OPTIMISATION SANS CONTRAINTE
II.8 Sommes de carrs Equations non linaires (1)
II.8.1 Moindres carrs non linaires
II. OPTIMISATION SANS CONTRAINTE
II.8 Sommes de carrs Equations non linaires (2)
II.8.1.1 Mthode de Gauss-Newton

Mthode de Newton :

Gauss- Newton :

Convergence quadratique si et non singulier

Problmes si J(x) singulier ou mal conditionn
 II. OPTIMISATION SANS CONTRAINTE
II.8 Sommes de carrs Equations non linaires (3)
II.8.1.2 Algorithme de Levenberg-Marquardt

Problmes

II.8.1.3 Mthodes quasi-Newton

 II. OPTIMISATION SANS CONTRAINTE
II.8 Sommes de carrs Equations non linaires (4)
II.8.2 Rsolution dquations non-linaires
Objectif:

Mthode de Newton-Raphson : Approximation du premier ordre

f (x)T
1
x k +1 = x k J(x k ) 1 F(x k ) J(x) = 0
f (x)T
n
Gauss-Newton pour minimiser

Utilisation possible des mthodes de moindres carrs non linaires

! Mthode locale avec J(x) non singulier
Autres mthodes par intervalles
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (1)

Fonction de Rosenbrock:

Mthode # itrations # valuations

Gradient 68 + arrt 302 + arrt
Simplexe 109 201
Gauss-Newton 13 55
Levenberg-Marquardt 21 92
Quasi-Newton (DFP) 25 109
Quasi-Newton (BFGS) 25 105
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (2)

Mthode du Gradient
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (3)

Mthode du Simplexe
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (4)

Mthode de Gauss-Newton
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (5)

Mthode de Levenberg-Marquardt
II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (6)

Mthode Quasi-Newton (DFP)

II. OPTIMISATION SANS CONTRAINTE
II.9 Exemple comparatif (7)

Mthode Quasi-Newton (BFGS)