Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Méthode d’optimisation

Zakia ANKHILI
Université Cadi Ayyad
ENSA, Marrakech

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 1/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

I) Algorithme

1) Définition
Un algorithme est un procédé qui permet à partir d’un
point initial x0 d’engendrer une suite (xk ). On le définit
par une application A qui à xk associé xk+1 .
On souhaite bien sûr que la suite (xk ) converge vers un
point optimal du pb d’optimisation considéré. Dans ce
cas, on dit que l’algorithme A converge vers la solution
du pb.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 2/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2) Convergence global
Définition
On dit qu’un algorithme A est globalement convergent (ou
possède la propriété de la convergence globale) si ∀ le point de
départ x0 choisi, la suite (xk ) engendré par A (ou une sous
suite de (xk )) converge vers un point satisfaisant une condition
nécessaire d’optimalité.

Remarques
La convergence globale d’un algorithme n’implique pas la
convergence vers un optimum global pour tout point de
départ x0 .
Notons que si un algorithme A possède la propriété de la
convergence globale, il suffit d’imposer une condition de
convexité pour assurer la convergence de l’algorithme vers
un optimum global du pb ∀ le point de départ choisi.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 3/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

3) Convergence asymptotique
L’efficacité d’un algorithme est mesurée par la vitesse de
convergence et sa complexité calculatoire.
Complexité calculatoire
Elle mesure le coût des opérations nécessaires pour obtenir
une itération. Le coût global étant le coût d’une itération
multiplié par le nombre d’itérations pour obtenir une
approximation à  près ( est fixé à l’avance) de l’optimum x ∗ .

Vitesse de convergence
Supposons qu’on compare entre plusieurs algorithmes
seulement par leur complexité calculatoire. En admettant que
le temps du calcul par itération est le même pour tous, le
meilleur est donc celui qui nécessitera le plus petit nombre
d’itération.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 4/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Malheureusement, on ne peut pas faire des conclusions

générales de ce genre puisque le point de départ, la nature de
la fonction à optimiser, la valeur de la tolérance choisie peut
varié considérablement. Donc, il faut penser à un autre type
d’analyse. C’est l’objet de l’étude de la convergence
asymptotique (i.e le comportement de la suite (xk ) au
voisinage du point limite x ∗ ). L’étude de la convergence
asymptotique permet d’attribuer à chaque algorithme un
indice d’efficacité appelé sa vitesse de convergence.

Supposons que que f : IRn → IR. On introduit l’erreur

vectorielle sur la solution: ek = x ∗ − xk (la suite xk → x ∗ ).

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 5/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Si la norme euclidienne kek k décroît linéairement, on dit

que la vitesse de convergence est linéaire. En terme
mathématique

∃c ∈]0, 1[, ∃k0 ∈ IN, ∀k ≥ k0 , kek+1 k ≤ ckek k

kek+1 k
Si lim = 0, on dit que la vitesse de convergence
k→+∞ ke k k
est superlinéaire.
On dit que la vitesse de convergence est superlinéaire
d’ordre p si on a une relation du type :

∃p > 1, ∃c ∈]0, 1[, ∃k0 ∈ IN, ∀k ≥ k0 , kek+1 k ≤ c(kek k)p

Si p = 2, on dit que la vitesse de convergence est

quadratique.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 6/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

II) Méthodes pour l’optimisation sans contraintes

On considère un problème d’optimisation sans contraintes :

min f (x)
x∈IRn

où f : IRn → IR de classe C 1 . On a la condition nécessaire

d’optimalité

(1) ∇f (x) = 0

Le système d’équations (1) se résout en général par des

méthodes itératives de descente.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 7/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

1) Principe général des méthodes itératives de

descente
Initialisation : On cherche x0 aussi bon que
possible.
Étape k : Si ∇f (x) ' 0, on termine, xk satisfait
approximativement la condition nécessaire
d’optimalité. Sinon,
On choisit une direction de descente dk à partir de xk :
∇f (xk )T dk < 0.
Recherche linéaire à partir de xk le long de la direction
dk : On cherche un minimum local ρk > 0 de
g(ρ) = f (xk + ρdk ). On pose

xk+1 = xk + ρk dk

et on va à l’étape k.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 8/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
x0 ne doit pas être un maximum local.
À la fin de l’étape k, càd lorsque la condition nécessaire
est vérifiée, il faut vérifier que c’est bien un minimum
local et non pas un point-selle

2) Méthode du gradient ou de la plus forte

pente
Définition
La méthode du gradient consiste à prendre comme
direction de descente à partir d’un point xk ,
dk = −∇f (xk ). En effet,

∇f (xk )T dk = −k∇f (xk )k2 < 0

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 9/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

La méthode du gradient est appelée également méthode de la

plus forte pente.
Proposition
Deux directions de déplacement successive sont orthogonales.

Preuve
Soit g : ρ 7→ f (xk + ρdk ). ρk minimise g, donc g 0 (ρk ) = 0.
C’est à dire

0 = ∇f (xk + ρk dk )T dk = ∇f (xk+1 )T dk = −dk+1 T dk .

D’où dk+1 ⊥dk

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 10/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
La proposition signifie que le gradient en un point est
perpendiculaire à la courbe de niveau passant par ce
point.
L’inconvénient de la méthode du gradient est que la
convergence peut être très lente pour certaines fonctions
Avantage :
Elle est simple
Pour l’espace mémoire : à chaque itération, il y a
seulement 2 vecteurs à stocker xk et dk

Convergence de la méthode
Soit f : IRn → IR une fonction de classe C 1 coercive. Alors,
pour tout point de départ x0 , la méthode du gradient avec
recherche linéaire converge vers un point stationnaire de f .
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 11/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Preuve
D’après l’hypothèse de coercivité ,
∃R > 0/kxk > R ⇒ f (x) ≥ f (x0 ). D’autre part, la suite
(f (xk )), par construction, est une suite décroissante. On a
donc f (xk ) ≤ f (x0 ), ∀k ≥ 0. On déduit alors que kxk k ≤ R et
donc la suite (xk ) est bornée. (xk ) admet alors une valeur
d’adhérence x̄. Par conséquent, il existe une sous suite (xnk )
telle que lim xnk = x̄. On a
k→+∞

f (xnk+1 ) ≤ f (xnk − ρ∇f (xnk )) ∀ρ > 0

(Recherche linéaire). f est de classe C 1 ,

lim f (xnk ) = f (x̄) et lim ∇f (xnk ) = ∇f (x̄).

k→+∞ k→+∞

Donc, f (x̄) ≤ f (x̄ − ρ∇f (x̄)), ∀ρ > 0. D’où ∇f (x̄) = 0

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 12/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

3) Méthode de directions conjuguées

3.1 Principe général
Considérons la fonction quadratique :
1
f (x) = x T Ax + bT x + c,
2
où A est une matrice n × n définie positive et
symétrique, b ∈ IRn et c ∈ IR. Le principe des
méthodes de directions conjuguées consiste, à partir
d’un x0 , à minimiser f (x) successivement suivant
des directions linéairement indépendantes qui sont
mutuellement conjuguées.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 13/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Définition
Soient A une matrice symétrique définie positive et
d1 , ..., dk ∈ IRn . On dit que d1 , ..., dk sont mutuellement
conjuguées par rapport à A (ou A− orthogonaux deux à deux)
si

∀i, j tels que 1 ≤ i ≤ k, 1 ≤ j ≤ k, et i 6= j on a diT Adj = 0

Proposition
Soit A une matrice n × n symétrique et définie positive. Si
d1 , ..., dk sont des vecteurs A− orthogonaux deux à deux, alors
ils sont linéairement indépendants.

Preuve
k k
αj djT Adi = 0. Alors,
X X
αj dj = 0. Pour 1 ≤ i ≤ k, on a
j=1 j=1
αi diT Adi =Chapitre
Zakia ANKHILI
0, 4∀1 ≤ iMéthode
≤ k,d’optimisation
d’où αi = 0ENSA
(car(Marrakech)
A est2013 définie 14/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
Dans IRn , si d1 , ..., dn sont A− orthogonaux deux à deux,
alors ces vecteurs forment une base.
On verra que les méthodes de directions conjuguées conduisent
à l’optimum en n étapes au plus. Supposons donc que ,
∀ k = 0, ..., n − 2, xk+1 est déterminé à partir de xk par :
xk+1 = xk + ρk dk ,
où ρk est la valeur de ρ qui minimise f (xk + ρdk ). On a donc
dkT ∇f (xk+1 ) = dkT (Axk+1 + b) = 0.
dkT A(xk + ρk dk ) + dkT b = 0.
D’où
dkT (Axk + b)
ρk = − ( A est définie positive)
dkT Adk
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 15/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

En remarquant que ∀ 1 ≤ k ≤ n,
k−1
X
xk = x0 + ρj dj ,
j=0

on trouve
k−1
dk T Axk = dkT Ax0 + ρj dkT Adj = dkT Ax0 .
X

j=0

Par suite ρk est défini par

dkT (Ax0 + b)
ρk = − .
dkT Adk

Soit Bk un sous espace de IRn engendré par d0 , ..., dk−1 . On

peut alors démontrer la propriété caractéristiques des
méthodes de directions conjuguées
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 16/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Théorème
∀ 1 ≤ k ≤ n, le point :
k−1
X
xk = x0 + ρ j dj
j=0

est l’optimum de f (x) sur la variété linéaire x0 + Bk x.

Remarque
On a Bn = IRn , alors xn est le minimum global de f sur
IRn .
Les méthodes de directions conjuguées convergent donc
de façon finie en au plus n étapes.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 17/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

3.2 La méthode de gradient conjugué pour les

fonctions quadratiques
On suppose que
1
f (x) = x T Ax + bT x + c
2
L’idée de la méthode est de construire progressivement des
directions d0 , ..., dn−1 , mutuellement conjuguées par rapport à
la matrice A. À chaque étape k, la direction dk est obtenue
par combinaison linéaire du −∇f (xk ) et des directions
précédentes d0 , ..., dk−1 . Les coefficients de la combinaison
linéaire étant choisis de telle sorte que dk soit conjuguée par
rapport à toutes les directions précédentes.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 18/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Algorithme
1 Initialisation : Choisir un point de départ x0 .
2 À l’itération k, on est au point xk
Choix de la direction:
dk = −∇f (xk ) + βk−1 dk−1 avec

−∇f (xk )T Adk−1

βk−1 = T Ad
dk−1 k−1

Recherche linéaire :

xk+1 = xk + ρk dk ,
∇f (xk )T dk
avec ρk = dkT Adk
Si ∇f (xk+1 ) ' 0, arrêter xk+1 = x ∗ , sinon k ← k + 1 et
retourner à l’étape (2)
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 19/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

3.3 Cas non quadratique : Méthode de Fletcher-Reeves

Il s’agit d’une généralisation de la méthode du gradient
conjuguée appliquée à une fonction quelconque. La différence
essentielle réside dans le fait qu’on n’a pas, en général,
d’expression du pas ρk . Il faut donc faire appel, à chaque
itération, à un algorithme de minimisation dans IR (recherche
linéaire).
Méthode de Fletcher-Reeves
1 Initialiser l’algorithme avec x0 et poser d0 = −∇f (x0 ),
2 à l’étape k, calculer xk+1 selon la formule de récurrence :
xk+1 = xk + ρk dk avec

k∇f (xk )k2

dk = −∇f (xk ) + βk−1 dk−1 et βk−1 =
k∇f (xk−1 )k2

ρk est la valeur de ρ qui minimise la fonction g définie

par: g(ρ) = f (xk + ρk dk ).
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 20/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

4) Méthode de Newton
Soit f : IRn → IR, une fonction de classe C 2 . L’idée de la
méthode itérative de Newton est de minimiser à chaque
itération l’approximation quadratique de f au point courant
xk . La fonction quadratique est donnée par le développement
de Taylor d’ordre 2 :
1
q(x) = f (xk ) + ∇f (xk )T (x − xk ) + (x − xk )T ∇2 f (xk )(x − xk ).
2
Si ∇2 f (xk ) est défini positif, alors q est strictement convexe et
admet donc un minimum unique xk+1 défini par
∇q(xk+1 ) = 0 ⇔ ∇f (xk ) + ∇2 f (xk )(xk+1 − xk ) = 0,
Donc
xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ).
Vérifions que dk = xk+1 − xk est une direction de descente.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 21/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

En effet,

∇f (xk )T dk = −∇f (xk )T [∇2 f (xk )]−1 ∇f (xk ) < 0,

car [∇2 f (xk )]−1 est définie positive

Remarque
La méthode de Newton converge en une seule itération si
f est quadratique strictement convexe.
La direction et le pas sont fixés.
La méthode s’arrête lorsque ∇f (xk ) = 0, car il s’ensuit
que xk+1 = xk .

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 22/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Inconvénients
L’inverse de la matrice hessienne [∇2 f (xk )]−1 peut ne pas
exister. Dans ce cas la méthode échoue. Cela intervient
lorsque la méthode atteint une région où f est linéaire
(ses secondes dérivées partielles valent zéro).
La méthode de Newton ne possède pas la propriété de
convergence globale.
A chaque itération de l’algorithme, il faut calculer le
gradient ∇f (xk ), et la matrice hessienne ∇2 f (xk ) puis
inverser celle-ci. Tout ceci, lorsque c’est possible, coûte
beaucoup trop cher en terme de calculs.
Si ∇2 f (xk ) n’est pas définie positive,
la méthode de Newton n’est pas une méthode de
descente : il est possible qu’on trouve f (xk+1 ) > f (xk ).
La méthode, à chaque itération, recherche uniquement
un point tel que ∇q(x) = 0. Ce point peut être un
Zakia ANKHILI
maximum,
Chapitre 4
unMéthode
minimum ou un point-selle.
d’optimisation ENSA (Marrakech) 2013 23/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Deux modifications importantes :

1 Modification du pas de la direction : On pose
xk+1 = xk + ρk dk ,
où dk = −[∇2 f (xk )]−1 ∇f (xk ), et ρk est choisi de telle
sorte que kxk+1 − xk k ne soit pas trop grande. On peut
aussi trouver ρk par une recherche linéaire.
2 Perturbation de ∇2 f (xk ) pour obtenir une matrice
définie positive : Si ∇2 f (xk ) est définie positive alors
dk est une direction de descente. Dans le cas contraire,
on fait une perturbation de ∇2 f (xk ) pour obtenir une
matrice définie positive :
Mk = k I + ∇2 f (xk ),
où k est la plus petite constante telle que toute les
valeurs propres de Mk soient supérieurs à une constante
δ > 0 donnée.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 24/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
dk = −Mk−1 ∇f (xk ) est une direction de descente. En
effet,

∇f (xk )T dk = −∇f (xk )Mk−1 ∇f (xk ) < 0.

Pour déterminer k théoriquement, il suffit de calculer les

valeurs propres de ∇2 f (xk ).
Pratiquement, on ne va pas calculer directement les
valeurs propres de ∇2 f (xk ). On factorise ∇2 f (xk ).
∇2 f (xk ) = LkT Dk Lk , où Lk est une matrice triangulaire
avec les éléments diagonaux valent 1 et Dk est une
matrice diagonale.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 25/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

5) Méthodes quasi Newton

5.1 Principe général
Ces méthodes sont des généralisations de la méthode de
Newton. L’idée de ces méthodes est d’imiter l’algorithme de
Newton tout en évitant de calculer le hessien de f et son
"inverse". Plus précisément, cela signifie que, à l’itération k,
on va chercher à construire une approximation Sk symétrique
définie positive de [∇2 f (xk )]−1 . C’est à dire au lieu de
procéder à l’itération :

xk+1 = xk − ρk [∇2 f (xk )]−1 ∇f (xk ),

on calcule
xk+1 = xk − λk Sk ∇f (xk ),
avec λk est le minimum de la fonction
g(λ) = f (xk − λSk ∇f (xk )).
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 26/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

A l’itération k, la matrice Sk est mise à jour par une correction

additive Sk+1 = Sk + Ck , avec Ck est une matrice de
correction qui tient compte des informations apportées par le
nouveau point et son gradient. En particulier, Ck sera choisi de
manière à satisfaire l’équation dite condition de quasi-Newton

(1) Sk+1 [∇f (xk+1 ) − ∇f (xk )] = xk+1 − xk .

Différentes formules de correction de type Sk+1 = Sk + Ck

ont été proposé. Suivant que la matrice Ck est de rang 1 ou
de rang 2, on parlera de correction de rang 1 ou de rang 2.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 27/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

5.2 Correction de rang un

On choisit une matrice de rang 1 de la forme Ck = αk vk vkT , où
αk et vk sont respectivement un scalaire et un vecteur choisis
de telle sorte que l’équation (1) est satisfaite. posons
(
qk = ∇f (xk+1 ) − ∇f (xk )
pk = xk+1 − xk
(1) ⇔ Sk+1 qk = pk , ce qui implique
(Sk + αk vk vkT )qk = pk ,
⇒ αk vk (vkT qk ) = pk − Sk qk .
On choisit par exemple
(
vk = pk − Sk qk
αk vkT qk = 1
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 28/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

On obtient
(pk − Sk qk )T (pk − Sk qk )
Sk+1 = Sk +
(pk − Sk qk )T qk

Algorithme de correction un
1 Soit x0 un point de départ, S0 = I , matrice initiale
2 A l’iteration k,

xk+1 = xk − λk Sk ∇f (xk ),

avec λk est le minimum de g(λ) = f (xk − λSk ∇f (xk )).

Sk est mise à jour par

(pk − Sk qk )T (pk − Sk qk )
(2) Sk+1 = Sk +
(pk − Sk qk )T qk

où pk = xk+1 − xk et qk = ∇f (xk+1 ) − ∇f (xk ).

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 29/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Théorème
Si f est quadratique de hessien symétrique défini positif A, et
si p0 , ..., pn−1 sont indépendants, alors la suite des matrices Sk
obtenue par la formule (2) converge, en au plus n étape, vers
A−1 .
Remarque
La formule (2) présente l’inconvénient que, même si la
fonction f est quadratique et son hessien A est défini
positif, les matrices Sk , obtenues ne sont pas
nécessairement définies positives.
La formule (2) peut ne pas avoir de sens, par exemple si
le terme ([pk − Sk qk ])T qk est nul ou simplement a une
très faible valeur.
Lorsque ces deux situations se produisent, il faut prévoir
des procédures spéciales pour la mise à jour des matrices
Sk . Chapitre 4
Zakia ANKHILI Méthode d’optimisation ENSA (Marrakech) 2013 30/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

5.3 Méthode de Davidon-Fletcher-Powell (DFP)

On utilise deux corrections de rang 1 pour la mise à jour de la

matrice Sk .

Sk+1 = Sk + αk vkT vk + βk wkT wk .

En prenant

vk = pk , wk = Sk qk , αk vkT qk = 1, et βk wkT qk = −1,

on obtient
pk pk T Sk qk qk T Sk
Sk+1 = Sk + −
pk T qk qk T Sk qk

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 31/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Algorithme de DFP
1 On part d’un point x0 et S0 = I (S0 = I peut être une
matrice définie positive quelconque)
2 On pose
xk+1 = xk − λk Sk ∇f (xk ),
avec λk est le minimum de f (xk − λSk ∇f (xk )), et Sk est
mise à jour par

pk pk T Sk qk qk T Sk
(3) Sk+1 = Sk + − ,
pk T qk qk T Sk qk

où pk = xk+1 − xk et qk = ∇f (xk+1 ) − ∇f (xk ).

Le résultat suivant montre que sous certaines conditions, la

formule (3) conserve la définie-positivité des matrices Sk .

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 32/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Théorème
On suppose que la matrice Sk est définie positive. Alors si la
condition pk T qk > 0 est vérifiée, la matrice Sk+1 est également
définie positive. Cette condition est satisfaite, en particulier, si
λk est obtenu par recherche linéaire.

Remarque
La conservation de la définie positivité est essentielle, car elle
garantit que les directions dk = −Sk ∇f (xk ) sont des directions
de descente.

Théorème
Si f est quadratique de matrice A définie positive, l’algorithme
(DFP) engendre des directions p0 , ..., pk vérifiant pour tout k
pi T Apj = 0, (0 ≤ i < j ≤ k)
Sk+1 Api = pi , (0 ≤ i ≤ k)
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 33/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
Le théorème montre que, dans le cas quadratique, les
directions, p0 , ..., pk engendrées par l’algorithme (DFP)
sont mutuellement conjuguées par rapport à A. On
retrouve alors une méthode de type gradient conjugué.
Dans ce cas l’algorithme converge donc en au plus n
itérations.
Pour k = n − 1, la deuxième assertion du théorème
précédent devient Sn Api = pi , (i = 0, ..., n − 1) et
comme les directions pi sont mutuellement conjuguées
par rapport à A, on en déduit que Sn A = I . Donc,
Sn = A−1 . La formule de correction (3) permet donc de
construire en au plus n étape (dans le cas quadratique),
l’inverse du hessien de f .

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 34/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

5.4 Méthode de Broyden, Fletcher, Goldfarb,

Shanno (BFGS)
Si on intervertit les rôles de pk et qk dans la formule

pk pk T Sk qk qk T Sk
(3) Sk+1 = Sk + − ,
pk T qk qk T Sk qk
on obtient une suite de matrices définie par

qk qk T Hk pk pk T Hk
(4) Hk+1 = Hk + − .
qk T p k pk T Hk pk
les matrices obtenues vérifient la relation Hk+1 pk = qk .
La formule (4) permet alors de construire une approximation
du hessien et non pas de son inverse. Pour obtenir une formule
de correction pour approximer l’inverse du hessien, il suffit de
prendre l’inverse de Hk .
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 35/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Le calcul donne
qk T [Hk ]−1 qk pk pk T
" #
−1 −1
[Hk+1 ] = [Hk ] + 1+ . T
p k T qk p k qk

pk qk T [Hk ]−1 + [Hk ]−1 qk pk T

−
p k T qk
Remarquons que la dernière formule exprime [Hk+1 ]−1 en
fonction de [H k ]−1 . On a alors la formule de correction
" #
qk T Sk qk pk pk T pk qk T Sk + Sk qk pk T
(5) Sk+1 = Sk + 1 + . T −
pk T qk p k qk p k T qk

L’algorithme BFGS se déduit alors directement de l’algorithme

DFP en remplaçant la formule (3) par la formule (5).

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 36/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Proposition
Si Sk est définie positive et pk T qk > 0, alors Sk+1 est définie
positive.

Remarque
La méthode BFGS est considérée comme très robuste et
est moins sensible aux erreurs dans les recherches
linéaires.
Lorsque les algorithmes DFP et BFGS sont appliquées à
une fonction non linéaire quelconque (non quadratique), il
faut procéder à des réinitialisations périodiques pour
assurer la convergence globale. Par exemple, à toute les n
itérations, on prend comme point de départ le dernier
point obtenu et on réinitialise la matrice H (en faisant
H0 = I )

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 37/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

III) Recherche linéaire

Comme nous l’avons vu, les méthodes de descente
consistent à chaque étape de résoudre un problème
unidimensionnel par la détermination de ρk . i.e.
chercher ρk ≥ 0, minimisant la fonction définie par

g(ρ) = f (xk + ρdk ).

Ce problème doit être résolu un grand nombre de

fois. Il est important de disposer d’algorithmes
efficaces pour le traiter.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 38/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

1) Recherche linéaire exacte

1.1 Méthode de Newton-Raphson
La fonction g est supposée de classe C 2 . La
recherche d’un minimum de g se fait en cherchant
un point stationaire.i.e. g 0 (ρ) = 0. Le problème à
résoudre est donc g 0 (ρ) = 0.
Soit ρk le point obtenu à l’étape k. On considère la
tangente à Cg 0 au point (ρk , g 0 (ρk )):

y = g 00 (ρk )(ρ − ρk ) + g 0 (ρk )

ρk+1 est pris comme étant l’intersection de cette

tangente avec l’axe (ox). g 0 (ρk )
ρk+1 = ρk − 00
Zakia ANKHILI Chapitre 4 Méthode d’optimisation
g (ρENSA
k ) (Marrakech) 2013 39/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Algorithme
ρ0 donné
g 0 (ρk )
ρk+1 = ρk − 00
g (ρk )

Remarque
Il est important de remarquer que cette procédure a une
propriété de convergence finie lorsqu’elle est appliquée à une
fonction quadratique du type

g(ρ) = uρ2 + vρ + w (u > 0).

En effet, pour un point de départ quelconque ρ0 , on a

g 0 (ρ0 ) = 2uρ0 + v

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 40/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2uρ0 + v v
g 00 (ρ0 ) = 2u et ρ1 = ρ0 − =− ,
2u 2u
qui est bien le minimum de g.

Lorsque le point de départ ρ0 est suffisamment proche du

minimum ρ∗ cherché, la vitesse de convergence de la méthode
est généralement quadratique. Cependant la convergence
globale de la méthode n’est pas garantie en général.

Exemple

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 41/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

1.2 Méthode de la sécante

Un inconvénient de la méthode de Newton est d’avoir évaluer
à la fois la dérivée première et la dérivée seconde en chaque
point. En approximant la dérivée seconde en ρk par

g 0 (ρk ) − g 0 (ρk−1 )
,
ρk − ρk−1
la formule de Newton devient
ρk − ρk−1
ρk+1 = ρk − g 0 (ρk ) .
g 0 (ρk ) − g 0 (ρk−1 )

Cette méthode est appelé méthode de la sécante. Elle consiste

à approximer la fonction g par la droite passant par
(ρk−1 , g 0 (ρk−1 )) et (ρk , g 0 (ρk )). En effet, l’equation de cette
droite est:
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 42/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

g 0 (ρk ) − g 0 (ρk−1 )
y= (ρ − ρk ) + g 0 (ρk ).
ρk − ρk−1
L’intersection de cette droite avec l’axe (ox) est donné par

g 0 (ρk ) − g 0 (ρk−1 )
g 0 (ρk ) = (ρk − ρ)
ρk − ρk−1
ρk − ρk−1
ρk+1 = ρk − g 0 (ρk ) .
g 0 (ρk ) − g 0 (ρk−1 )

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 43/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
Comme la méthode de Newton, la convergence globale de la
méthode de la sécante n’est pas assurée. Les points de départ
ρ0 et ρ1 doivent donc choisis suffisamment proche de
l’optimum ρ∗ .

Théorème
Si g est de classe C 3 au voisinage de ρ∗ et si g 00 (ρ∗ ) > 0, la
méthode
√ de la sécante a une convergence superlinéaire d’ordre
1+ 5
2
(nombre d’or)

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 44/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2) Recherche linéaire inexacte

Les méthodes unidimensionnelles décrites dans le paragraphe
précédent visent à chercher ρ le minimum local de g définie
par : g(ρ) = f (x + ρd) qui assure de plus la décroissance de f .
D’autre part, l’application principale des méthodes de
recherche linéaire est à l’intérieur des algorithmes
d’optimisation multi-dimensionnelle. Trouver ρ signifie, qu’il
faudra calculer un grand nombre de fois la fonction g, et cela
peut être coûteux du point de vue du temps de calcul. Par
conséquent, dans la plupart des algorithmes d’optimisation
non linéaire, on ne fait pas de recherche linéaire exacte. On
cherche plutôt une valeur de ρ qui assure une décroissance
suffisante de f . Si tel est le cas, nous pouvons terminer la
recherche linéaire relativement loin de la solution optimale du
sous-problème unidimensionnelle en question.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 45/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Nous allons presenter trois règles les plus populaires de ce

type. Le principe commun à toutes ces règles est que ρ ne doit
pas choisi ni trop grand ni trop petit.
2.1) Règle d’Armijo
Considérons le problème minn f (x). Soit x ∈ IRn un point
x∈IR
courant et soit d une direction de descente (d T ∇f (x) < 0).
Le but est de réduire la valeur de f (x) par un pas ρ dans la
direction d :
f (x + ρd) < f (x).
Supposons que f est de classe C 1 , alors la fonction
g : ρ → f (x + ρd) est aussi de classe C 1 et on a
g(0) = f (x) et g 0 (0) = ∇f (x)T d < 0.
On a alors
g(ρ) − g(0) ≈ ρg 0 (0) < 0.
La règle d’Armijo basée sur cette condition est construite de la
façon suivante :
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 46/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Soit un réel 0 < m < 1. La règle est la suivante :

Règle d’Armijo
Si g(ρ) ≤ g(0) + mg 0 (0)ρ, alors ρ convient.
Si g(ρ) > g(0) + mg 0 (0)ρ, alors ρ est trop grand.

Remarque
Rappelons que la règle d’Armijo assure que le nouveau point
obtenu x 0 = x + ρd, vérifie f (x 0 ) < f (x) (propriété de
descente)

2.2 La règle de Goldstein

En ajoutant une deuxième inégalité à la règle d’Armijo on
obtient la règle de Goldstein, où m1 et m2 sont deux
constantes vérifiant 0 < m1 < m2 :

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 47/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Règle de Goldstein
Si g(ρ) < g(0) + m2 g 0 (0)ρ, alors ρ est trop petit.
Si g(ρ) > g(0) + m1 g 0 (0)ρ, alors ρ est trop grand.
Si g(0) + m2 g 0 (0)ρ ≤ g(ρ) ≤ g(0) + m1 g 0 (0)ρ, alors ρ
convient
Dans le cas quadratique on a
1
g(ρ) = aρ2 + g 0 (0)ρ + g(0), a > 0.
2
Le choix de m2 doit être tel que, le pas optimal vérifie la règle
de Goldstein. Le pas optimal ρ∗ vérifie g 0 (ρ∗ ) = 0, soit
0
ρ∗ = −ga(0) . On a donc
g 0 (0) ∗
g(ρ∗ ) = g(0) + ρ.
2
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 48/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Donc ρ∗ sera considéré comme satisfaisant si m2 ≥ 12 . Des

valeurs typiques utilisées dans la pratique sont m1 = 0.1 et
m2 = 0.7
Théorème
Soit f : IRn → IR coercive. Soit l’algorithme de gradient

xk+1 = xk − ρk ∇f (xk ),

où à chaque itération le pas ρk satisfait la règle de Goldstein

g(0) + m2 g 0 (0)ρk ≤ g(ρk ) ≤ g(0) + m1 g 0 (0)ρk ,

avec g(ρ) = f (xk − ρ∇f (xk )) et 0 < m1 < m2 < 1. Alors la

suite (xk ) est bornée, la suite (f (xk )) est décroissante et
convergente, et le vecteur ∇f (xk ) vérifie

lim k∇f (xk )k = 0.

k→+∞
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 49/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2.3) Règle de Wolfe

La règle de Wolfe fait appel au calcul de g 0 (ρ), elle est donc en
théorie plus coûteuse que la règle de Goldstein. Cependant
dans de nombreuses applications, le calcul du gradient ∇f (x)
représente un faible coût additionnel en comparaison du coût
d’évaluation de f (x), c’est pourquoi cette règle est très utilisée.
Règle de Wolfe
Si g(ρ) > g(0) + m1 g 0 (0)ρ, alors ρ est trop grand.
Si g(ρ) ≤ g(0) + m1 g 0 (0)ρ et g 0 (ρ) < m2 g 0 (0), alors ρ est
trop petit.
Si g(ρ) ≤ g(0) + m1 g 0 (0)ρ et g 0 (ρ) ≥ m2 g 0 (0), alors ρ
convient.
Dans cette règle, on s’assure que ρ n’est pas trop petit en
assurant que g 0 (ρ) a suffisamment augmenté.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 50/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Le choix de m1 et m2 n’est pas très critique. Des valeurs

courantes sont : m1 = 0.1 et m2 = 0.7.
Théorème
Soit f : IRn → IR bornée inférieurement et supposons que ∇f
satisfait la condition :

∀x, y k∇f (x) − ∇f (y)k ≤ kkx − yk,

où k est une constante.

Soit l’algorithme de gradient : xk+1 = xk − ρk ∇f (xk ), où à
chaque itération le pas ρk satisfait la règle de Wolfe

g(ρ) ≤ g(0) + m1 g 0 (0)ρ et g 0 (ρ) ≥ m2 g 0 (0)

avec 0 < m1 < m2 < 1. Alors la suite (xk ) converge vers un

point x ∗ , et on a ∇f (x ∗ ) = 0.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 51/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

IV) Méthodes pour l’optimisation avec contraintes

1) Méthodes par résolution des équations de KKT

Nous étudierons dans ce paragraphe une classe de méthodes
dont le principe commun consiste à résoudre les équations de
KKT par la méthode de Newton. Leur comportement
asymptotique est très intéressant, puisque, sous des
hypothèses appropriées, on obtient une vitesse de convergence
superlinéaire ou quadratique. Par contre elles devront être
généralement combinées avec d’autres méthodes pour assurer
la convergence globale.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 52/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

1.1 Cas des contraintes d’égalité

a) Méthodes de Newton
On cherche à résoudre

 min f (x)
s.à

(P) 1, ..., p
 hi (x) = 0, i =

x ∈ IRn
On sait que la recherche d’un point de KKT revient à résoudre
le système à n + p inconnues et n + p équation
 p
X
∇f (x) + λi ∇hi (x) = 0


 i=1
hi (x) = 0, i = 1, ..., p


Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 53/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Ce système est équivalent à

(
∇x L(x, λ) = 0
(S )
h(x) = 0

où p
X
L(x, λ) = f (x) + λi hi (x)
i=1

est le lagrangien associé au problème (P). La méthode de

Newton consiste, à partir d’un point (xk , λk ), à linéariser le
système (S ) et à définir (xk+1 , λk+1 ) comme la solution du
système linéarisé :
(
∇x L(xk , λk ) + ∇2x L(xk , λk )(xk+1 − xk ) + ∇h(xk )(λk+1 − λk ) = 0
h(xk ) + ∇h(xk )T (xk+1 − xk ) = 0.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 54/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

En posant Jk = ∇h(xk )T et
p
Hk = ∇2x L(xk , λk ) = ∇2 f (xk ) + λi ∇2 hi (xk ),
X

i=1

le système (S ) devient
! ! !
Hk JkT xk+1 − xk −∇f (xk )
(S ) =
Jk 0 λk+1 −h(xk )

Si on suppose que la matrice Hk est inversible,

! la solution
xk+1 −xk
explicite du système (S ) est =
λk+1
 
H −1 −H −1 J T [JH −1 J T ]−1 JH −1 H −1 J T [JH −1 J T ]−1 !
−∇f (xk )
× .
 

−h(xk )
[JH −1 J T ]−1 JH −1 −[JH −1 J T ]−1
Pour simplifier l’écriture, on a omis l’indice de l’itération k
pour les matrices Hk et Jk .
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 55/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Convergence
Supposons la qualification des contraintes et l’existence d’une
solution (x ∗ , λ∗ ). Supposons de plus, l’existence d’une
constante positive q telle que :

y T ∇2x L(x ∗ , λ∗ )y ≥ qkyk2 , ∀y telle que

y T ∇hi (x ∗ ) = 0, i = 1, ..., p.
Alors, la méthode de Newton converge de façon quadratique
vers (x ∗ , λ∗ ).

La méthode de Newton présente un certain nombre

d’inconvénients:
La suite (xk , λk ) peut ne pas converger si le point de
départ choisi est très loin de la solution (x ∗ , λ∗ ).
les équations de KKT sont aussi vérifiées pour les
maximums.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 56/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Si on veut remédier à ces inconvénients il faut disposer d’une

bonne estimation initiale de (x0 , λ0 ).
Remarque
La résolution des équation de KKT peut également se faire par
des méthodes quasi newtoniennes où on utilise à chaque
!
H JT
itération une approximation de l’inverse de . Ceci
J 0
évite d’avoir à calculer les dérivées seconde.
b) Méthodes de Wilson
Dans la méthode précédente, pour éviter les points
stationnaires qui ne sont pas des minimums, on peut faire
l’analyse suivante : si on note yk = xk+1 − xk on observe que
le système (S ) s’écrit

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 57/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

(
Hk yk + JkT λk+1 = −∇f (xk )
h(xk ) + Jk yk = 0.
Le vecteur yk est la solution du problème d’optimisation
quadratique suivant :

1 T
min y Hk y + ∇f (xk )T y
(Q) s.à 2
h(xk ) + Jk y = 0


et λk+1 est le multiplicateur de lagrange associé. Au lieu de

résoudre le système (S ), on peut donc résoudre le problème
quadratique (Q), ce qui permet d’éviter les points
stationnaires qui ne sont pas des minimums. La résolution de
ce problème peut se faire avec toute méthode adaptée aux
problèmes quadratiques. Cette extension de la méthode de
Newton est due à Wilson.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 58/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Remarque
La méthode de Wilson possède les mêmes propriétés de
convergence quadratique au voisinage de l’optimum que
la méthode de Newton.
La méthode présente des difficultés lorsque Hk n’est pas
définie positive.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 59/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

1.2 Cas des contraintes d’inégalité

On cherche à résoudre

 min f (x)
s.à

(P)
 gi (x) ≤ 0, i =n 1, ..., m

x ∈ IR
La méthode de Wilson se généralise très facilement au cas des
contraintes d’inégalité. Les contraintes linéarisées prennent la
forme
∇g(xk )T y + g(xk ) ≤ 0.
On peut alors utiliser une méthode consistant à résoudre
itérativement le problème quadratique

1 T
 min y Hk y + ∇f (xk )T y
(Q)  s.à 2
g(xk ) + Jk y ≤ 0
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 60/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2) Méthodes duales
On considère le pb d’optimisation (P)

 min f (x)
s.à

(P)
 gi (x) ≤ 0, i =n 1, ..., m

x ∈ IR
son dual est (
max θ(λ)
(D) s.à
λ≥0
n
λi gi (x)/x ∈ IRn }. L’intérêt du
X
où θ(λ) = inf{f (x) +
i=1
problème dual est double:
Il est concave (exercice)
Les contraintes sont simples à prendre en compte.
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 61/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2.1 Méthode d’Uzawa

Le principe de la méthode d’Uzawa est d’utiliser la méthode
du gradient pour maximiser la fonction duale, tout en tenant
compte de la contrainte λ ≥ 0 : cela donne la méthode

λk+1 = [λk + ρk ∇θ(λk )]+ = max(0, λk + ρk ∇θ(λk )).

L’utilisation de cette méthode suppose que la fonction duale

est différentiable. On a

θ(λ) = minn L(x, λ).

x∈IR

Notons xλ le vecteur tel que θ(λ) = L(xλ , λ), on a alors

dxλ
∇θ(λ) = ∇x L(xλ , λ) + ∇λ L(xλ , λ) = g(xλ ).
dλ
L’algorithme de la méthode est donc le suivant :
Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 62/66
Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Algorithme d’Uzawa
1 Poser k = 0 et λ0 = 0.
2 Déterminer xk solution du problème

min f (x) + λk g(x)

x∈IRn

3 Si max gi (xk ) <  alors on s’arrête.

4 Sinon, calculer λk+1 = [λk + ρk g(xk )]+
5 Faire k ← k + 1 et retourner en 2.
Au point 4 on peut choisir ρk fixe ou bien faire une recherche
linéaire. Dans le test d’arrêt choisi la valeur de  > 0 devra
être choisie prudemment : en effet, s’il n’existe pas de
point-selle on ne peut avoir xk ∈ S (S est l’ensemble réalisable
de (P)). Donc si  est trop petit l’algorithme ne s’arrêtera pas.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 63/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Problème avec contraintes d’inégalité et d’égalité

On considère le pb d’optimisation (P)


 min f (x)
s.à



(P)  gi (x) ≤ 0, i = 1, ..., m
 hi (x) = 0, i =

 1, ..., p
x ∈ IRn
son dual est (
max θ(λ, µ)
(D) s.à
λ≥0
n p
µi hi (x)/ x ∈ IRn }.
X X
où θ(λ, µ) = inf{f (x) + λi gi (x) +
i=1 i=1

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 64/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

Algorithme d’Uzawa
1 Poser k = 0, choisir λ0 ∈ IRm p
+ et µ0 ∈ IR .
2 Déterminer xk solution du problème

min f (x) + λk g(x) + µk h(x)

x∈IRn

3 Si le test d’arrêt est vérifier alors on s’arrête.

4 Sinon, calculer

λk+1 = [λk + ρk g(xk )]+

µk+1 = µk + ρk h(xk )
5 Faire k ← k + 1 et retourner en 2.

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 65/66

Algorithmes Méthodes pour l’optimisation sans contraintes Recherche linéaire Méthodes pour l’optimisation avec contraintes

2.2 Méthode d’Arrow et Hurwicz

Cette méthode est très voisine de la méthode d’Uzawa. Au

lieu de déterminer xk comme le minimum de L(x, λk ) on se
contente d’un pas dans la direction −∇x L(x, λk ): on définit
xk+1 par
xk+1 = xk − αk ∇x L(xk , λk ),
et λk+1 par
λk+1 = [λk + ρk g(xk )]+ .

Zakia ANKHILI Chapitre 4 Méthode d’optimisation ENSA (Marrakech) 2013 66/66