Université Hassiba Benbouali de Chlef

Faculté de Technologie / Département de Génie des Procédés

Modélisation et Optimisation des Procédés

Optimisation des Procédés _ Optimisation sans contraintes

Master M2 _S3
Génie Chimique
Génie des Procédés Pharmaceutiques

Dr Soumia. KOUADRI MOUSTEFAI 1

 Programme et contenu du module
I.1. Problèmes d’optimisation rencontrés en Génie des procédés.
I.2. Présentation de problème d’optimisation
I.3.Rappel des Concepts Fondamentaux en Optimisation
I.4.Recherche directe monodimensionnelle et multidimensionnelle.
I.5. Approche mathématique de l’optimisation sans contrainte.
I.6. Méthodes de descente pour les problèmes sans contrainte
I.7. Problèmes avec contraintes égalités et avec contraintes inégalités
I.8. Programmation Linéaire
I.9. Simplexe
I.10. Méthode de Lagrange
I.11. Méthode des Pénalités
2
Optimisation sans contraintes
I.4. Méthodes directes mono-variable
Pour que ces Méthodes puissent être employées avec efficacité, il est
nécessaire que, dans l’intervalle étudié, la fonction de réponse soit
unimodale, c’est-à-dire qu’elle présente un seul optimum. Cela est
souvent le cas dans la mesure où l’expérimentateur, compte tenu de son
expérience du phénomène, se place dans une zone relativement peu
éloignée de l’optimum.
Définitions et hypothèses générales
Position du problème
On recherche x* = min f(x) pour x ∈ [a, b] ⊂ R
Définition des méthodes de recherche monodimensionnelle
- Les méthodes monodimensionnelles ou monovariables concernent la
recherche de l’optimum d’une fonction scalaire à une seule variable.
4
Méthodes de recherche directe
- Les méthodes de recherche directe représentent l’ensemble des
méthodes d’optimisation qui permettent, sous certaines hypothèses, de
déterminer l’optimum d’une fonction sans nécessiter le calcul des
dérivées d’ordre 1 ou 2 de cette fonction.
- Les méthodes présentées dans cette partie s‘appliquent à des
intervalles [a, b] où la fonction f est unimodale.
Fonction unimodale
La fonction f est unimodale sur l’intervalle [a, b] si et seulement si :
∀ x1, x2 ∈ [a, b] avec x1 < x2 , on a

x2 < x*  f(x1) > f(x2) a x1 x2 x* b

x1 > x*  f(x1) < f(x2) a x* x1 x2 b

Où x* = Min f(x), x ∈[a, b] 5
Principe de réduction de l’intervalle de recherche

La propriété d’unimodalité permet de réduire l’intervalle de recherche

par comparaion de deux essais. En effet, il est immédiat de constater
que si x1 < x2 : f(x1) > f(x2)  x* ∈ [x1, b]

f(x1) < f(x2)  x* ∈ [a, x2]

Partant de l’intervalle initial [a, b] et en se donnant deux points x1 et x2 ,

on peut réduire l’intervalle initial à l’intervalle [x1, b] ou [a, x2]. La
procédure est ensuite réitérée dans ce nouvel intervalle.
Intervalle d’incertitude : intervalle dans lequel est situé x*

Initialement l’intervalle d’incertitude a pour longueur L0 = b – a

Supposons que l’on ait fait n essais x1, x2, ….,xn. Les points sont
indicés de telle sorte que l’on ait x1 < x2 …. <xn. Soit l’indice k tel que
f(xk) = Min {f(xi)}. 6
La fonction f étant unimodale, on a x* ∈[xk-1, xk+1]. En effet, si on
suppose que x* < xk-1 < xk, f étant unimodale, on a f(xk-1) < f(xk).
Or, f(xk) = Min {f(xi)} < f(xk-1), ce qui contredit l’hypothèse
d’unimodalité. Donc, on a x* ≥ xk-1.
De même, si on suppose que xk < xk+1 < x*, f étant unimodale, on a
f(xk) > f(xk+1); or, f(xk) étant le minimum, ceci contredit également
l’hypothèse d’unimodalité. Donc, x* ≤ xk+1.
Après les n essais, le nouvel intervalle d’incertitude a pour longueur :
Ln(xk) = xk+1 – xk-1.
Une méthode sera d’autant plus efficace que la longueur Ln(xk) sera
d’autant plus faible.
L’objectif des méthodes présentées ci-après consiste à déterminer le
meilleur emplacement à choisir pour les points x1 et x2 de façons à
atteindre l’optimum x* le plus rapidement possible, ce qui caractérise
l’efficacité des méthodes. 7
I.4.1. Méthode du nombre d’Or
La stratégie utilisée dans la méthode nombre d’or consiste à générer
deux points dans l’intervalle de recherche, de telle sorte que l’intervalle
éliminé à chaque essai soit dans la même proportion de longueur de
l’intervalle total. A chaque itération de la procédure, on doit générer un
seul point (sauf à la première itération).
+
a x1 x2 b
2d
La procédure consiste à partager l’intervalle L0 de longueur (b – a) en
02 portions de longueur x et y, de façon à ce que le rapport de la
longueur totale au plus grand segment soit identique au rapport du plus
grand segment au plus petit. On veut assurer que le rapport de réduction
t = Lj-1/Lj soit constant pour tous les essais. 8
En supposant que y > x, on doit avoir :
b–a x+y y
= = B–a y
y y x Soit : =
y b - a-y
Donc : y2 + (b - a)y - (b-a)2 = 0
L’équation admet une seule racine positive :

y=
 1  5 b  a  ≈ 0,618(b – a) ; x + y = (b – a) : x ≈ 0,382 (b – a)
2
 1 5 
Le nombre d’or NO = 2 est appelé «nombre d’or», car il conserve
les proportions. x x
+
a x1 x2 b
Cette relation permet de positionner le point x1 dans l’intervalle [a, b] (le
segment [a, x1] a pour longueur x); le point x2 est ensuite placé de telle
sorte que le segment [x2, b] ait également pour longueur x. En fait x2 ce
déduit de x1 par symétrie par rapport au milieu de l’intervalle [a, b]. 9
On élimine ensuite un des deux points en comparant les valeurs des
fonctions. Les autres points se déduisent à chaque étape de celui qui reste
après réduction, par symétrie par rapport au milieu des nouveaux
intervalles.
Exemple : si l’on suppose que l’on élimine le segment [x2, b], le nouveau
point x3 se déduit de x1 par symétrie par rapport au milieu (noté +) de
l’intervalle [a, x2].
+
a x1 x2 b

a x1 + x3 x2
On a donc après avoir calculé n + 1 points (donc n+1 fois la fonction f),
le facteur de réduction r égal à :

r = (Ln/L0) = Non Ln = Non L0

Cette relation permet de décider à l’avance l’arrêt de la recherche en

fonction de la précision souhaitée sur le résultat. 10
I.4.2. Méthode Dichotomique
On désigne par 2d la distance minimale entre deux points, c’est-à-dire la
distance minimale qui les rend discernables ; cette grandeur est évaluée
en fonction de la précision de la machine utilisée.

Dans cette méthode de recherche, on procède par paire d’essais, en

réduisant à chaque étape l’intervalle d’incertitude par un facteur voisin
de 2. Comme on ne dispose a priori d’aucune information sur la fonction,
on place les deux points de manière symétrique par rapport au milieu de
l’intervalle d’incertitude.
+
a x1 x2 b
2d
L’intervalle d’incertitude résultant de la réduction par deux points aura
pour longueur :
11
 L0 + 2d L0
n = 2 : L1 = = + d
2 2
De même, avec un nombre quelconque n pair de points, on obtient les
longueurs suivantes :

n = 4 : L2 = 1 L1 + d = L0 + d 1  1/2
2 4
1 L0
n = 6 : L3 = L2 + d = + d (1 + 1/2 + 1/4)
2 8

Soit pour n = 2k :
L0
Lk = + d (1 + 1/2 + 1/4 + … 1/2)(n/2 -1) 
2n/2
Soit pour n = 2k + 2 :
L0
Lk +1 = + d (1 + 1/2 + 1/4 + … 1/2)(n/2) 
2(n + 2)/2 12
Ainsi, la formule se démontre facilement par récurrence. Le terme entre
parenthèses est une progression géométrique de raison ½. Donc, après
n = 2k essais, la longueur de l’intervalle d’incertitude est :
Lk = (½)n/2 L0 + 2d (1 - (½)n/2)
Le facteur de réduction r = Lk/L0 est égal à :

r = (½)n/2 + (2d/L0) (1 - (½)n/2 ) ≈ (½)n/2 + (2d /L0)

On remarque que l’efficacité de la méthode diminue quand n

augmente, puisque r diminue régulièrement et tend vers la limite
2d/L0.

De façon approchée (d = 0, on obtient Lk = (1/2)k L0 .

13
I.4.3. Méthodes d’interpolation quadratique (Quasi-Newton)
Principe des méthodes Newtoniennes
On suppose que la fonction f, définie sur [a, b] est de classe C2, à dérivée
seconde positive sur cet intervalle. Dans ce cas, la recherche d’un minimum
(local) de f sur [a, b], revient à résoudre l’équation f’(x) = 0.

La résolution de cette équation peut s’effectuer par le schéma itératif de

f '(x k)
Newton : k+1
x = x - k

f"(xk)
Le développement de la fonction f en série de Taylor au point xk :
f(x) = f(xk) + f '(xk) (x – xk) + ½ f"(xk) (x – xk)2
f '(x) = f '(xk) + f"(xk) (x – xk) = 0
Cette procédure nécessite la connaissance des expressions analytiques des
dérivées, ce qui est rarement le cas. On utilise alors des approximations
numériques de ces dérivées «méthode Quasi-Newton ». 14
Méthode Quasi_Newton
f '(xk)
Le schéma itératif xk+1 = xk - est effectué en utilisant des
f"(xk)
approximations des dérivées par différences finies :
h f(x + h) – f(x – h)
x* = x - *
2 f(x + h) – 2f(x) + f(x -h)
Principe
- On choisi trois points x1, x2, et x3 régulièrement espacés dans
l’intervalle [a, b]
- On pose h = x2 – x1 = x3 – x2
- On calcul f(x1), f(x2) et f(x3)
- La solution x* est donnée par :
h f(x3) – f(x1) ( f(x3) – f(x1)) (h/2)
x* = x - * =x-
2 f(x3) – 2f(x2) + f(x1) f(x3) – 2f(x2) + f(x1)
15
On peut ensuite effectuer une itération supplémentaire ; en supposant par
exemple que f(x1) > f(x3) > f(x2) >f(x*) et x2 < x* < x3 ; la solution se
trouve dans l’intervalle [x2, x3].

On pose :
x1 = x2
x3 est inchangé
x2 = milieu de [x2, x3]
h = x2 – x1 = x3 – x2
On recalcule x* en utilisant la formule

16
Exemples
Forme quadratique : on veut minimiser la fonction f(x) = x2 – 1 sur
l’intervalle [a, b]=[-2, 3] « la solution est x* = 0 ».
Méthode du nombre d’or
x1 = 0,382 (b – a) + a = - 0,09
x2 = 0,618 (b – a) + a = 1,09
f(x1) = - 0,9919 x y
f(x2) = 0,1881 -2 0,09 1,09 3

-2 0,09 1,09 3
a x1 x2 b
17
Puisque f(x2) > f(x1), on élimine [x2, b], on recherche donc la solution
dans [a, x2].
x3 est le symétrique de x1 par rapport au milieu x* de [a, x2], qui a pour
longueur 3,09.xc = 0,5*3,09 + a = -0,455
La longueur de [xc,x1] = 0,365
x3 = -0,455 – 0,365 = 0,82
F(x3) = -0,3276
Puisque f(x3) > f(x1), on élimine [a, x3], on recherche donc la solution
dans [x3, x2].

18
 I.5. Aspect théorique de l’optimisation sans contraintes
I.5.1 – Formulation du problème
Le problème étudié est : Min f(x)
x ∈Rn
où f est une fonction de Rn dans R.
La recherche d’une solution est effectuée en l’absence de contrainte,
c’est-à-dire que l’on recherche une solution sur Rn et non sur un sous-
ensemble D de Rn (ce qui correspond à l’optimisation en présence de
contraintes, et qui a pour effet de changer la solution du problème).
Exemple
Problème sans contrainte Min f(x) = x2
x ∈Rn Solution : x* = 0.
Problème avec contrainte Min f(x) = x2
x ≥1 Solution x* = 1
On constate que la solution ne correspond pas à un point stationnaire 19
I.5.2. Théorème fondamental
On considère dans cette partie une fonction quelconque f de classe C2.
Le développement en série de Taylor à l’ordre 2 de la fonction f au
voisinage V(x*) d’une solution x* du problème (P), s’écrit :

f(x) = f(x*) + ∇Tf (x*)∆x + ½ ∆x ∇2f (x*)∆x + O3 (∆x)

Où ∆x = x – x*
Théorème fondamental : condition nécessaire et suffisante si :

∇f (x*) = 0 (x* est un point stationnaire de f)

∇2f (x*) est définie positive.

Application à la recherche du minimum de la forme quadratique; cas où
B est définie positive 20
- Forme de fonction quadratique :

f(x) = f0 + aTx + 0,5 xT Bx

On a :

∇ f(x) = a + Bx

∇2f (x) = B

D’après le théorème fondamental, x* est un minimum strict de f, si est

seulement si :

∇ f(x*) = a + Bx* = 0

∇2f (x*) = B est définie positive

21
I.6. Méthodes numériques pour les problèmes sans contraintes

I.6.1 – Principe fondamental des méthodes de descente

Les techniques de descente procèdent par itérations à partir d’un

vecteur initial x0 donné, jusqu’au vecteur final xf. Le passage du
vecteur xk (kième itération) au vecteur xk+1 s’effectue en trois étapes :

- Choix d’une direction de descente sk

- Détermination de la longueur wk (wk > 0) du pas suivant cette

direction

- Calcul de xk+1 = xk + wk sk

- Test(s) d’arrêt.

22
I.6.2 - Direction de descente

I.6.2.1-Définition : le vecteur sk est une direction de descente de la

fonction f(x), s’il existe w* > 0 tel que, pour tout w satisfaisant 0 < w ≤
w*, l’on ait : f(xk+1) = f(xk + wsk) < f(xk) (1)

f(x)=c1

x3 x1
x4

x2
x0

f(x)=c2 < c1
f(x)=c3 < c2 23
Par hypothèse, f(x) est différentiable, d’où :

lim
 
f ( x k  ws k )  f x k

 
df x k  ws k

 
df x k  ws k dx = ∇Tf(xk)sk= skT ∇f(xk) (2)
w dw dx dw
W 0
donc, sk est une direction de descente si et seulement si : ∇Tf (xk) sk < 0 (3)
2.2 - Détermination générale de la direction de descente

soit M une matrice définie positive. Tout vecteur sk défini par :

sk = - M ∇f (xk) (4)

est une direction de descente. En effet, on a :

∇Tf (xk) sk = - ∇Tf (xk)M ∇f (xk) < 0

Les différentes méthodes présentées ci-après se différencient par le

choix de la matrice M. 24
I.6.3 - Longueur du pas de descente wk
I.6.3.1. Définition de la longueur du pas de descente wk: la longueur
du pas de descente wk est un scalaire strictement positif ; c’est une
mesure de la distance le long de la direction de descente sk entre deux
vecteurs successifs xk et xk+1. Différentes approches sont possibles pour
la détermination du pas wk.

I.6.3.2. Détermination théorique de la longueur optimale du pas de

descente wkopt : en supposant donnée une direction de descente sk, il est
possible de déterminer théoriquement la longueur optimale (notée wkopt)
du pas de descente selon cette direction.

En utilisant le schéma itératif xk+1 = xk + wsk, le pas de longueur

optimale doit minimiser la fonction : h(w) = f(xk + wsk)
dhw
D’après la condition du premier ordre : 0
dw 25
D’après (2) skT ∇f (xk + wsk) = skT ∇f (xk+1) = 0 (5)

En pratique, en développant f(xk+1) en série de Taylor au 2ème ordre, il

vient : f (xk+1) = f (xk) + ∇Tf (xk)(wsk) + 0.5(wskT) ∇2f (xk)(wsk)
La longueur optimale du pas de descente w est telle que :
h(w) = f (xk+1) - f (xk) = ∇Tf (xk)(wsk) + 0.5(wskT) ∇2f (xk)(wsk)
soit négative et maximale, c’est à dire minimale.
Condition du 1er ordre dhw  0 ∇Tf (xk)(sk)+(wskT)∇2f (xk)(sk) =0
dw
 
T f x k s k
  kT 2
 
kopt
w
s  f xk sk
après calculs, u(wkopt) est donnée par :
   0.5 s f xf x s s
k 2
u wkopt
T k

kT 2 k k

cette fonction est négative lorsque la matrice Hessienne est définie positive
d 2 hwkopt 
2nd  wkopt s kT  2 f x k s k
d wkopt 
Condition du ordre 2

Strictement positif si la matrice Hessienne est définie positive 26

En pratique, la détermination théorique de la longueur optimale du pas
nécessite la connaissance de la matrice Hessienne, ce qui est rarement le
cas. C’est pourquoi, la grande majorité des algorithmes utilise des
procédures numériques pour déterminer la longueur du pas de descente.
I.6.3.3. Pas de descente optimal : étant donné un vecteur xk et une
direction de descente sk, un pas wk est dit optimal s’il est déterminé
numériquement comme étant la solution du problème
monodimensionnel : wk = Min f (xk + wsk) = Min h(w)
w w
On est donc amené à résoudre, à chaque itération, un problème de
minimisation monovariable par une des méthodes monodimensionnelles
(méthode du nombre d’or ou interpolation).

I.6.3.4. Pas de descente de longueur théoriquement justifiée: dans

certains cas, des considérations théoriques sur la direction de descente
fournissent une longueur de pas théoriquement optimale. C’est le cas
pour la méthode de Newton du deuxième ordre qui conduit à wk = 1. 27
I.6.3.5.Pas de descente non optimal (sous relaxation):à chaque
itération, on fixe une valeur maximale wk (wk > 1) pour le pas de
descente. Si on a : f (xk + wsk) < f (xk) (7)
On conserve la valeur wk. Dans le cas contraire, on multiplie wk par un
facteur d (0 < d < 1) wknew = wkold * d
Et l’on effectue à nouveau le test (7) ; s’il est vérifié, on conserve la valeur de
wk ; sinon, on répète cette procédure jusqu’à ce que le test (7) soit vérifié.
I.6.4. Test(s) d’arrêt
Pour arrêter les itérations au sein des procédures de descente, on peut
utiliser les tests suivant :
1 – Dépassement d’un nombre maximal d’itérations kmax, fixé a priori.

2 – Non évolution de la fonction objectif : < e1 « tolérance donnée »

3 – Gradient nul : ‖∇f (xk) ‖< e2 « tolérance donnée » 28

I.6.5.Méthodes du premier ordre Méthodes utilisant uniquement les dérivées 1ères
I.6.5.1. Méthode de la plus grande pente (Méthode du gradient)
Cette méthode permet de déterminer le minimum d’une fonction dont
on peut calculer le gradient. Lorsqu’on ne dispose pas d’une expression du
gradient de la fonction f, une estimation par une méthode de différence finies peut être
utilisée.
sk = - M ∇f (xk)
Le choix le plus simple pour la matrice M est la matrice identité I, la
matrice identité d’ordre n. La direction de descente est alors définie par :
sk = - ∇f (xk) (8)
Cette direction est appelée « Direction de la plus grade pente ».
Donc, sk est une direction de descente si et seulement si : ∇Tf (xk) sk < 0
∇Tf (xk) sk = |∇Tf (xk) | | sk | cos(q
 q  90 ;  q < 90 ;  q > 90 29
Algorithme de la méthode ∇f (xk)
Etape 1 : Pour un vecteur initial x0 donnée,
sk
- calculer f(x0) q

- initialiser le nombre d’itération k à zéro

Etape 2 : calculer ∇f(xk) et poser sk = -∇f (xk)
numériquement, analytiquement ou symboliquement -∇f (xk)
Etape 3 : calculer la longueur du pas wk suivant la direction sk.
a. Pas optimal : déterminer wk par une méthode de recherche
monodimensionnelle, tel que : f(xk + wksk) = min f(xk + wsk) = min h(w)
w>0 w>0
b. Pas non optimal : trouver wk par la méthode de sous relaxation, tel
que : f (xk + wsk) < f (xk)
Etape 4 : calculer xk+1 = xk + wk sk
Etape 5 : calculer f(xk+1) et effectuer les tests d’arrêt. S’ils sont vérifiés,
la recherche est terminée, sinon poser k = k+1 et retourner à l’étape 2. 30
Exemple : on considère le Pb : min f(x) = (x1 – 1)2 + (x2 - 2)2 ; x ∈ R2

on a : -∇Tf (x) = [2 (x1 – 1), 2(x2 – 2)] ; x0T = [2; 3] et f(x0) = 2

1. Calcul de w par la méthode de sous relaxation : on choisit pour

toutes les itérations wk = 3 et d = 0,5

∇Tf (x0) = [2;2] ; s0T = - ∇Tf (x0) = [-2;-2]

(x0 + w0s0)T = [-4; -3] ; f (x0 + w0s0) = 50 la fonction ne diminue pas

on pose w0 = dw0 = 1,5 = w0new = dw0old = 0,5 *3 = 1,5

(x0 + w0s0)T = [-1; 0] ; f (x0 + w0s0) = 8 la fonction ne diminue pas

on pose w0 = dw0 = 0,75

(x0 + w0s0)T = [0,5 ; 1,5] ; f(x0 + w0s0) = 0,5 la fonction ayant diminué,
on pose : x1T = (x0 + w0s0)T = [0,5 ; 1,5] ; f(x1) = 0,5.
∇Tf (x1) = [-1 ; -1] et s0T = - ∇Tf (x1) = [1 ; 1] 31
(x1 + w1s1)T = [3,5;4,5] ; f (x1 + w1s1)=12,5 la fonction ne diminue pas
on pose w1 = dw1 = 1,5

(x1 + w1s1)T = [2; 3] ; f (x1 + w1s1) = 2 la fonction ne diminue pas, on

pose w1 = dw1 = 0,75

(x1 + w1s1)T =[1,25;2,25] ; f (x1 + w1s1)=0,125 la fonction ayant diminué

on pose : x2T = (x1 + w1s1)T = [1,25; 2,25] ; f(x2) = 0,125

2. Recherche du pas optimal

(x0 + ws0)T = [2 – 2w; 3 – 2w] ; min f(x0 + ws0) = Min h(w)
w>0 w>0
avec, h(w) = (1 – 2w)2 + (1 – 2w)2
- Condition du premier ordre : h’(w0) = 0 ⇔ w0 = 0,5
- Condition du second ordre : h"(w0) = 16 > 0 ; donc w0 est un
minimum. On pose x1T = (x0 + w0s0)T = [1, 2] = x*T
32
I.6.5.2. Méthode des gradients conjugués
I.6.5.2.1. Gradients (Directions) conjugués
Définition : soit B une matrice symétrique n × n, définie positive. On dit que
deux vecteurs s1 et s2 de Rn sont B-conjugués (ou conjugués par rapport à B)
s’il vérifient : s1 T B s2 = 0 (1)
La matrice B étant définie positive, la forme bilinéaire : a(s1, s2) = s1TB s2
définit un produit scalaire et la relation (1) traduit l’orthogonalité des vecteurs
s1 et s2 pour ce produit scalaire.
• Soit B  IRnxn, définie positive. Un ensemble de vecteurs non nuls
s1,…,sn sont B-conjugués si siTBsj = 0 i, j, ij.
Note
• Si B = I, conjugués = orthogonaux.
• Si s1…,sn sont B-conjugués, alors ils sont linéairement indépendants.
33
Preuve

• Supposons par l ’absurde que

sn = a1s1+...+an-1sn-1

et a1,..., an-1 non tous nuls. Alors,

snTBsn = a1snTBs1+...+an-1snTBsn-1

• Comme s1,..., sn sont B-conjugués,

snTBsn = 0

• Impossible car sn est non nul et B définie positive.

34
Algorithme du gradient conjugué pour une forme quadratique

Etape 1

Pour un vecteur initial x0 donnée, calculer g 0

  f x  
0
 a  Bx 0

 
Poser s 0  f x 0 et initialiser le nombre d’itération k à zéro.

Etape 2

A l’itération k, on effectue les calculs à partir du vecteur xk.

Définir : xk+1 = xk + wksk

   
avec : kT k
s g
w   kT k
k
où : g k  f x k  a  Bx k
s Bs
35
Puis :
  
S k 1   g k 1   k S k où : g k 1  f x k 1  a  Bx k 1 
 k 1 k
Avec : g BS
 k   kT k
S BS
Poser k = k + 1 et revenir au début de l’algorithme.

Théorème

A une itération quelconque k où l’optimum n’est pas encore atteint

(c’est à dire gi  0, i = 1, 2, ……., k), on a :

Les directions S0, S1, ….., Sk+1 sont mutuellement conjuguées par
rapport à la matrice hessienne B et :
 k 1T k 1
kT k g g
g g
w   kT k
k
 0    kT k
k

g Bg
S BS
36
Exemple Supposons qu’on veut minimiser f(x)
 
f x  2x12  x22  3 ; x0  1,1 ; S 0   4,2
t t

x0
x0 x1=x0+w1s1
x1=x0+w1s1

x2=x1+w2s2
x2=x1+w2s2

Trouver la direction conjuguée à S0.

 4 4 0
S     ;  f x   Bx   
0 2

 2 0 2
On choisi S11 et on détermine S21
4 0  S11   S11 
 14 2    1   16 4  1   0
0 2  S 2   S 2  S 11  1  16  4S 12  0  S 12  4
 
 16 S11  4 S 21  0 S 1  1  4
t
37
Vérifions qu’on peut trouver le minimum de f(x) en deux étapes, en
utilisant s0 ensuite s1.
Puisque f(x) est quadratique on peut utiliser la formule
  4
4 2  
S f x
kT
w   kT k
k
k
  w0     2 
20
4 0 4
S BS  4  2     72
0 2    2 

1 20  4  0.1111
x  x w s        
1 0 0 0


1 72 
  
2 0 .4444 
Pour l’étape suivante la direction de recherche est : S 1  1  4
t

1 
 0,4444 0,8888  
  4
w 
1
 0,111
 4 0  1 
1  4    
0 4    4 
 0,1111  1  0 
x  x w S  
2 1 1 1
  0,1111    
0,4444    4  0  38
Cas d’une forme quelconque

La méthode proposée par Fletcher et Reeves (1964) est une extension

directe de la procédure présentée pour les formes quadratique, au cas de
fonctions quelconques.

Lorsqu’elle est appliquée à une fonction quadratique, elle est identique

précédemment.

Pour une fonction quelconque, cette méthode nécessite peu de calculs et

d’espace mémoire, et sa vitesse de convergence est largement
supérieure à celle des algorithmes classiques de gradient (comme par
exemple la méthode de plus grande pente).

39
Algorithme de la méthode

Etape 1 Pour un vecteur initial x0 donné, calculer f(x0), s0= -f(x0) et

initialiser le nombre d’itération k à zéro.

Etape 2

a – calculer wk en minimisant la fonction h(w) = f(xk + w sk) «

méthodes de recherche monodimensionnelle).

b – Calculer xk+1 = xk + wksk

c – Calculer ensuite : k 1

 f x k 1
 s k    
 T f x k  1 f x k  1
f x f x 
S
T k k

Etape 3 Effectuer les tests d’arrêt. S’ils sont vérifiés, la recherche est
terminée, sinon poser k = k + 1 et retourner à l’étape 2.
40
I.6.5.3. Méthode de Newton du second ordre

La direction de descente est fournie par le développement en série de

Taylor au deuxième ordre de la fonction f au voisinage du vecteur xk.

       
f x k  d k  f x k  T f x k d k  0,5 d kT  2 f x k d k

On choisit alors comme nouveau vecteur xk+1, le minimum de f(xk + dk),

lorsqu’il existe.

La matrice Hessienne  2 f x k  est définie positive

Le minimum est défini par :  

T f x k 1  0
        
f x k  d k  f x k  T f x k d k  0,5d kT  2 f x k d k

   
f x k   2 f x k d k  0

x k 1
 x  f x
k 2
 k 1
 
f x k


x k 1  x k  2
f x  
k

 f xk  
On remarque que dans cette méthode, la longueur du pas de descente
est fixée (en fait on a wk = 1).

Par construction, la méthode de Newton appliquée à une forme

quadratique converge en une seule itération.
42
Pour une fonction quelconque des difficultés de convergence peuvent
apparaître, en particulier lorsque le vecteur initial x0 est trop éloigné de
la solution optimale, car on peut sortir du domaine de validité du
développement de Taylor au voisinage du vecteur xk. Pour pallier cette
difficulté, on utilise le schéma itératif :

x k 1
 x w  f x
k k 2
 
k 1
 
f x k

Où wk est déterminé en minimisant la fonction h(w) = f(xk + wsk) (méthode de

recherche monodimentionnelle).

43
Méthodes Quasi-newtoniennes

Le principe général de ces méthodes consiste en une extension de

la formule de Newton, où la matrice  22
  1
f xkk)-1
f(x est remplacée par
k
une matrice H définie positive, donnant la direction de descente à
partir du gradient  f  
x k
.

Le schéma itératif s’écrit alors :

x k 1  x k  wk H k f x k 

44
 Algorithme de la méthode
Etape 1 : Pour un vecteur initial x0 donné, calculer f(x0), s0 = -f(xk)

Etape 2
A – déterminer la direction de descente sk = -Hkf(xk)
Calculer wk en minimisant la fonction h(w) = f(xk + wsk)
B – calculer xk+1 = xk + wksk
C- Déterminer la matrice Hk+1 selon la relation

45