74
Cours d Optimisation Sans Contraintes Dr BELLOUFI MOHAMMED Octobre 2015 UniversitØ Mohamed ChØrif Messaadia de Souk-Ahras FacultØ des Sciences et Technologie DØpartement des MathØmatiques et Informatique Site web :http ://www.univ-soukahras.dz/fr/prole/mbellou E-mail : [email protected] ConformØment aux programmes LMD : MathØmatiques MathØmatiques et informatique

Cours d™Optimisation Sans Contraintes

  • Upload
    others

  • View
    4

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Cours d™Optimisation Sans Contraintes

Cours dOptimisation Sans Contraintes

Dr BELLOUFI MOHAMMED

Octobre 2015

Université Mohamed Chérif Messaadia de Souk-Ahras

Faculté des Sciences et Technologie

Département des Mathématiques et Informatique

Site web :http ://www.univ-soukahras.dz/fr/prole/mbellou E-mail : [email protected]

Conformément aux programmes LMD : Mathématiques

Mathématiques et informatique

Page 2: Cours d™Optimisation Sans Contraintes
Page 3: Cours d™Optimisation Sans Contraintes

0.1. OPTIMISATION SANS CONTRAINTES

OPTIMISATION SANS CONTRAINTESConformément aux programmesLMD : MathématiquesMathématiques et informatique

0.1 Optimisation sans contraintes

Unité d’enseignement : MéthodologieMatière : Optimisation sans contraintesCrédits :5Coeffi cient :2Objectifs de l’enseignement (Décrire ce que l’étudiant est censé avoir acquis comme

compétences après le succès à cette matière —maximum 3 lignes).

Connaissances préalables recommandées (descriptif succinct des connaissancesrequises pour pouvoir suivre cet enseignement —Maximum 2 lignes).

Contenu de la matière :Chapitre1 : Quelques rappels de calcul différentiel, Convexité1.1 Différentiabilité, gradient, matrice hessienne

1.2 Développement de Taylor

1.3 Fonctions convexes

Chapitre2 : Minimisation sans contraintes2.1 Résultats d’existence et d’unicité

2.2 Conditions d’optimalité du 1er ordre

2.3 Conditions d’optimalité du 2nd ordre

Chapitre3 : Algorithmes3.1 Méthode du gradient

3.2 Méthode du gradient conjugué

3.3 Méthode de Newton

3.4 Méthode de relaxation

3.5 Travaux pratiques

Mode d’évaluation : Examen (60%) , contrôle continu (40%)

Dr.BelloufiMohammed - U Souk Ahras Optimisation

Page 4: Cours d™Optimisation Sans Contraintes

Table des matières

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1 Quelques rappels de calcul différentiel, Convexité 5

1.1 Différentiabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Dérivée partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.2 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.3 Matrice Hessienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.4 Dérivée directionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.5 Direction de descente . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Développement de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.1 Propriétés des ensembles convexes . . . . . . . . . . . . . . . . . . . 13

1.3.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Travaux dirigés 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5 Suggestions et Corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Minimisation sans contraintes 19

2.1 Résultats d’existence et d’unicité . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.1 Conditions nécessaires d’optimalité . . . . . . . . . . . . . . . . . . 23

2.2.2 Conditions suffi santes d’optimalité . . . . . . . . . . . . . . . . . . 25

2.3 Travaux dirigés 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Suggestions et Corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Algorithmes 31

3.0.1 Convergence globale . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.0.2 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1 Méthode du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

i

Page 5: Cours d™Optimisation Sans Contraintes

TABLE DES MATIÈRES

3.1.1 Algorithme du Gradient . . . . . . . . . . . . . . . . . . . . . . . . 33

3.1.2 Méthode du gradient à pas constant . . . . . . . . . . . . . . . . . . 35

3.1.3 Méthode du gradient à pas optimal . . . . . . . . . . . . . . . . . . 36

3.2 Méthode du gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.1 Le principe général d’une méthode à directions conjuguées . . . . . 37

3.2.2 Méthode de gradient conjugué dans le cas quadratique . . . . . . . 39

3.2.3 Méthode du gradient conjugué dans le cas non quadratique . . . . . 46

3.3 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.2 Avantages et inconvénients . . . . . . . . . . . . . . . . . . . . . . . 49

3.4 Méthode de quasi Newton ou quasi-Newtonniennes . . . . . . . . . . . . . 51

3.4.1 Formules de mise à jour de l’approximation du Hessien . . . . . . . 52

3.4.2 Méthode de correction de rang un . . . . . . . . . . . . . . . . . . . 53

3.4.3 Méthode de Davidon Fletcher Powell (DFP) . . . . . . . . . . . . . 54

3.4.4 Méthode de Broyden, Fletcher, Goldfarb et Shanno(BFGS) . . . . . 57

3.4.5 Les méthodes de classe Broyden . . . . . . . . . . . . . . . . . . . . 59

3.5 Méthode de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.6 Travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.7 Travaux dirigés 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.8 Suggestions et Corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

ii

Page 6: Cours d™Optimisation Sans Contraintes

0.2. INTRODUCTION

0.2 Introduction

L’optimisation est une branche des mathématiques et de l’informatique en tant que

disciplines, cherchant à modéliser, à analyser et à résoudre analytiquement ou numérique-

ment les problèmes qui consistent à déterminer quelles sont la ou les solution(s) satisfaisant

un objectif quantitatif tout en respectant d’éventuelles contraintes.

Dans la vie courante, nous sommes fréquemment confrontés à des problèmes "d’op-

timisation" plus ou moins complexes. Cela peut commencer au moment où l’on tente de

ranger son bureau, de placer son mobilier, et aller jusqu’à un processus industriel, par

exemple pour la planification des différentes tâches. Ces problèmes peuvent être exprimés

sous la forme générale d’un "problème d’optimisation".

L’optimisation joue un rôle important en recherche opérationnelle (domaine à la fron-

tière entre l’informatique, les mathématiques et l’économie), dans les mathématiques ap-

pliquées (fondamentales pour l’industrie et l’ingénierie), en analyse et en analyse numé-

rique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution,

pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie

du contrôle et de la commande.

L’optimisation peut être définie comme la science qui détermine la meilleure solution à

certains problèmes mathématiquement définie, qui sont souvent des modèles de physique

réal. C’est une technique qui permet de "quantifier" les compromis entre des critères

parfois non commensurables ([2004]).

L’optimisation recouvre l’étude des critères d’optimalité pour les différents problèmes,

la détermination des méthodes algorithmiques de solution, l’étude de la structure de telles

méthodes et l’expérimentation de l’ordinateur avec ces méthodes avec vrais problèmes de

la vie ([1987]).

D‘un point de vue mathématique, l‘optimisation consiste à rechercher le minimum

ou le maximum d’une fonction avec ou sans contraintes.

L’optimisation possède ses racines au 18ième siècle dans les travaux de :

-Taylor, Newton , Lagrange, qui ont élaboré les bases des développements limités.

- Cauchy ([1847]) fut le premier à mettre en œuvre une méthode d’optimisation,méthode du pas de descente, pour la résolution de problèmes sans contrainte.

Il faut attendre le milieu du vingtième siècle, avec l’émergence des calculateurs et

surtout la fin de la seconde guerre mondiale pour voir apparaître des avancées spectacu-

laires en termes de techniques d’optimisation. A noter, ces avancées ont été essentiellement

obtenues en Grande Bretagne.

Aujourd’hui, tous les systèmes susceptibles d’être décrits par un modèle mathématique

sont optimisés. La qualité des résultats et des prédictions dépend de la pertinence du

Dr.BelloufiMohammed - U Souk Ahras 1 Optimisation

Page 7: Cours d™Optimisation Sans Contraintes

0.2. INTRODUCTION

modèle, de l’effi cacité de l’algorithme et des moyens pour le traitement numérique.

Les domaines d’applications sont extrêmement variés : optimisation d’un trajet, de

la forme d’un objet, d’un prix de vente, d’une réaction chimique, du contrôle aérien,

du rendement d’un appareil, du fonctionnement d’un moteur, de la gestion des lignes

ferroviaires, du choix des investissements économiques, de la construction d’un navire, etc.

L’optimisation de ces systèmes permet de trouver une configuration idéale, d’obtenir un

gain d’effort, de temps, d’argent, d’énergie, de matière première, ou encore de satisfaction.

Très loin de constituer une liste exhaustive, ces quelques exemples attestent de la

variété des formulations et préfigure la diversité des outils mathématiques susceptibles de

résoudre ces problèmes.

Plus formellement, l’optimisation est l’étude des problèmes qui s’expriment de la ma-

nière suivante.

Étant donné une fonction f : Rn → R, trouver un élément x de Rntel que f (x) ≤ f (x)

pour tout x ∈ R.On dit que l’on cherche à minimiser la fonction f sur l’ensemble R. La fonction f porte

divers noms : fonction-coût ou simplement coût, fonction-objectif ou simplement objectif,

critère, etc.

Cela permet de varier le vocabulaire.

L’ensemble Ω des points de R qui satisfont cette condition est appelé l’ensemble ad-missible et les points de Ω sont appelés les points admissibles du problème. On dit que

le problème est réalisable si Ω est non vide (l’ensemble admissible étant souvent défini de

manière implicite, son caractère non vide n’est pas nécessairement évident, ce qui justifie

le besoin de ce concept de réalisabilité).

Le point x est appelé solution du problème d’optimisation (ou minimum ou minimi-

seur). On l’appelle aussi parfois une solution globale pour le distinguer des notions locales

introduites ci-dessous.

L’optimisation est découpée en sous-disciplines qui se chevauchent, suivant la forme

de la fonction objectif et celle des contraintes : l’optimisation en dimension finie ou infinie

(on parle ici de la dimension de l’espace vectoriel des variables à optimiser), l’optimisa-

tion continue ou combinatoire (les variables à optimiser sont discrètes dans ce dernier

cas), l’optimisation différentiable ou non lisse (on qualifie ici la régularité des fonctions

définissant le problème), l’optimisation linéaire (fonctions affi nes), quadratique (objectif

quadratique et contraintes affi nes), semi-définie positive (la variable à optimiser est une

matrice dont on requiert la semi-définie positivité), copositive (la variable à optimiser

est une matrice dont on requiert la copositivité), conique (généralisation des disciplines

précédentes, dans laquelle on minimise une fonction linéaire sur l’intersection d’un cône

et d’un sous-espace affi ne), convexe (fonctions convexes), non linéaire, la commande op-

Dr.BelloufiMohammed - U Souk Ahras 2 Optimisation

Page 8: Cours d™Optimisation Sans Contraintes

0.2. INTRODUCTION

timale, l’optimisation stochastique (en) et robuste (en) (présence d’aléas), l’optimisation

multicritère (un compromis entre plusieurs objectifs contradictoires est recherché), l’op-

timisation algébrique (fonctions polynomiales), l’optimisation bi-niveaux, l’optimisation

sous contraintes de complémentarité, l’optimisation disjonctive (l’ensemble admissible est

une réunion d’ensembles), etc.

Cette abondance de disciplines provient du fait que pratiquement toute classe de pro-

blèmes modélisables peut conduire à un problème d’optimisation, pourvu que l’on y intro-

duise des paramètres à optimiser. Par ailleurs, les conditions d’optimalité de ces problèmes

d’optimisation apportent parfois des expressions mathématiques originales qui, par le mé-

canisme précédent, conduisent à leur tour à de nouveaux problèmes d’optimisation.

L’optimisation linéaire étudie le cas où la fonction objectif et les contraintes carac-

térisant l’ensemble A sont linéaires. C’est une méthode très employée pour établir les

programmes des raffi neries pétrolières, mais aussi pour déterminer la composition la plus

rentable d’un mélange salé, sous contraintes, à partir des prix de marché du moment.

L’optimisation linéaire en nombres entiers étudie les problèmes d’optimisation linéaire

dans lesquels certaines ou toutes les variables sont contraintes de prendre des valeurs

entières. Ces problèmes peuvent être résolus par différentes méthodes : séparation et

évaluation, méthode des plans sécants.

L’optimisation quadratique étudie le cas où la fonction objectif est une forme quadra-

tique (avec contraintes linéaires)

L’optimisation non linéaire étudie le cas général dans lequel l’objectif ou les contraintes

(ou les deux) contiennent des parties non linéaires, éventuellement non-convexes.

L’optimisation stochastique étudie le cas dans lequel certaines des contraintes dé-

pendent de variables aléatoires. En optimisation robuste, les aléas sont supposés être

situés dans des intervalles autour de positions nominales et on cherche à optimiser le

système soumis à de tels aléas, dans le pire des cas.

La programmation dynamique utilise la propriété qu’une solution se compose nécessai-

rement de sous-solutions optimales (attention : le contraire n’est pas vrai en général) pour

décomposer le problème en évitant l’explosion combinatoire. Elle est utilisable lorsque la

fonction objectif est une somme de fonctions monotones croissantes dont les arguments

sont des inconnues distinctes. C’est la programmation dynamique qui permet par exemple :

- aux avionneurs de trouver les plans de décollage optimaux de leurs engins,

- aux ingénieurs de bassin de répartir la production minière entre leurs différents puits,

- aux producteurs d’électricité de planifier la marche des usines hydroélectriques,

- aux media planners de répartir effi cacement un budget de publicité entre différents

supports.

Formellement on peut écrire ce problème noté (P ) de la manière suivante :

Dr.BelloufiMohammed - U Souk Ahras 3 Optimisation

Page 9: Cours d™Optimisation Sans Contraintes

0.2. INTRODUCTION

(P ) minimiser f(x) x ∈ Rn

Remarquons toute fois que comme on a

supx∈Rn

f (x) = − infx∈Rn

(−f (x))

alors le problème de maximisation d’une fonction f est équivalent au problème de mini-

misation de −f . L’équivalence veut dire ici que les solutions sont les mêmes et que lesvaleurs optimales sont opposées. En particulier, une méthode pour analyser et résoudre

un problème de minimisation pourra être utilisée pour analyser et résoudre un problème

de maximisation.

Parmi les plus anciennes méthodes utilisées pour résoudre les problèmes du type (P ),

on peut citer la méthode du Gradient conjugué.

De nombreuses contributions apparaissent ensuite dans les années soixante. G. Zouten-

dijk ([1960]), C. W. Carroll ([1961]), P. Wolfe ([1961]), R. Fletcher et M. J. D. Powell

([1963]),C. Reeves ([1964]),A. A. Goldstein ([1965]) et A. V. Fiacco et G. P. McCormick

([1968]) pour la programmation non linéaire ainsi que E. Polak et G. Ribière([1969]), B.T.

Polyak ([1969]) et J.F. Price ([1969]).

Le problème que l’on étudie ici celui de la recherche du minimum (maximum) d’une

fonction réelle f : Rn → R .Beaucoup de problèmes peuvent se formuler de cette manière .D’autre part, dans les

problèmes ou les variables x1, ..., xn sont astreintes à vérifier des conditions supplémen-

taires (du type : gi (xi) ≤ 0, i = 1, ...m ) on peut dans certaines conditions se ramener à

des problèmes d’optimisation sans contraintes.

Dr.BelloufiMohammed - U Souk Ahras 4 Optimisation

Page 10: Cours d™Optimisation Sans Contraintes

Chapitre 1

Quelques rappels de calculdifférentiel, Convexité

Dans ce chapitre, on définit et on introduit les outils fonctionnels de base nécessaires

pour l’optimisation sans contraintes.

1.1 Différentiabilité

On se place dans Rn, n <∞, considéré comme un espace vectoriel normé muni de lanorme euclidienne notée ‖.‖.Soit Ω un ouvert de Rn.

1.1.1 Dérivée partielle

Définition 1.1.1 Soit f : Rn → R une fonction continue. La fonction notée ∇if(x) :

Rn → R, également notée ∂f/∂xi est appelée iieme dérivée partielle de f et est définie par

limα→0

f (x1, ..., xi + α, ..., xn)− f (x1, ..., xi, ..., xn)

α.

Cette limite peut ne pas exister.

1.1.2 Gradient

Si les dérivées partielles ∂f/∂xi exixtent pour tout i, le gradient de f est défini de la

façon suivante.

5

Page 11: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

Définition 1.1.2 • On note par

(∇f(x))T =

(∂f

∂x1

, ...,∂f

∂xn

)(x)

,

le gradient de f au point x = (x1, .., xn).

Le gradient jouera un role essentiel dans le développement et l’analyse des algorithmes

d’optimisation.

Exemple 1.1.1 Soit f (x1, x2, x3) = ex1 + x21x3− x1x2x3. Le gradient de f est donné par

∇f (x1, x2, x3) =

ex1 + 2x1x3 − x2x3

−x1x3

x21 − x1x2

.

Remarque 1.1.1 i)∂f

∂0(x) = 0.

ii)∂f

∂xi(x) =

∂f

∂ei(x).

On note e1, e2, ...en les éléments de la base canonique de Rn, où ei est le vecteurde Rn donné par :

(ei)j = δij =

0 Si j 6= i

1 Si j = i∀i, j = 1, 2, ..., n,

(symboles de Kronecker).

Remarque 1.1.2 Nous rappellons aussi la formule :

∂f

∂h(x) = 〈5f(x), h〉 , ∀x ∈ Ω ∀h ∈ Rn.

Proposition. 1.1.1 (Gradient de la composée) Supposons qu’on deux ouverts Ω ⊂Rn et U ⊂ R et deux fonctions f : Ω→ R et g : U → R avec en plus f(Ω) ⊂ U (on peut

alors définir g f : Ω → R). Supposons que f, g sont de classe C1. Alors g f est ausside classe C1 avec en plus

∇(g f)(x) = g′(f(x))5 f(x) ∀x ∈ Ω .

Exemple 1.1.2 f (x1, x2) = x21x2 + 2, g (x) = 2x+ 1.

Dr.BelloufiMohammed - U Souk Ahras 6 Optimisation

Page 12: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

1.1.3 Matrice Hessienne

Définition 1.1.3 • On appelle Hessien de f la matrice symétrique de Mn(R)

H(x) = ∇(∇Tf)(x) = ∇2f(x) =

(∂2f

∂xi∂xj

)(x), i = 1, ..., n, j = 1, ..., n.

Alors

H(x) =

∂2f

∂x1∂x1

∂2f∂x1∂x2

· · · ∂2f∂x1∂xn

∂2f∂x2∂x1

∂2f∂x2∂x2

· · · ∂2f∂x2∂xn

......

. . ....

∂2f∂xn∂x1

∂2f∂xn∂x2

· · · ∂2f∂xn∂xn

.

Remarque 1.1.3 Si f ∈ C2(Ω) alors 52f(x) est une matrice symmétrique ∀x ∈ Ω

(c’est le Théorème de Schwarz).

Exemple 1.1.3 Soit f (x1, x2, x3) = ex1 +x21x3−x1x2x3. L’hessienne de f est donné par

H (x) =

ex1 + 2x3 −x3 2x1 − x2

−x3 0 −x1

2x1 − x2 −x1 0

.

Définition 1.1.4 • On dit que x∗ est un point stationnaire de f si ∇f(x∗) = 0.

Proposition. 1.1.2 (Lien entre ∇ et ∇2) a) La i-ème ligne de 52f(x) Jacobienne du

i-ème élément de 5f.b) On a

52f(x)h = ∇〈5f(x), h〉 , ∀x ∈ Ω ∀h ∈ Rn.

Preuve. a) évidenteb) On a :

∂xi〈∇f(x);h〉 =

∂xi

(n∑j=1

∂f

∂xj(x)hj

)

=

n∑i=1

∂2f

∂xixj(x)hj

= (52f(x)h)i .

Exemple 1.1.4 Si f : Rn → R est une fonction constante alors 5f = 52f = 0.

Dr.BelloufiMohammed - U Souk Ahras 7 Optimisation

Page 13: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

Soit f : Rn → R définie par

f(x) =< a, x > ∀x ∈ Rn,

où a ∈ Rn est un vecteur donné (c’est à dire, f est une fonction linéaire), Alors on calculefacilement :

∂f

∂xk= ak, donc

5f = a

(le gradient est constant).

Ceci nous donne

52f = 0.

Corollaire 1.1.1 Soit f : Rn → R donnée par

f(x) =< Ax;x > ∀x ∈ Rn.

où A ∈ Mn(R) est une matrice carrée, réelle, de taille n (c’est à dire, f est la fonction

quadratique associée à la matrice A). Alors pour un p ∈ 1, 2, ...n fixé, on peut écrire

f(x) =n∑

i,j=1

Ai,jxixj = Appx2p +

n∑j=1,j 6=p

Apjxpxj +n∑

i=1,i 6=p

Aipxixp +n∑

i,j=1,i 6=p,j 6=p

Aijxixj ,

ce qui nous donne

∂f

∂xp= 2Appxp +

n∑j=1,j 6=p

Apjxj +n∑

i=1,i 6=p

Aipxi =n∑j=1

Apjxj +n∑i=1

Aipxi = (Ax)p + (ATx)p.

Nous avons donc obtenu :

5f(x) = (A+ AT )x,∀x ∈ Rn.

On peut aussi écrire

∂f

∂xi(x) =

n∑k=1

(A+ AT )ikxk ∀i = 1, ..., n.

On a alors immédiatement :

∂2f

∂xi∂xj(x) = (A+ AT )ij, ∀i, j = 1, ..., n ,

Dr.BelloufiMohammed - U Souk Ahras 8 Optimisation

Page 14: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

c’est à dire

∇2f(x) = A+ AT , ∀x ∈ Rn.

Donc la hessienne de f est constante.

Remarque 1.1.4 En particulier, si A est symmétrique (c’est à dire A = AT ) alors

5〈Ax, x〉 = 2Ax, ∀x ∈ Rn.

52 〈Ax, x〉 = 2A, ∀x ∈ Rn.

1.1.4 Dérivée directionnelle

Définition 1.1.5 On appelle dérivée directionnelle de f dans la direction d au point x,notée δf(x, d), la limite (éventuellement ±∞) du rapport :

f(x+ hd)− f(x)

hlorsque h tend vers 0.

Autrement dit :

δf(x, d) = limh→0

f(x+ hd)− f(x)

h= ∇Tf(x)d.

Remarque 1.1.5 • Si ‖d‖ = 1 : la dérivée directionnelle est le taux d’accroissement de

f dans la direction d au point x.

Remarque 1.1.6 Pour tout x ∈ Ω et h ∈ Rn on note

∂f

∂h(x) = lim

t→0

1

t[f (x+ th)− f(x)] = g′(0),

(c’est la dérivée directionnelle de f en x de direction h) où on a noté g(t) = f(x+ th).

Remarque 1.1.7 • Le taux d’accroissement est maximal dans la direction du gradient• Le gradient indique la direction de la plus grande pente.

Exemple 1.1.5 Soit f (x1, x2, x3) = ex1 + x21x3 − x1x2x3 et soit

d =

d1

d2

d3

.

Dr.BelloufiMohammed - U Souk Ahras 9 Optimisation

Page 15: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

La dérivée directionnelle de f dans la direction d est

(d1 d2 d3)∇f (x1, x2, x3) = d1 (ex1 + 2x1x3 − x2x3)− d2x1x3 + d3

(x2

1 − x1x2

)ou ∇f (x1, x2, x3) est donné par

∇f (x1, x2, x3) =

ex1 + 2x1x3 − x2x3

−x1x3

x21 − x1x2

.

Définition 1.1.6 (Fonction différentiable) Soit f : Rn → R une fonction continue.

Si, pour tout d ∈ Rn, la dérivée directionnelle de f dans la direction d existe, alors lafonction f est dite différentiable.

Remarque 1.1.8 Cette noyion est parfois appelée Gateaux-différentiabilité , en ce

sens que d’autres type de différentiabilité peuvent etre définis (comme la différentiabilité

au sens Fréchet).

La dérivée directionnelle donne des informations sur la pente de la fonction dans la

direction d, tout comme la dérivée donne des informations sur la pente des fonctions

à une variable. Notamment, la fonction est croissante dans la diréction d si la dérivée

directionnelle est strictement positive et décroissante si elle est strictement négative. Dans

ce dernier cas, nous dirons qu’il s’agit d’une direction de descente.

1.1.5 Direction de descente

Soit f : Rn → R une fonction différentiable. Soient x, d ∈ Rn. La direction d est unedirection de descente en x si

dT 5 f(x) < 0.

Le terminologie <<direction de descente>> est justifiée par le théorème suivant.

Théorème 1.1.1 Soit f : Rn → R une fonction différentiable. Soient x ∈ Rn tel que5f(x) 6= 0 et d ∈ Rn. Si d est une direction de descente, alors il existe η > 0 tel que

f (x+ αd) < f (x) , ∀0 < α ≤ η .

De plus, pour tout β < 1, il existe η > 0 tel que

f (x+ αd) < f (x) + αβ 5 f(x)Td ,

pour tout 0 < α ≤ η.

Dr.BelloufiMohammed - U Souk Ahras 10 Optimisation

Page 16: Cours d™Optimisation Sans Contraintes

1.1. DIFFÉRENTIABILITÉ

Preuve. ([1])

Théorème 1.1.2 (plus forte pente) Soit f : Rn → R une fonction différentiable.

Soient x ∈ Rn et d∗ = 5f(x). Alors pour tout d ∈ Rn tel que ‖d‖ = ‖∇f (x)‖ , ona

dT 5 f(x) ≤ d∗T 5 f(x) = 5f(x)T 5 f(x).

Preuve. ([1])

Exemple 1.1.6 Soit f (x) = 12x2

1 + 2x22 et soit x = (1 1)T . Nous considérons trois direc-

tions

d1 = ∇f (x) =

(1

4

), d2 =

(1

1

)et d3 =

(−1

3

).

La dérivée directionnelle de f dans chacune de ces directions vaut :

dT1∇f (x) = 17,

dT2∇f (x) = 5,

dT3∇f (x) = 11.

Théorème 1.1.3 (Plus forte descente) Soit f : Rn → R une fonction différentiable.Soient x ∈ Rn et d∗ = −5 f(x). Alors pour tout d ∈ Rn tel que ‖d‖ = ‖∇f (x)‖ , on a

−5 f(x)T 5 f(x) = d∗T 5 f(x) ≤ dT 5 f(x),

et la diréction opposée au gradient est celle ou la fonction a la plus forte descente.

Preuve. ([1])

Exemple 1.1.7 Soit f (x) = 12x2

1 + 2x22 et soit x = (1 1)T . Nous considérons trois direc-

tions

d1 = −∇f (x) =

(−1

−4

), d2 =

(−1

−1

)et d3 =

(1

−3

).

La dérivée directionnelle de f dans chacune de ces directions vaut :

dT1∇f (x) = −17,

dT2∇f (x) = −5,

dT3∇f (x) = −11.

Dr.BelloufiMohammed - U Souk Ahras 11 Optimisation

Page 17: Cours d™Optimisation Sans Contraintes

1.2. DÉVELOPPEMENT DE TAYLOR

1.2 Développement de Taylor

La formule de Taylor est un outil important en convexité. Nous la rappelons dans le

cas général.

Soit Ω ⊂ Rn ouvert, f : Ω→ R, a ∈ Ω et h ∈ Rn tels que [a, a+ h]. Alors :

1. Si f ∈ C1(Ω) alors

i) Formule de Taylor à l’ordre 1 avec reste intégral

f(a+ h) = f(a) +

1∫0

〈∇f(a+ th), h〉 dt.

ii) Formule de Taylor - Maclaurin à l’ordre 1

f(a+ h) = f(a)+ < ∇f(a+ h), h > .

iii) Formule de Taylor - Young à l’ordre 1

f(a+ h) = f(a)+ < ∇f(a), h > +o(‖h‖).

2. Si f ∈ C2(Ω) alors

i) Formule de Taylor à l’ordre 2 avec reste intégral

f(a+ h) = f(a)+ < ∇f(a), h > +

1∫0

(1− t) < ∇2f(a+ th)h, h > dt.

ii) Formule de Taylor - Maclaurin à l’ordre 2

f(a+ h) = f(a)+ < ∇f(a);h > +1

2< ∇2f(a+ θh)h, h > avec 0 < θ < 1.

iii) Formule de Taylor - Young à l’ordre 2

f(a+ h) = f(a)+ < ∇f(a), h > +1

2< ∇2f(a)h, h > +o(‖h‖2).

Remarque 1.2.1 Dans la proposition précédente la notation o(‖h‖k) pour k ∈ N∗ signifieune expression qui tend vers 0 plus vite que ‖h‖k (c’est à dire, si on la divise par ‖h‖k,le résultat tend vers 0 quand ‖h‖ tend vers 0).

Théorème 1.2.1 Soit f : Ω→ R de classe Cn+1(Ω). Si le segment [a, a+ h] est contenu

dans U, on a :

f(a+ h) = f(a) + f ′(a).h+ ...+1

n!f (n) (a) (h)n +

1∫0

(1− t)n

n!f (n+1) (a+ th) (h)(n+1) dt.

( Reste integral)

Dr.BelloufiMohammed - U Souk Ahras 12 Optimisation

Page 18: Cours d™Optimisation Sans Contraintes

1.3. FONCTIONS CONVEXES

1.3 Fonctions convexes

La convexité est à la base une propriété géométrique. On voit assez bien ce qu’est un

objet convexe dans un espace à deux ou trois dimentions. nous allons maintenant montrer

comment cette propriété peut aussi s’appliquer aux fonctions de Rn dans R.

Définition 1.3.1 Un ensemble C ⊂ Rn est dit convexe si pour tout couple (x, y) ∈ C2 et

∀λ ∈ [0, 1] on a ;

λx+ (1− λ) y ∈ C.

1.3.1 Propriétés des ensembles convexes

la définition d’ensemble convexe peut s’enterpréter en disant que le segment reliantx et y doit être dans C.

Soit x1, x2, ..., xk ∈ Rn et tj telle que tj ≥ 0 etk∑j=1

tj = 1. Tout expréssion de la

forme

k∑j=1

tjxj.

S’appelle combinaison convexe des points xj ou barycentre.

tout entier est un ensemble convexe, de même qu’un singleton a .

soit la famille Cii=1...p d’ensembles convexes et S =

p⋂i=1

Ci. Alors S est convexe.

1.3.2 Fonction convexe

Définition 1.3.2 (fonction convexe) Soit C ⊆ Rn un ensemble convexe non vide. Unefonction f : C −→ R est convexe si et seulement si

∀x, y ∈ C, ∀t ∈ [0, 1] ; f(tx+ (1− t)y) ≤ tf(x) + (1− t)f(y).

Dr.BelloufiMohammed - U Souk Ahras 13 Optimisation

Page 19: Cours d™Optimisation Sans Contraintes

1.3. FONCTIONS CONVEXES

Une fonction f est concave si −f convexe. On dira que f est strictement convexe dansC si et seulement si :

∀x, y ∈ C, ∀t ∈ [0, 1] ; f(tx+ (1− t)y) < tf(x) + (1− t)f(y).

Définition 1.3.3 (Fonction fortement ou uniformément convexe de module υ > 0)Soit C ⊆ Rn un ensemble convexe non vide. Une fonction f : C → R est fortement ouuniformément convexe de module υ > 0 si

f(tx+ (1− t)y) ≤ tf(x) + (1− t)f(y)− υ

2t(1− t) ‖x− y‖2 , ∀x, y ∈ C2, ∀t ∈ [0, 1] .

Définition 1.3.4 (Fonction convexe différentiable) Soit C ⊆ Rn, f : Rn −→ R et

x ∈ int(C). f est dite différentiable au point x, s’il existe un vecteur A ∈ Rn et unefonction α : Rn → R telle que

f(x) = f(x) + A(x− x) + ‖x− x‖α(x, x− x),

où :α(x, x− x) −→x→x

0. On peut note le vecteur A comme suit :

A = Of(x) = (∂f(x)

∂x1

, ....,∂f(x)

∂xn).

Définition 1.3.5 (Fonction convexe deux foix différentiable) Soit C ⊆ Rn non videet f : Rn −→ R.est dite deux foix différentiable ou point x ∈ int(C) s’il existe un vecteur

Of(x) et une matrice symétrique H(x) d’ordre (n, n) appellèe matrice hessienne, et une

Dr.BelloufiMohammed - U Souk Ahras 14 Optimisation

Page 20: Cours d™Optimisation Sans Contraintes

1.3. FONCTIONS CONVEXES

fonction α : Rn → R tels que

∀x ∈ C : f(x) = f(x) + Of(x)T (x− x) +1

2(x− x)TH(x)(x− x) + ‖x− x‖2 α(x, x− x),

où :α(x, x− x) −→x→x

0.On peut écrire :

H(x) =

∂2f(x)

∂x1∂x1

∂2f(x)

∂x1∂x2

· · · ∂2f(x)

∂x1∂xn∂2f(x)

∂x2∂x1

∂2f(x)

∂x2∂x2

· · · ∂2f(x)

∂x2∂xn· · · · · ·· · · · · ·

∂2f(x)

∂xn∂x1

∂2f(x)

∂xn∂x2

· · · ∂2f(x)

∂xn∂xn

.

Dr.BelloufiMohammed - U Souk Ahras 15 Optimisation

Page 21: Cours d™Optimisation Sans Contraintes

1.4. TRAVAUX DIRIGÉS 1

1.4 Travaux dirigés 1

Exercice 01Montrer qu’une norme est convexe.

Exercice 02Montrer que la fonction indicatrice d’un ensemble K définie par

1K =

0 if x ∈ K,

+∞ sinon,est convexe si et seulement si K est convexe.

Exercice 03Soit U une partie convexe d’un espace vectoriel V . Montrer que f : U ⊂ V → R est

convexe si et seulement si l’ensemble suivant :

epi (f) = (ν, α) ∈ V × R | ν ∈ U, α ≥ f (ν)

est une partie convexe de V × R.Exercice 04Soit F une fonction de Rn dans R. Pour u et v fixés dans Rn on définit la fonction de

R∗+ vers R suivante :

∀λ > 0 Φ (λ) =F (u+ λv)− F (u)

λ.

Montrer que si F est convexe alors Φ est croissante.

Exercice 05Soit f une fonction de R dans R dérivable sur l’intervalle ]0, 1]. On suppose que f ′

n’est pas bornée sur ]0, 1]. Montrer que f n’est pas lipschitzienne sur [0, 1].

Exercice 06Soit a une forme bilinéaire symétrique de Rn × Rn dans R.a) Montrer que l’on peut trouver une matrice symétrique A d’ordre n telle que :

∀u, v ∈ Rn a (u, v) = (Au, v) .

b) Calculer le gradient et la dérivée seconde (hessien) de la fonctionnelle J définie sur

Rn par :J(v) = 1

2(Av, v)− (b, v) , où b ∈ Rn est fixé.

(c) À quelle condition sur A, la fonction J est-elle convexe ? strictement convexe ?

Exercice 07Soit f une fonction convexe de Rn dans R. Montrer que :

Dr.BelloufiMohammed - U Souk Ahras 16 Optimisation

Page 22: Cours d™Optimisation Sans Contraintes

1.5. SUGGESTIONS ET CORRIGÉS

∀ (λi)1≤i≤p ∈ (R+)p tq

p∑i=1

λi = 1, ∀ (xi)1≤i≤p ∈ (Rn)p, f(

p∑i=1

λixi

)≤

p∑i=1

λif (xi) .

1.5 Suggestions et Corrigés

Exercice 01Soit N une norme d’un espace vectoriel E. Soient x, y ∈ E et t ∈ [0, 1].

N(tx+ (1− t)y) = N(tx) +N((1− t)y) = tN(x) + (1− t)N(y).

N est donc convexe.

Exercice 02a) Supposons K convexe et soient x, y ∈ Rn et t ∈ [0, 1].

—Si x et y sont dans K alors tx+ (1− t)y est dans K et

IK(tx+ (1− t)y) = 0 = t IK(x)︸ ︷︷ ︸=0 car x∈K

+ (1− t) IK(y)︸ ︷︷ ︸=0 car y∈K

.

—Si x (ou y) n’est pas dans K, alors IK(x) (ou IK(y)) = +8, et l’inegalité de convexité

est trivialement verifiée.

(b) Reciproquement. Soient x, y ∈ K et t ∈ [0, 1] ; par convexite de IK

IK(tx+ (1− t)y) ≤ 0 ≤ t IK(x)︸ ︷︷ ︸=0 car x∈K

+ (1− t)IK(y)︸ ︷︷ ︸ = 0

=0 car y∈K

.

Comme IK ne prend que les valeurs 0 ou +8, IK(tx+(1−t)y) = 0 et tx+(1−t)y) ∈ K.Exercice 03(a) Supposons f convexe ; soient (u, α) et (v, β) dans épi(f) et t ∈ [0, 1]. Comme U

est convexe, tu+ (1− t)v ∈ U etf(tu+ (1− t)v) = tf(u) + (1− t)f(v) = tα + (1− t)β ;donc t(u, α) + (1− t)(v, β) ∈épi(f).

(b) Reciproquement. ´

Comme (u, f(u)) et (v, f(v)) sont dans épi(f), t(u, f(u)) + (1− t)(v, f(v)) aussi.

La convexité de f en découle.

Exercice 04Soient λ1 ≥ λ2 > 0. Posons t = λ1

λ2∈ ]0, 1] .

F (u+ λ2v) = F (u+ tλ1v) = F ((1− t)u+ t(u+ λ1v))

≤ (1− t)F (u) + tF (u+ λ1v).

Dr.BelloufiMohammed - U Souk Ahras 17 Optimisation

Page 23: Cours d™Optimisation Sans Contraintes

1.5. SUGGESTIONS ET CORRIGÉS

Donc

F (u+ λ2v)− F (u) ≤ t(F (u+ λ1v)− F (u)) =λ1

λ2

(F (u+ λ1v)− F (u)),

c’est-à-dire Φ (λ1) ≤ Φ (λ2) .

Exercice 05On montre que si f est lipschitzienne sur [0, 1] et dérivable, alors f0 est bornée sur

]0, 1] :

Soit x ∈ ]0, 1] et h assez petit pour que x−h ∈ [0, 1]. Comme f est lipschitzienne sur

]0, 1]

‖f(x− h)− f(x)‖ ≤ k |h| ,

où k est indépendant de x. En divisant et avec h → 0, on obtient que la dérivée à

gauche est bornée. On procède de même avec la dérivée à droite (sauf en 1).

Exercice 06a) On applique le théorème de représentation de Riesz à l’application linéaire a(u,·) :

v 7−→ a(u, v), pour u fixé. On définit ainsi une forme linéaire Au ; on voit facilement que

u 7−→ Au est linéaire : Au = Au.

b) ∇J(v) = Av − b et D2J(v) = A.

Exercice 07On raisonne par récurrence : c’est vrai pour p = 2. Supposons que c’est vrai pour p−1.

Soit (λi)1≤i≤p ∈ (R+)p tel quep∑i=1

λi = 1. Il existe donc i0 tel que λi0 6= 0. Posons

µ =p∑

i=1, i 6=i0λi. Il est clair que λi0 ,µ ∈ ]0, 1[ et λi0 +µ = 1. Soit (xi)1≤i≤p ∈ Rp. On appelle

x le barycentre des points (λi, xi) i 6=i0 de sorte quep∑

i=1, i 6=i0λixi = µx La convexité de f

donne

f

(p∑i=1

λixi

)= f (µx+ λi0xi0) ≤ µf (x) + λi0f (xi0) .

comme x =p∑

i=1, i 6=i0

λiµxi, on utilise l’hypothèse de récurrence pour conclure.

Dr.BelloufiMohammed - U Souk Ahras 18 Optimisation

Page 24: Cours d™Optimisation Sans Contraintes

Chapitre 2

Minimisation sans contraintes

Soit f : Rn → R . On appelle problème de minimisation sans contraintes le problémesuivant

(P )

minx∈Rn

f(x) .

L’étude de ces problèmes est importante pour des raisons diverses. Beaucoup de problèmes

d’optimisation avec contraintes sont transformés en des suites de problèmes d’optimisation

sans contraintes (multiplicateur de Lagrange, méthodes des pénalités, . . .). Létude des

problèmes d’optimisation sans contraintes trouve aussi des applications dans la résolution

des systèmes non linéaires. Une grande classe d’algorithmes que nous allons considérer

pour le problème d’optimisation sans contraintes ont la forme générale suivante

x0 étant donnée, calculer xk+1 = xk + αkdk, (2.1)

le vecteur dk s’appelle la direction de descente, αk le pas de la méthode à la k-iéme

itération. En pratique, on s’arrange presque toujours pour avoir l’inégalité suivante

f(xk+1) ≤ f(xk),

qui assure la décroissance suffi sante de la fonction objectif f . De tels algorithmes sont

souvent appellés méthodes de descente. Essentiellement la différence entre ces algorithmes

réside dans le choix de la direction de descente dk, cette direction étant choisie nous

sommes plus où moins ramenés à un problème unidimensionnel pour la détermination de

αk. Pour s’approcher de la solution optimale du problème (P ) (dans le cas général, c’est

un point en lequel ont lieu peut être avec une certaine précision les conditions nécessaires

d’optimalité de f), on se déplace naturellement à partir du point xk dans la direction de la

décroissance de la fonction f . L’optimisation sans contraintes a les propriétés suivantes :

19

Page 25: Cours d™Optimisation Sans Contraintes

2.1. RÉSULTATS D’EXISTENCE ET D’UNICITÉ

- toutes les méthodes nécessitent un point de départ x0.

- les méthodes déterministes convergent vers le minimum local le plus proche.

- plus vous saurez sur la fonction (gradient, hessien) plus la minimisation sera effi cace.

Considérons le problème d’optimisation sans contraintes (P ).

Définition 2.0.1 Soit f : Rn → R, une fonction continûment différentiable.a) soit x ∈ Rn. x est dite solution optimale globale de (P ) si et seulement si :

∀x ∈ Rn, f(x) ≤ f(x).

b) soit x ∈ Rn. x est dite solution optimale locale de (P ) si et seulement s’il existe un

voisinage Vε(x) de x tel que

f(x) ≤ f(x), ∀x ∈ Vε(x).

c) soit x ∈ Rn. x est dite solution optimale stricte de (P ) si et seulement s’il existe

un voisinage Vε(x) de x tel que

f(x) < f(x), ∀x ∈ Vε(x) et x 6= x .

2.1 Résultats d’existence et d’unicité

Avant d’étudier les propriétés de la solution (ou des solutions) de (P) il faut s’assurer

de leur existence. Nous donnerons ensuite des résultats d’unicité.

Définition 2.1.1 On dit que f : Rn → R est coercive silim

‖x‖→+∞f (x) = +∞.

Ici ‖·‖ désigne une norme quelconque de Rn. On notera ‖·‖p (p ∈ N) la norme lp de

Rn :

∀x = (x1, ..., xn) ∈ Rn ‖x‖p =

[n∑i=1

|xi|p] 1p

.

La norme infinie de Rn est

∀x = (x1, ..., xn) ∈ Rn ‖x‖∞ = max1≤i≤n

|xi|.

Théorème 2.1.1 (Existence) Soit f : Rn → R ∪ +∞ propre, continue et coercive.Alors (P) admet au moins une solution.

Dr.BelloufiMohammed - U Souk Ahras 20 Optimisation

Page 26: Cours d™Optimisation Sans Contraintes

2.1. RÉSULTATS D’EXISTENCE ET D’UNICITÉ

Preuve. [09]- Soit d = inf(P); d < +∞ car f est propre. Soit (xp)p∈N ∈ Rn une suite minimisante,

c’est-à-dire telle que

limp→+∞

f (xp) = d.

Montrons que (xp) est bornée.

Si ce n’était pas le cas on pourrait extraire de cette suite une sous-suite (encore notée

(xp)) telle limp→+∞

‖xp‖ = +∞ . Par coercivité de f on aurait limp→+∞

f (xp) = +∞ ce qui

contredit le fait que limp→+∞

f (xp) = d < +∞.Comme (xp) est bornée, on peut alors en extraire une sous-suite (encore notée (xp))

qui converge vers x ∈ Rn Par continuité de f , on a alorsd = lim

p→+∞f (xp) = f (x).

En particulier d > −∞ et x est une solution du problème (P).

Théorème 2.1.2 (Unicité) Soit f : Rn → R ∪ +∞ strictement convexe. Alors leproblème (P) admet au plus une solution.

Preuve. [09]- Supposons que f admette au moins un minimum m et soient x1 6= x2 (dans Rn)

réalisant ce minimum :f (x1) = f (x2) = m. Par stricte convexité de la fonction f on a

alors :

f

(x1 + x2

2

)<

1

2(f (x1) + f (x2)) = m ;

ceci contredit le fait que m est le minimum. Donc x1 = x2.

Donnons pour terminer un critère pour qu’une fonction soit strictement convexe et

coercive :

Théorème 2.1.3 Soit J une fonction C1 de Rn dans R. On suppose qu’il existe α > 0

tel que

∀(x, y) ∈ Rn × Rn (∇f (x)−∇f (y) , x− y) ≥ α ‖x− y‖2 (2.2)

Alors J est strictement convexe et coercive ; en particulier le problème (P) admet une

solution unique .

Preuve. [09]- La condition (2.2) implique que ∇J est monotone et que f est convexe. De plus on

a la stricte convexité de J . Enfin J est coercive : en effet, appliquons la formule de Taylor

avec reste intégral

f(y) = f(x) +

1∫0

d

dtf (x+ t(y − x)) dt = f(x) +

1∫0

(∇f (x+ t(y − x)) , y − x) dt.

Dr.BelloufiMohammed - U Souk Ahras 21 Optimisation

Page 27: Cours d™Optimisation Sans Contraintes

2.2. CONDITIONS D’OPTIMALITÉ

Donc

f(y) = f(x) + (∇f (x), y − x) +

1∫0

(∇f (x+ t(y − x))−∇f (x) , y − x) dt. (2.3)

D’après (2.2) on obtient

f(y) ≥ f(x) + (∇f (x), y − x) +

1∫0

tα ‖x− y‖2 dt.

Finalement

f(y) ≥ f(x)− ‖∇f(x)‖ ‖y − x‖+α

2‖x− y‖2 .

Fixons x = 0 par exemple ; il est alors clair que f est coercive.

Par conséquent, f admet un minimum unique x∗ sur Rn caractérisé par∇f(x∗) = 0.

La condition (2.2) nous amène à la définition suivante :

Définition 2.1.2 (Fonction elliptique) On dit que f : Rn → R est elliptique si lacondition (2.2) est vérifiée, c’est-à-dire

∃α > 0 tel que ∀(x, y) ∈ Rn × Rn (∇f (x)−∇f (y) , x− y) ≥ α ‖x− y‖2.

α est la constante d’ellipticité.

Proposition. 2.1.1 Une fonction f : Rn → R deux fois différentiable sur Rn est ellip-tique si et seulement si

∀(x, y) ∈ Rn × Rn(D2f (x) y, y

)≥ α ‖y‖2 .

Preuve. [09]- On utilise de nouveau la formule de Taylor appliquée à la fonction ϕ : t → ϕ(t) =

f(x+ ty). La démonstration est laissée au lecteur.

Il faut maintenant donner des conditions pour pouvoir calculer la (ou les) solutions.

On va chercher à montrer que cette solution est solution de certaines équations, de sorte

qu’il sera plus facile de la calculer.

2.2 Conditions d’optimalité

Les conditions d’optimalité sont des équations, des inéquations ou des propriétés que

vérifient les solutions de (P ) (conditions nécessaires ) ou qui assure à un point d’être

solution de (P ) (condition suffi sante). Elles traduisent ainsi l’expression de l’optimalité

locale sous une forme analytique. Ces conditions sont utiles pour :

Dr.BelloufiMohammed - U Souk Ahras 22 Optimisation

Page 28: Cours d™Optimisation Sans Contraintes

2.2. CONDITIONS D’OPTIMALITÉ

- vérifier l’optimalité éventuelle d’un point x ∈ Rn, voir si c’est un minimum, unmaximum où un point stationnaire.

- calculer les solutions de (P ).

- mettre en œuvre des méthodes numériques permettant de résoudre (P ).

- définir des tests d’arrêts des itérations dans les algorithmes de résolution de (P ).

On parlera de conditions du premier ordre lorsque celles-ci ne font intervenir que des

dérivées premières de f . Quant aux conditions du second ordre, elles font intervenir les

dérivées premières et secondes de f .

2.2.1 Conditions nécessaires d’optimalité

Etant donné un point x, la propriété de différentiabilité continue de la fonction f

fournit une première manière de caractériser une solution optimale.

- Conditions nécessaires d’optimalité du premier ordre

Théorème 2.2.1 Soit f : Rn → R telle que f soit différentiable au point x ∈ Rn. Soitd ∈ Rn telle que ∇f(x)td < 0. Alors il existe δ > 0 tel que f(x + αd) < f(x) pour tout

α ∈]0, δ[. La direction d s’appelle dans ce cas direction de descente.

Preuve. [09]Comme f est différentiable en x alors

f(x+ αd) = f(x) + α∇f(x)td+ α ‖d‖λ(x;αd),

où λ(x;αd)→ 0 pour α→ 0. Ceci implique :

f(x+ αd)− f(x)

α= ∇f(x)td+ ‖d‖λ(x;αd), α 6= 0,

et comme ∇f(x)td < 0 et λ(x;αd)→ 0 pour α→ 0, il existe δ > 0 tel que

∇f(x)td+ ‖d‖λ(x;αd) < 0 pour tout α ∈]0, δ[,

et par conséquent on obtient :

f(x+ αd) < f(x) pour tout α ∈]0, δ[.

Théorème 2.2.2 Soit f : Rn → R différentiable au point x ∈ Rn. Si x est un minimumlocal de (P ) alors ∇f(x) = 0.

Dr.BelloufiMohammed - U Souk Ahras 23 Optimisation

Page 29: Cours d™Optimisation Sans Contraintes

2.2. CONDITIONS D’OPTIMALITÉ

Preuve. [09]On démontre par l’absurde, on suppose que ∇f(x) 6= 0.

Si on suppose d = −∇f(x), on obtient :

∇f(x)t.d = −‖∇f(x)‖2 < 0,

et par le théorème 2.2.1, il existe δ > 0 tel que

f(x+ αd) < f(x), ∀α ∈ ]0, δ[ .

ce qui donne une contradiction avec le fait que x est un minimum local, d’où ∇f(x) = 0.

-Conditions nécessaires d’optimalité du second ordre

Définition 2.2.1 a) Une matrice symétrique A est dite semi définie positive si :

∀d ∈ Rn, dtAd ≥ 0.

b) Une matrice symétrique A est dite définie positive si :

∀d ∈ Rn, d 6= 0, dtAd > 0.

Théorème 2.2.3 Soit f : Rn → R deux fois différentiable au point x ∈ Rn. Si x est unminimum local de (P ) alors ∇f (x) = 0 et la matrice hessienne de f au point x, qu’on

note H (x), est semi définie positive.

Preuve. [09]Soit d ∈ Rn quelconque, f étant deux fois différentiable au point x, on aura pour tout

α 6= 0

f(x+ αd) = f(x) +1

2α2dtH(x)d+ α2 ‖d‖2 λ(x, αd),

avec λ(x, αd)→ 0, quand α→ 0.

Ceci implique

f (x+ λd)− f (x)

α2=

1

2dtH (x) d+

∥∥d2∥∥α (x, αd) ,

ainsi x est un optimum local, il existe alors δ > 0 tel que

f (x+ λd)− f (x)

α2≥ 0, ∀α ∈ ]0, δ[ .

Dr.BelloufiMohammed - U Souk Ahras 24 Optimisation

Page 30: Cours d™Optimisation Sans Contraintes

2.2. CONDITIONS D’OPTIMALITÉ

Comme x est un minimum local alors f(x+ αd) ≥ f(x) pour α suffi samment petit, d’où

1

2dtH(x)d+ ‖d‖2 λ(x;αd) ≥ 0 pour α petit.

En passant à la limite qund α → 0, on obtient que dtH(x)d ≥ 0, d’où H(x) est semi

définie positive.

2.2.2 Conditions suffi santes d’optimalité

Les conditions données précédemment sont nécessaires (si f n’est pas convexe), c’est-

à-dire qu’elle doivent être satisfaites pour tout minimum local, cependant, tout point

vérifiant ces conditions n’est pas nécessairement un minimum local. Le théorème 1.7 sui-

vant établit une condition suffi sante pour qu’un point soit un minimum local, si f deux

fois différentiable.

Théorème 2.2.4 Soit f : Rn → R deux fois différentiable au point x ∈ Rn. Si ∇f (x) = 0

et H (x) est définie positive alors x est un minimum local strict de (P ) .

Preuve. [09]

f étant deux fois différentiable au point x, on aura pour tout x ∈ Rn

f (x) = f (x) +1

2(x− x)tH (x) (x− x) + ‖(x− x)‖2 α (x, (x− x)) ,

avec

α (x, (x− x)) →x→x

0 (∇f (x) = 0) .

Supposons que x n’est pas un optimum local strict. Alors il existe une suite xkk∈N telleque xk 6= x : ∀k, et

xk 6= x : ∀k, xk →k→∞

x et f (xk) ≤ f (x) .

Prenons x = xk, divisons le tout par ‖(x− x)‖2

et notons dk =(x− x)

‖(x− x)‖ , ‖dk‖ = 1, on obtient

f (xk)− f (x)

‖(xk − x)‖2 =1

2dtkH (x) dk + λ (x, (xk − x)) , λ (x, (xk − x)) →

k→∞0

Alors1

2dtkH (x) dk + λ (x, (xk − x)) ≤ 0, ∀k.

Dr.BelloufiMohammed - U Souk Ahras 25 Optimisation

Page 31: Cours d™Optimisation Sans Contraintes

2.2. CONDITIONS D’OPTIMALITÉ

D’autre part la suite dkk∈N est bornée (‖dk‖ = 1, ∀n). Donc il existe une sous suitedkk∈N1⊂N telle que

dk →k→∞,k∈N1

d.

Finalement lorsque k →∞, k ∈ N1, on obtient

1

2dH (x) d ≤ 0.

La dernière relation et le fait que d 6= 0(∥∥∥d∥∥∥ = 1

)impliquent que la matrice hessienne

H (x) n’est pas définie positive. Ceci est en contradiction avec l’hypothèse.

cas convexe

Théorème 2.2.5 Soit f : Rn → R telle que f est convexe et différentiable. Alors x est

un minimum globale de f si et seulement si

∇f(x) = 0.

Remarque 2.2.1 Dans le cas ou f est convexe, alors tout minimum local est aussi glo-

bale. De plus si f est strictement covexe, alors tout minimum local devient non seulement

global mais aussi unique.

Dr.BelloufiMohammed - U Souk Ahras 26 Optimisation

Page 32: Cours d™Optimisation Sans Contraintes

2.3. TRAVAUX DIRIGÉS 2

2.3 Travaux dirigés 2

Exercice 01Les fonctions f suivantes sont-elles coercives ?

a) f : R→ R définie par f (x) = x3 + x2 + 1.

b) f : Rn → R définie par f (x) = (a, x) + b avec a ∈ Rn et b ∈ R.c) f : R2 → R définie par f (x) = 2x2

1 + x2 − 1.

d) f : R2 → R définie par f (x) = 2x21 + x3

2 + 2x22.

e) f : R2 → R définie par f (x) = x21 + x2

2 − 1000x1 − 5000.

Exercice 02Soit A une matrice symétrique définie positive à coeffi cients réels. Montrer qu’il existe

une constante α > 0 telle que

∀v ∈ Rn (Av, v) ≥ α ‖v‖2 ,

où (., .) est le produit scalaire de Rn et ‖.‖ la norme euclidienne associée.Exercice 03Montrer par un exemple que la condition ∇f = 0 est une condition nécessaire d’op-

timalité et pas suffi sante.

Exercice 04Trouver les minima et les maxima sur R2 de la fonction f définie sur R2 par :

a) f(x1, x2) = x21 − x1x2 + 1

6x3

2,

b) f(x1, x2) = x21 − 2x1x2 + 1,

c) f(x1, x2) = x31 + x3

2 − 9x1x2 + 27.

Exercice 05Soit J (v) = 1

2(Av, v) − (b, v)où A est une matrice symétrique de Rn dans Rn et v

∈ Rn, une fonctionnelle quadratique de Rn dans R. Démontrer les propositions suivantes :a) J est convexe si et seulement si A est semi-définie positive.

b) J est strictement convexe si et seulement si A est définie positive.

c) ∃u ∈ Rn tel que : ∀ v ∈ Rn − u J (u) < J (v) si et seulement si A est définie

positive.

d) ∃u ∈ Rn tel que : ∀ v ∈ Rn J (u) ≤ J (v) si et seulement si A est semi-définie

positive et l’ensemble w ∈ Rn | Aw = b n’est pas vide.(e) Si la matrice A est semi-d´efinie positive et si l’ensemble w ∈ Rn | Aw = b est

vide, alors infv∈Rn J (v) = −∞.Exercice 06Chercher les dimensions d’un wagon rectangulaire non couvert (ou d’une caisse sans

Dr.BelloufiMohammed - U Souk Ahras 27 Optimisation

Page 33: Cours d™Optimisation Sans Contraintes

2.4. SUGGESTIONS ET CORRIGÉS

couvercle) telles que pour un volume donné V , la somme des aires des côtés et du plancher

soit minimale.

Exercice 07On se propose d’approcher un nuage de points donnés par les couples de réels (ti, xi),

i ∈ 1, ..., N par une parabole d’équation x(t) = at2 + bt + c où a, b et c sont trois réels

à déterminer. Autrement dit, on fait une régression “parabolique”.

(a) Exprimer le problème ci-dessus sous forme de problème de minimisation au sens des

moindres carrés. On précisera en particulier la fonction coût, les inconnues et l’ensemble

des contraintes.

(b) Ce problème de minimisation a-t’il une solution ? Pourquoi ? Est-elle unique ?

(c) Ecrire le système d’optimalité permettant de trouver le minimum.

On notera Sk la quantité Sk =N∑i=1

tki .

2.4 Suggestions et Corrigés

Exercice 01a) Non car lim

x→−∞J(x) = −∞.

b) Si a = 0 alors J est constante et ne peut pas etre coercive. Si a 6= 0, il existe

i0, 1 ≤ i0 ≤ n tel que ai0 = 0. On prend la suite xk = −kai0ei0 (Où ei est le i eme vecteurde base). Lorsque k → +∞, on a ‖xk‖ → +∞ et J(xk) → −∞. J n’est donc jamaiscoercive.

3. Non : prendre la suite xn = (0,−n).

4. Non : prendre la suite xn = (0,−n).

5. Oui car J(x1, x2) = (x1 − 500) + x2 − 255000.

Exercice 02A est symétrique, donc il existe une base de vecteurs propres orthonormés (ui)i=1,...,n.

les valeurs propres associées (λi)i=1,...,n sont strictement positives puisque A est définie

positive. Soit x =n∑i=1

xiui dans Rn. Nous avons

(Ax, x) =n∑i=1

λixixj (ui, uj) =n∑i=1

λix2i ≥ λmin ‖x‖2.

La constante peut être prise égale à la plus petite valeur propre λmin > 0.

Exercice 03Il suffi t de consid´erer la fonction de R vers R définie par f(x) = x3.

Exercice 04

a) Il y a deux points critiques : (0, 0) et (12, 1). La matrice hessienne vaut

[2 −1

−1 x2

].

Dr.BelloufiMohammed - U Souk Ahras 28 Optimisation

Page 34: Cours d™Optimisation Sans Contraintes

2.4. SUGGESTIONS ET CORRIGÉS

Pour x2 = 0, la matrice a deux valeurs propres de signes différents. Le point (0, 0) n’est

ni un minimum, ni un maximum. Pour x2 = 1, la matrice est d2finie positive. Le point

(12, 1) est un minimum strict.

b) Le point (0, 0) est un point critique mais ce n’est ni un minimum, ni un maximum.

c) Les deux points critiques sont (0, 0) et (3, 3). Le point (0, 0) n’est ni un maximum

ni un minimum car la matrice hessienne n’est ni semi-positive ni semi-négative. (3, 3) est

un minimum strict.

Exercice 05Un rapide calcul donne pour tous u, v ∈ Rn et t ∈ [0, 1] :

J(tu+ (1− t)v)− tJ(u)− (1− t)J(v) =t(t− 1)

2(A(u− v), u− v).

D’où a) et b).

La question c) est une application directe du cours.

d) Soient u, v ∈ Rn et t > 0 :

J(u+ tv)− J(u) = t(Au− b, v) +t2

2(Au, u). (B.1)

S’il existe u ∈ Rn tel que : ∀v ∈ Rn, J(u) ≤ J(v), ( B.1) donne après division par t

∀v ∈ Rn (Au− b, v) +t

2(Au, u) ≥ 0.

En faisant tendre t vers 0 on voit que (Au− b, v) ≥ 0 pour tout v et donc Au− b = 0

(l’ensemble w ∈ Rn | Aw = b n’est donc pas vide) ; par conséquent

∀v ∈ Rn ,∀t > 0t

2(Au, u) ≥ 0,

ce qui signifie que A est semi-définie positive.

Réciproquement, on choisit u dans l’ensemble w ∈ Rn | Aw = b qui n’est pas vide.Si de plus A est semi-définie positive, la relation ( B.1) montre que J(u) ≤ J(u+ tv)

pour tout v ∈ Rn.e) C’est en partie la contraposée de d). Elle s’en déduit immédiatement en supposant

par exemple que inf J(v) > −∞.Exercice 06Soient x la largeur, y la longueur et z la hauteur du wagon. V = xyz et la somme des

aires et du plancher vaut A = xy + 2yz + 2xz. Les côtes sont de longueur non nulle donc

Dr.BelloufiMohammed - U Souk Ahras 29 Optimisation

Page 35: Cours d™Optimisation Sans Contraintes

2.4. SUGGESTIONS ET CORRIGÉS

xy > 0 (par exemple) et z = Vxy. On doit donc minimiser la fonction

A(x, y) = xy + 2V(x+ y)

xy= xy +

2V

y+

2V

x.

Le système d’optimalité est :

y3 = 2V,

x3 = 2V,et on obtient x = y = 3

√2V .

Exercice 07a) Le problème s’écrit

min J(a, b), (a, b, c) ∈ R3,

où J(a, b, c) =n∑i=1

(xi − at2i − bti − c)2. Les inconnues sont (a, b, c) et il n’y a pas de

contraintes.

b) Il y a solution unique si la matrice A =

S4 S3 S2

S3 S2 S1

S2 S1 N

associée à la forme

quadratique est définie positive (Sk =n∑i=1

tki ).

c) Le système d’optimalité s’écrit : A

a

b

c

=

N∑i=1

xit2i

N∑i=1

xiti

N∑i=1

xi

.

Dr.BelloufiMohammed - U Souk Ahras 30 Optimisation

Page 36: Cours d™Optimisation Sans Contraintes

Chapitre 3

Algorithmes

Dans ce chapitere, nous allons présenter quelques algorithmes permettant de calculer

(de manière approchée) la ou les solutions du problème (P) de départ. Bien entendu,

nous ne pouvons pas être exhaustifs ; nous présentons les méthodes “de base” les plus

classiques. Toutefois, la plupart de ces algorithmes exploitent les conditions d’optimalité

dont on a vu qu’elles permettaient (au mieux) de déterminer des minima locaux. Laquestion de la détermination de minima globaux est diffi cile et dépasse le cadre que nous

nous sommes fixés. Néanmoins, nous décrirons dans la section suivante, un algorithme

probabiliste permettant de “déterminer”un minimum global.

Remarquons aussi que nous avons fait l’hypothèse de différentiabilité de la fonction J .

Il existe des méthodes permettant de traiter le cas non différentiable (ou non régulier).

Nous n’en parlerons pas ici.Nous commencerons par quelques définitions :

Définition 3.0.1 (Algorithmes) Un algorithme est défini par une application A de Rn

dans Rn permettant la génération d’une suite d’éléments de Rn par la formule :x0 ∈ Rn donné, k = 0 étape d’initialisation,

xk+1 = A(xk), k = k + 1 itération k.

Ecrire un algorithme n’est ni plus ni moins que se donner une suite (xk)k∈N de Rn ; étudier

la convergence de l’algorithme, c’est étudier la convergence de la suite (xk)k∈N .

3.0.1 Convergence globale

Définition 3.0.2 On dit qu’un algorithme est globalement convergent (où encore, possèdela propriété de la convergence globale) si, quelque soit le point de départ x0 choisi, la suite

xkk générée par cet algorithme (où une sous suite) converge vers un point satisfant unecondition nécessaire d’optimalité.

31

Page 37: Cours d™Optimisation Sans Contraintes

La notion de convergence globale concerne le fait qu’on aura limite même si l’itéré ini-

tial est très éloigné de la limite x. Au contraire , on aura seulement une convergence locale

si une suite xkk converge vers x. Il est trés important de souligner qu’elle n’impliquepas (contrairement à ce que pourrait suggérer le terme) la convergence vers un optimum

global pour tout point de départ x0. Il s’agirait là, du reste, d’une condition beaucoup très

sévère, qui ne serait remplir pratiquement par aucun des algorithmes cunnus. Néanmoins,

on peut noter que dés qu’un algorithme possède la propriété de convergence global, il suffi t

d’imposer une condition de convexité pour obtenir précisément la convergence de l’algo-

rithme vers un optimum global du problème (P ), quelque soit le point de départ choisi. Il

est bien entendu que c’est très impotant d’assurer la convergence d’un algorithme, mais

la vitesse de la convergence est un facteur à prendre en compte lors de l’utilisation (où

la génération) d’un algorithme, on a en effet "intérêt" à ce que la méthode soit la plus

rapide possible tout en restant précise et stable.

3.0.2 Vitesse de convergence

La convergence globale d’un algorithme ayant été établie, nous nous intéressons main-

tenant à l’évaluation de son effi cacité d’un point de vue pratique, l’effi cacité d’un algo-

rithme dépend du nombre d’itérations nécessaires pour obtenir une approximation à ε

près (ε fixé à l’avance) de l’optimum x. Si l’on compare entre eux plusieurs algorithmes,

et si l’on admet que le temps de calcul par itération est sensiblement le même pour tous,

le meilleur est celui qui nécessitera le plus petit nombre d’itérations. Malheureusement,

il se révèle impossible de dégager des conclusions générales de ce genre de comparaison.

Suivant le point de départ choisi, la nature de la fonction à optimiser, la valeur de la

tolérance choisie, la hiérarchie des algorithmes peut varier considérablement. Si l’on veut

dégager un critère ayant une certaine valeur d’absolu, il faut par conséquent recourir à un

autre type d’analyse, c’est l’objet de l’étude de la convergence asymptotique c’est-à-dire

du comportement de la suite xk au voisinage du point limite x. Ceci conduit à attribuerà chaque algorithme un indice d’effi cacité appelé sa vitesse de convergence. Nous intro-

duisons maintenant les différents types de convergence. Plaçons nous dans Rn, où ‖ . ‖désigne la norme euclidienne et considérons une suite xk convergeant vers x.

— Si lim sup‖xk+1−x∗‖‖xk − x∗‖

= λ < 1.

On dit que la convergence est linéaire et λ est le taux de convergence associé.

— Si‖xk+1−x∗‖‖xk − x∗‖

−→ 0 quand k −→∞,on dit que la convergence est superlinéaire.

• Plus précisément si ∃p > 1 tel que lim supk−→∞

‖xk+1 − x∗‖‖xk − x∗‖p

< +∞,

Dr.BelloufiMohammed - U Souk Ahras 32 Optimisation

Page 38: Cours d™Optimisation Sans Contraintes

3.1. MÉTHODE DU GRADIENT

on dit que la convergence est superlinéaire d’ordre p.

• En particulier si lim supk−→∞

∥∥xk+1 − x∗∥∥

‖xk − x∗‖2 < +∞,

on dit que la convergence est quadratique (superlinéaire d’ordre 2).

3.1 Méthode du gradient

La méthode (ou algorithme) du Gradient fait partie d’une classe plus grande deméthodes numéri- ques appelées méthodes de descente. Expliquons rapidement l’idéedirectrice de ces méthodes.

On veut minimiser une fonction J . Pour cela on se donne un point de départ arbitraire

xo. Pour construire l’itéré suivant x1 il faut penser qu’on veut se rapprocher du minimum

de J ; on veut donc que J(x1) < J(xo). On cherche alors x1 sous la forme x1 = xo + ρ1d1

où d1 est un vecteur non nul de Rn et ρ1 un réel strictement positif. En pratique donc, on

cherche d1 et ρ1 pour que J(xo+ρ1d1) < J(xo). On ne peut pas toujours trouver d1. Quand

d1 existe on dit que c’est une direction de descente et ρ1 est le pas de descente. Ladirection et le pas de descente peuvent être fixes ou changer à chaque itération. Le schéma

général d’une méthode de descente est le suivant :x0 ∈ Rn donné

xk+1 = xk + ρkdk, dk ∈ Rn − 0, ρk ∈ R+∗,

où ρk et dk sont choisis de telle sorte que J(xk + ρkdk) ≤ J(xk).

Une idée naturelle pour trouver une direction de descente est de faire un développement

de Taylor (formel) à l’ordre 2 de la fonction J entre deux itérés xk et xk+1 = xk + ρkdk :

J(xk + ρkdk) = J(xk) + ρk(∇J(xk), dk) + o(ρkdk).

Comme on veut J(xk + ρkdk) < J(xk), on peut choisir en première approximation

dk = −∇J(xk). La méthode ainsi obtenue s’appelle l’algorithme du Gradient. Le pas ρkest choisi constant ou variable.

3.1.1 Algorithme du Gradient

1. Initialisation

k = 0 : choix de x0 et de ρ0 > 0.

2. Itération k

xk+1 = xk − ρk∇J(xk).

Dr.BelloufiMohammed - U Souk Ahras 33 Optimisation

Page 39: Cours d™Optimisation Sans Contraintes

3.1. MÉTHODE DU GRADIENT

3. Critère d’arrêt

Si ‖xk+1 − xk‖ < ε , STOP.

Sinon, on pose k = k + 1 et on retourne à 2.

Dans tout ce qui suit, ε est un réel positif (petit) donné qui représente laprécision désirée.

Cette méthode a pour avantage d’être très facile à mettre en oeuvre. Malheureuse-

ment, les conditions de convergence sont assez lourdes (c’est essentiellement de la stricte

convexité) et la méthode est en général assez lente. Nous donnons ci-dessous un critère

de convergence :

Théorème 3.1.1 Soit J une fonction C1 de Rn dans R, coercive et strictement convexe.On suppose qu’il existe une constante M strictement positive telle que

∀(x, y) ∈ Rn × Rn ‖∇J(x)−∇J(y)‖ ≤M ‖x− y‖ . (3.1)

Alors, si on choisit le pas ρk dans un intervalle [β1, β2] tel que 0 < β1 < β2 <2

M, la

méthode du gradient converge vers le minimum de J .

Preuve. J admet un minimum unique sur Rn et ce minimum x∗ est caractérisé par

∇J(x∗) = 0 , puisque J est strictement convexe. Montrons que la suite xk engendrée par

l’algorithme converge vers x∗ . Appliquons la relation (2.3) à y = xk+1 et x = xk :

J(xk+1) = J(xk) + (∇J(xk), xk+1−xk) +1∫0

(∇J(xk + t(xk+1−xk))−∇J(xk), xk+1−xk)dt.

Comme xk+1 = xk − ρk∇J(xk) on obtient (avec (3.1) )

J(xk+1)−J(xk) ≤ −1

ρk‖xk+1 − xk‖2+

1∫0

‖∇J(xk + t(xk+1 − xk))−∇J(xk)‖ ‖xk+1 − xk‖ dt,

J(xk+1)− J(xk) ≤ −1

ρk‖xk+1 − xk‖2 +

M

2‖xk+1 − xk‖2 =

[M

2− 1

ρk

]‖xk+1 − xk‖2 .

Si on choisit ρk dans un intervalle [β1, β2] tel que 0 < β1 < β2 <2

M, nous obtenons

alors

J(xk+1)− J(xk) ≤[M

2− 1

β2

]‖xk+1 − xk‖2 .

La suite J(xk) est alors strictement décroissante ; comme elle est minorée elle converge.

Cela entraîne d’une part que J(xk+1)−J(xk) tend vers 0 et d’autre part que la suite (xk)

est bornée (par coercivité). On peut donc extraire de (xk) une sous-suite convergente vers

Dr.BelloufiMohammed - U Souk Ahras 34 Optimisation

Page 40: Cours d™Optimisation Sans Contraintes

3.1. MÉTHODE DU GRADIENT

x. De plus comme

‖xk+1 − xk‖2 ≤[

1

β2

− M

2

]−1

[J(xk+1)− J(xk)] ,

la suite (xk+1 − xk) tend également vers 0. Par conséquent ∇J(xk) =xk+1 − xk

ρktend

vers 0.

Par continuité de ∇J , on obtient ∇J(x) = 0. Donc x est l’unique minimum x∗ de J .

Ceci étant vrai pour toute valeur d’adhérence de la suite (xk) cela prouve que toute la

suite (xk) converge vers x∗ .

Définition 3.1.1 On dit qu’une fonction F de Rn dans Rn est Lipschitzienne de rap-port M > 0 si

∀(x, y) ∈ Rn × Rn ‖F (x)− F (y) ≤‖M ‖x− y‖ .

La condition (3.1) du théorème précédent signifie donc que ∇J est lipschitzienne.

Corollaire 3.1.1 Soit J , une fonction C1 de Rn dans R, elliptique et de dérivée lipschit-zienne (c’est-à-dire vérifiant (2.2) et (3.1)). Alors, si on choisit le pas ρk dans un intervalle

[β1, β2] tel que 0 < β1 < β2 <2

M, la méthode du gradient converge vers le minimum de

J .

Preuve. Il suffi t de coupler les résultats des théorèmes 2.1.3 et 3.1.1.

Remarque 3.1.1 Lorsque J vérifie (2.2) et (3.1), on peut aussi interpréter l’algorithme

du gradient à pas constant comme la méthode des approximations successives appliquée à

la recherche du point fixe de la fonction

Sρ(x) = x− ρ∇J(x),

où ρ 6= 0. On peut en effet montrer que Sρ est lipschitzienne de rapport (1 − 2ρα +

ρ2M2). C’est

donc une contraction stricte si ρ ∈]0, 2α/M2[ ; elle possède alors un unique point fixe.

Pour ρ = α/M2, le taux de contraction est (1 − α/M2) : c’est le meilleur possible. La

convergence est alors celle d’une série géométrique de raison (1− α/M2).

3.1.2 Méthode du gradient à pas constant

On utilise le plus souvent la méthode du gradient à pas constant ( ρk ≡ ρ constant).

Toutefois, on peut faire varier le pas à chaque itération : on obtient alors la méthode du

gradient à pas variable.

Dr.BelloufiMohammed - U Souk Ahras 35 Optimisation

Page 41: Cours d™Optimisation Sans Contraintes

3.1. MÉTHODE DU GRADIENT

3.1.3 Méthode du gradient à pas optimal

La méthode du gradient à pas optimal propose un choix du pas qui rend la fonctioncoût minimale le long de la direction de descente choisie. Plus précisément, l’étape 2.

devient

2’.- Itération k

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

où ρk réalise le minimum sur R+ de la fonction Φk définie par

Φk(ρ) = J(xk − ρ∇J(xk)).

En pratique, on ne cherche pas le minimum de Φk et on détermine ρk en effectuant une

recherche linéaire de pas optimal suivant une règle de la forme suivante par exemple :

Règle de recherche linéaire de Wolfe

1. Initialisation ρ = 1 (par exemple), ρ− = ρ+ = 0. On se donne 0 < β1 < β2 < 1.

2. Si Φk(ρ) ≤ Φk(0) + β1ρΦ′k(0) et Φk(ρ) ≥ β2Φ′k(0) , STOP : ρk = ρ .

3. Sinon

—Si Φk(ρ) > Φk(0) + β1ρΦ′k(0), on pose ρ+ = ρ

—Si Φk(ρ) ≤ Φk(0) + β1ρΦ′k(0) et Φk(ρ) < β2Φ′k(0), on pose ρ− = ρ et on va à 4.

4. Choix d’un nouveau ρ :

—Si ρ+ = 0, on cherche ρ > ρ− (par exemple ρ = 2ρ−).

—Si ρ+ > 0, on cherche ρ ∈]ρ−, ρ+[ (par exemple ρ =ρ− + ρ+

2).

Retour à 2.

La règle apparaissant à l’étape 2. est connue sous le nom générique de règle d’Armijo.Il existe beaucoup d’autres règles de recherche linéaire.

Exemple 3.1.1 Les conditions du théorème peuvent paraître compliquées, aussi nous don-nons un exemple. Soit J la fonction de Rn vers R déjà évoquée plusieurs fois (car elle

joue un rôle important) définie par

J(x) =1

2(Ax, x)− (b, x),

où A est une matrice carrée, symétrique et définie positive et b ∈ Rn.Cette fonction J vérifie les hypothèses du théorème ci-dessus avec pour constantes α

et M la plus petite et la plus grande valeur propre de A (respectivement).

Dr.BelloufiMohammed - U Souk Ahras 36 Optimisation

Page 42: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

Remarque 3.1.2 La notion d’ellipticité est très importante, car elle conditionne la conver-gence de la plupart des algorithmes qui vont être décrits par la suite. Toutefois, les condi-

tions de convergence que nous donnons sont toujours des conditions suffi santes. L’algo-

rithme converge si elles sont vérifiées mais il peut éventuellement converger, mêmesi elles ne le sont pas ....En pratique, on ne calcule pas α et M . Pour trouver l’intervalle de convergence deρ,

on fait plusieurs tests pour différentes valeurs. La non convergence se traduit en général,

soit par une explosion de la solution ( elle va clairement vers +∞) soit par des oscillations(périodiques ou non) qui empêchent la suite des itérés de converger vers une valeur.

3.2 Méthode du gradient conjugué

Les méthodes du gradient conjugué sont utilisées pour résoudre les problèmes d’opti-

misation non linéaires sans contraintes spécialement les problèmes de grandes tailles. On

l’utilise aussi pour résoudre les grands systèmes linéaires.

Elles reposent sur le concept des directions conjuguées parce que les gradients successifs

sont orthogonaux entre eux et aux directions précédentes.

L’idée initiale était de trouver une suite de directions de descente permettant de ré-

soudre le problème

min f(x) : x ∈ Rn . (P)

Où f est régulière (continûment différentiable)

Dans ce chapitre on va décrire toutes ces méthodes, mais avant d’accéder à ces der-

nières, on va d’abord donner le principe général d’une méthode à directions conjuguées

3.2.1 Le principe général d’une méthode à directions conjuguées

Donnons la définition de "conjugaison" :

Définition 3.2.1 Soit A une matrice symétrique n×n, définie positive. On dit que deuxvecteurs x et y de Rn sont A−conjugués (ou conjugués par rapport à A) s’ils vérifient

xTAy = 0.

Description de la méthode

Soit d0, d1, ..., dn une famille de vecteurs A-conjugués. On appelle alors méthode dedirections conjuguées toute méthode itérative appliquée à une fonction quadratique stric-

tement convexe de n variables : q(x) = 12xTAx+ bTx+ c; avec x ∈ Rn et A ∈Mn×n est

Dr.BelloufiMohammed - U Souk Ahras 37 Optimisation

Page 43: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

symétrique et définie positive, b ∈ Rn et c ∈ R , conduisant à l’optimum en n étapes au

plus. Cette méthode est de la forme suivante :

x0 donné,

xk+1 = xk + αkdk,

où αk est optimal et d1, d2, .., dn possédant la propriété d’êtremutuellement conjuguées

par rapport à la fonction quadratique

Si l’on note gk = ∇q (xk), la méthode se construit comme suit :

Calcul de αkComme αk minimise q dans la direction dk, on a, ∀k :

q′ (αk) = dTk∇q(xk+1) = 0,

dTk∇q(xk+1) = dTk (Axk+1 + b) = 0.

Soit :

dTkA(xk + αkdk) + dTk b = 0,

d’où l’on tire :

αk =−dTk (Axk + b)

dTkAdk.

Comment construire les directions A-conjuguées ?Des directions A-conjuguées d0, ..., dk peuvent être générées à partir d’un ensemble

de vecteurs linéairement indépendants ξ0, ...., ξk en utilisant la procédure dite de Gram-

Schmidt, de telle sorte que pour tout i entre 0 et k, le sous-espace généré par d0, ..., di soit

égale au sous-espace généré par ξ0, ...., ξi.

Alors di+1 est construite comme suit :

di+1 = ξi+1 +

i∑m=0

ϕ(i+1)mdm.

Nous pouvons noter que si di+1 est construite d’une telle manière, elle est effectivement

linéairement indépendante avec d0, ..., di.

En effet, le sous-espace généré par les directions d0, ..., di est le même que le sous-espace

généré par les directions ξ0, ...., ξi, et ξi+1 est linéairement indépendant de ξ0, ...., ξi.

ξi+1 ne fait donc pas partie du sous-espace généré par les combinaisons linéaires de la

Dr.BelloufiMohammed - U Souk Ahras 38 Optimisation

Page 44: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

formei∑

m=0

ϕ(i+1)mdm, de sorte que di+1 n’en fait

pas partie non plus et est donc linéairement indépendante des d0, ..., di.

Les coeffi cients ϕ(i+1)m, eux sont choisis de manière à assurer la A-conjugaison des

d0, ..., di+1.

3.2.2 Méthode de gradient conjugué dans le cas quadratique

La méthode du gradient conjugué quadratique est obtenue en appliquant la procé-

dure de Gram-Schmidt aux gradients ∇q(x0), ...,∇q(xn−1), c’est-à-dire en posant ξ0 =

−∇q(x0), ..., ξn−1 = −∇q(xn−1).

En outre, nous avons :

∇q(x) = Ax+ b,

et ∇2q(x) = A.

Notons que la méthode se termine si ∇q(xk) = 0.

La particularité intéressante de la méthode du gradient conjugué est que le membre de

droite de l’équation donnant la valeur de dk+1 dans la procédure de Gram-Schmidt peut

être grandement simplifié.

Notons que la méthode du gradient conjugué est inspirée de celle du gradient (plus

profonde pente).

Algorithme de La méthode du gradient conjugué pour les fonctions quadra-tiques

On suppose ici que la fonction à minimiser est quadratique sous la forme : q(x) =12xTAx+ bTx+ c.

Si l’on note gk = ∇f(xk), l’algorithme prend la forme suivante.

Cet algorithme consiste à générer une suite d’itérés xk sous la forme :

xk+1 = xk + αkdk.

L’idée de la méthode est :

1- construire itérativement des directions d0, ..., dk mutuellementconjuguées :A chaque étape k la direction dk est obtenue comme combinaison linéaire du gradient

Dr.BelloufiMohammed - U Souk Ahras 39 Optimisation

Page 45: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

en xk et de la direction précédente dk−1 c’est-à-dire

dk+1 = −∇q(xk+1) + βk+1dk,

les coeffi cients βk+1étant choisis de telle manière que dk soit conjuguée avec toutes les

directions précédentes. autrement dit :

dTk+1Adk = 0,

on en déduit :

dTk+1Adk = 0⇒(−∇q(xk+1) + βk+1dk

)TAdk = 0

⇒ −∇T q(xk+1)Adk + βk+1dTkAdk = 0

⇒ βk+1 =∇T q(xk+1)Adk

dTkAdk=gTk+1Adk

dTkAdk.

2-déterminer le pas αk :En particulier, une façon de choisir αk consiste à résoudre le problème d’optimisation

unidimensionnelle suivant :

αk = min f(xk + αdk) , α > 0,

on en déduit :

αk =−dTk gkdTkAdk

= − 1

AdkgkdTkdTk

=−dTk gkdTkAdk

.

Le pas αk obtenu ainsi s’appelle le pas optimal.

Algorithme 3.1 (Algorithme du gradient conjugué "quadratique"

Etape 0 : (initialisation)

Soit x0 le point de départ, g0 = ∇q(x0) = Ax0 + b, poser d0 = −g0,

poser k = 0 et aller à l’étape 1.

Etape 1 :

si gk = 0 : STOP ( x∗ = xk)."Test d’arrêt"

si non aller à l’étape 2.

Etape 2 :

Dr.BelloufiMohammed - U Souk Ahras 40 Optimisation

Page 46: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

Prendre xk+1 = xk + αkdk avec :

αk =−dTk gkdTkAdk

,

dk+1 = −gk+1 + βk+1dk,

βk+1 =gTk+1Adk

dTkAdk.

Poser k = k + 1 et aller à l’étape 1.

La validité de l’algorithme du gradient conjugué linéaire

On va maintenant montrer que l’algorithme ci-dessus définit bien une méthode de

directions conjuguées.

Théorème 3.2.1 A une itération k quelconque de l’algorithme où l’optimum de q(x) n’est

pas encore atteint (c’est-à-dire gi 6= 0, i = 0, 1, ..., k ) on a :

a)

αk =gTk gkdTkAdk

6= 0, (3.2)

b)

βk+1 =gTk+1 [gk+1 − gk]

gTk gk, (3.3)

=gTk+1gk+1

gTk gk. (3.4)

c) Les directions d0, d1, ..., dk+1 engendrées par l’algorithme sont mutuellement conju-

guées.

Preuve. On raisonne par récurrence sur k en supposant que d0, d1, ..., dk sont mutuelle-

ment conjuguées.

a) Montrons d’abord l’équivalence de (3.2) et de (3.3).

On a : dk = −gk + βkdk−1.

Donc (3.2) s’écrit :

αk =−dTk gkdTkAdk

=− [−gk + βkdk−1]T gk

dTkAdk

=gTk gkdTkAdk

− βkdTk−1gk

dTkAdk

Dr.BelloufiMohammed - U Souk Ahras 41 Optimisation

Page 47: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

Comme (d0, d1, ..., dk−1) sont mutuellement conjuguées, xk est l’optimum de q(x) sur la

variété νk passant par x0 et engendrée par (d0, d1, ..., dk−1).

Donc dTk−1gk = 0 d’où l’on déduit (3.3).

b) Pour démontrer (3.4) remarquons que :

gk+1 − gk = A(xk+1 − xk) = αkAdk

⇒ Adk =1

αk[gk+1 − gk] .

On a alors :

gTk+1Adk =1

αkgTk+1 [gk+1 − gk] ,

et en utilisant (3.3)

αk =gTk gkdTkAdk

,

il vient

gTk+1Adk =dTkAdkgTk gk

.gTk+1 [gk+1 − gk]

⇒gTk+1Adk

dTkAdk=gTk+1 [gk+1 − gk]

gTk gk.

Or

βk+1 =gTk+1Adk

dTkAdk=gTk+1 [gk+1 − gk]

gTk gk,

ce qui démontre (3.4).

Alors du fait que :

gTk+1gk = 0,

car

gk = dk − βkdk−1.

Appartient au sous-espace engendré par (d0, d1, ..., dk) et que gk+1 est orthogonal à ce

sous-espace .

c) Montrons enfin que dk+1 est conjuguée par rapport à (d0, d1, ..., dk).

Dr.BelloufiMohammed - U Souk Ahras 42 Optimisation

Page 48: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

On a bien dTk+1Adk car, en utilisant dk+1 = −gk+1 + βkdk on aura :

dTk+1Adk =(−gk+1 + βk+1dk

)TAdk

= −gTk+1Adk + βk+1dTkAdk

= −gTk+1Adk +gTk+1Adk

dTkAdkdTkAdk

= 0.

Vérifions maintenant que :

dTk+1Adi = 0 pour i = 0, 1, ..., k − 1.

On a :

dTk+1Adi = −gTk+1Adi + βk+1dTkAdi.

Le seconde terme est nul par l’hypothèse de récurrence ((d0, d1, ..., dk )sont mutuelle-

ment conjuguées).

Montrons qu’il en est de même du premier terme. Puisque xi+1 = xi + αidi et que

αi 6= 0 on a :

Adi =1

αi(Axi+1 − Axi)

=1

αi(gi+1 − gi) .

En écrivant :

gi+1 = di+1 − βidi,gi = di − βi−1di−1,

on voit que Adi est combinaison linéaire de di+1, di et de di−1 seulement).

Mais puisque (d0, d1, ..., dk) sont mutuellement conjuguées, on sait que le point xk+1

est l’optimum de q(x) sur la variété νk+1, engendrée par (d0, d1, ..., dk) .

Donc gk+1 est orthogonal au sous-espace engendré par (d0, d1, ..., dk) et comme Adiappartient à ce sous-espace pour i = 0, 1, ..., k−1, on en déduit gTk+1Adi = 0 ce qui achève

la démonstration.

Dr.BelloufiMohammed - U Souk Ahras 43 Optimisation

Page 49: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

Remarque 3.2.1 dans ce cas dk est une direction de descente puisque

dTk∇q(xk) =(−∇q(xk) + βk+1dk−1

)T ∇q(xk)= −∇q(xk)T∇q(xk) + βk+1d

Tk−1∇q(xk)

= −‖∇q(xk)‖2 (car dTk−1∇q(xk) = 0 )

dTk∇q(xk) = −‖∇q(xk)‖2 < 0.

Les avantages de la méthode du gradient conjugué quadratique

1- la consommation mémoire de l’algorithme est minime : on doit stocker les quatrevecteurs xk, gk, dk, Adk

( bien sur xk+1 prend la place de xk au niveau de son calcul avec des remarques

analogues pour gk+1, dk+1, Adk+1) et les scalaires αk, βk+1.

2- L’algorithme du gradient conjugué linéaire est surtout utile pour résoudre desgrands systèmes creux, en effet il suffi t de savoir appliquer la matrice A à un vecteur.

3- La convergence peut être assez rapide : si A admet seulement r (r < n) valeurs

propres distincts la convergence a lieu en au plus r itération.

Différentes formules de βk+1 dans le cas quadratique

Les différentes valeurs attribuées à βk définissent les différentes formes du gradient

conjugué.

Si on note yk−1 = gk − gk−1, sk = xk+1 − xk on obtient les variantes suivantes :1- Gradient conjugué variante Hestenes - Stiefel(HS)

βHSk =gTk+1yk

dTk yk.

2- Gradient conjugué variante Fletcher Reeves(FR)

βFRk =‖gk‖2

‖gk−1‖2 .

3- Gradient conjugué variante Daniel (D)

βDk =gTk+1∇2f (xk) dk

dTk∇2f (xk) dk.

Dr.BelloufiMohammed - U Souk Ahras 44 Optimisation

Page 50: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

4- Gradient conjugué variante Polak-Ribière-Polyak(PRP)

βPRPk =gTk yk

‖gk−1‖2 .

5- Gradient conjugué variante descente —Fletcher (CD)

βCDk = − ‖gk‖2

dTk−1gk−1

.

6- Gradient conjugué variante Liu - Storey(LS)

βLSk = −gTk+1yk

dTk gk.

7- Gradient conjugué variante de Dai-Yuan(DY)

βDYk =‖gk‖2

dTk−1yk−1

.

8- Gradient conjugué variante de Dai—Liao (DL)

βDLk =gTk+1 (yk − tsk)

yTk sk.

9- Gradient conjugué variante Hager-Zhang(HZ)

βHZk =

(yk − 2dk

‖yk‖2

dTk yk

)Tgk+1

dTk yk.

10- Gradient conjugué variante de Z. Wei [74]

β∗k =gTk

(gk − ‖gk‖

‖gk−1‖gk−1

)‖gk−1‖2 .

11- Gradient conjugué variante de Hao Fan, Zhibin Zhu et Anwa Zhou

βMNk =

‖gk‖2 − ‖gk‖‖gk−1‖g

Tk gk−1

µ |gTk dk−1|+ ‖gk−1‖2 .

12- Gradient conjugué variante Rivaie-Mustafa-Ismail-Leong(RMIL)

βRMILk =

gTk (gk − gk−1)

‖dk−1‖2 .

Dr.BelloufiMohammed - U Souk Ahras 45 Optimisation

Page 51: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

13- Gradient conjugué variante Belloufi, Benzine(CGBB)

Remarque 3.2.2 Dans le cas quadratique on a vu que :

βHSk+1 = βPRPk+1 = βFRk+1 = βCDk+1 = βDYk+1.

Dans le cas non quadratique, ces quantités ont en général des valeurs différentes.

3.2.3 Méthode du gradient conjugué dans le cas non quadra-

tique

On s’intéresse dans cette section à la minimisation d’une fonction f : Rn → R, nonnécessairement quadratique :

min f(x); x ∈ Rn.

Les méthodes du gradient conjugué générent des suites xkk=0,1,2...de la forme sui-

vante :

xk+1 = xk + αkdk.

Le pas αk ∈ R étant déterminé par une recherche linéaire. la direction dk est définiepar la formule de récurrence suivante(βk ∈ R)

dk =

−gk si k = 1,

−gk + βkdk−1 si k ≥ 2.

Ces méthodes sont des extensions de la méthode du gradient conjugué linéaire du cas

quadratique, si βk prend l’une des valeurs

βPRPk =gTk yk

‖gk−1‖2 ,

βFRk =‖gk‖2

‖gk−1‖2 ,

βCDk =‖gk‖2

−dTk−1gk−1

,

où yk−1 = gk − gk−1.

Algorithme de La méthode du gradient conjugué pour les fonctions quel-conques

Etape0 : (initialisation)

Dr.BelloufiMohammed - U Souk Ahras 46 Optimisation

Page 52: Cours d™Optimisation Sans Contraintes

3.2. MÉTHODE DU GRADIENT CONJUGUÉ

Soit x0 le point de départ, g0 = ∇f(x0), poser d0 = −g0

Poser k = 0 et aller à l’étape 1.

Etape 1 :

Si gk = 0 : STOP ( x∗ = xk)."Test d’arrêt"

Si non aller à l’étape 2.

Etape 2 :

Définir xk+1 = xk + αkdk avec :

αk : calculer par la recherche linéaire

dk+1 = −gk+1 + βk+1dk,

βk+1 : défini selon la méthode.

Poser k = k + 1 et aller à l’étape 1.

Remarque 3.2.3 Dans le cas quadratique avec recherche linéaire exacte, on a vu queβPRPk = βFRk = βCDk = βDYk .

Exemple 3.2.1 Appliquons l’algorithme de gradient conjugué dans le cas quadratique auproblème quadratique défini par :

min f(x) = 12xTQx+ bTx

où Q =

1 1 1 1

1 2 2 2

1 2 3 3

1 2 3 4

, b =

−4

−7

−9

−10

.Les itérations sont détaillées dans le tableau suivant. L’algorithme converge après avoir

généré 4 directions. Il est aisé de vérifier que les directions générées par l’algorithme sont

bien conjuguées et que les gradients sont orthogonaux entre eux.

Itérations de la méthode des gradients conjuguées pour l’exemple

Dr.BelloufiMohammed - U Souk Ahras 47 Optimisation

Page 53: Cours d™Optimisation Sans Contraintes

3.3. MÉTHODE DE NEWTON

k xk ∇f (xk) dk αk βk

1

+5.00000e+00

+5.00000e+00

+5.00000e+00

+5.00000e+00

+1.60000e+01

+2.80000e+01

+3.60000e+01

+4.00000e+01

-1.60000e+01

-2.80000e+01

-3.60000e+01

-4.00000e+01

+1.20766e-01

2

+3.06775e+00

+1.61856e+00

+6.52430e-01

+1.69367e-01

+1.50810e+00

+9.48454e-01

-2.29750e-01

-1.06038e+00

-1.52579e+00

-9.79407e-01

+1.89953e-01

+1.01616e+00

+1.02953e+00 +1.10547e-03

3

+1.49690e+00

+6.10224e-01

+8.47993e-01

+1.21554e+00

+1.70656e-01

-1.55585e-01

-9.20500e-02

+1.23492e-01

-1.97676e-01

+1.38241e-01

+9.54138e-02

-1.05497e-01

+2.37172e+00 +1.77089e-02

4

+1.02806e+00

+9.38093e-01

+1.07429e+00

+9.65332e-01

+5.77796e-03

-1.65085e-02

+2.31118e-02

-1.15559e-02

-8.27569e-03

+1.82552e-02

-2.19062e-02

+1.02229e-02

+3.39118e+00 +1.26355e-02

5

+1.00000e+00

+1.00000e+00

+1.00000e+00

+1.00000e+00

-1.66356e-12

-3.12639e-12

-4.21174e-12

-4.78906e-12

3.3 Méthode de Newton

La méthode de Newton n’est pas une méthode d’optimisation à proprement parler.

C’est en réalité une méthode utilisée pour résoudre des équations non linéaires de la forme

F (x) = 0 où F est une fonction de Rn dans Rn. Nous allons d’abord la décrire puis montrercomment on peut l’appliquer à la recherche de minimum.

3.3.1 Description de la méthode

Considérons le problème d’optimisation sans contraintes (P )

(P ) : Minx∈Rn

f (x) ,

où f : Rn −→ R.Le principe de la méthode de Newton consiste à minimiser successivement les approxima-

Dr.BelloufiMohammed - U Souk Ahras 48 Optimisation

Page 54: Cours d™Optimisation Sans Contraintes

3.3. MÉTHODE DE NEWTON

tions du second ordre de f , plus précisément si

f (x) = f (x) +∇f (xk)t (x− xk) + (x− xk)tH (xk) (x− xk) + o ‖x− xk‖2 ,

posons

q (x) = f (x) +∇f (xk)t (x− xk) + (x− xk)tH (xk) (x− xk) .

Soit xk+1 l’optimum de q, alors il vérifie ∇q (xk+1) = 0, soit en remplaçant :

∇f (xk) +H (xk) (xk+1 − xk) = 0,

ou encore

H (xk) (xk+1 − xk) = −∇f (xk) ,

donc

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

Algorithme 2.1

Etape initiale : Soit ε > 0, critère d’arrêt. Choisir x1 point initial, poser k = 1 et aller

a l’étape principale.

Etape principale : Si ‖∇f (xk)‖ ≤ ε stop, sinon poser

xk+1 = xk − [H (xk)]−1∇f (xk) remplacer k par k + 1 est aller a l’étape principale.

3.3.2 Avantages et inconvénients

Avantages

Si le point x1 et assez proche de la solution optimale locale x∗ telle que H (x∗) soit définie

positive, alors l’algorithme de Newton converge de façon quadratique vers la solution x∗.

c’est à dire que l’on a,

‖xk+1 − x∗‖ ≤ γ ‖xk − x∗‖2 γ ≥ 0.

Inconvénients :

1-Cette méthode fonctionne très bien pour les problèmes de petite dimension (1 ≤ n ≤ 10),

lorsque on peut calculer facilement la matrice Hessienne H et sont inverse. Ce calcul

nécessite des itérations plus nombreuses et couteuses dans les problèmes de grandes tailles.

2-Comme xk+1 = xk − [H (xk)]−1∇f (xk) On voit bien que le successeur xk+1 de xk n’est

pas toujours bien défini.

Dr.BelloufiMohammed - U Souk Ahras 49 Optimisation

Page 55: Cours d™Optimisation Sans Contraintes

3.3. MÉTHODE DE NEWTON

3-Même si H (xk)−1 existe la direction dk = − [H (xk)]

−1∇f (xk) n’est pas toujours une

direction de descente.

Théorème 3.3.1 Soit F est une fonction de classe C2 de Rn dans Rn et x∗ un zéro deF (c’est-à-dire F (x∗) = 0). On suppose en outre que ce zéro est isolé et que DF (x∗) est

inversible (DF désigne la dérivée première de F ).

Alors il existe une boule fermée B centrée en x∗ telle que, pour tout point x0 ∈ B, lasuite (xk) définie par la méthode de Newton est entièrement contenue dans B et convergevers x∗ qui est le seul zéro de F dans B.Enfin la convergence est géométrique : il existe β ∈]0, 1[ tel que

∀k ≥ 0 ‖xk − x∗‖ ≤ βk ‖x0 − x∗‖ .En d’autres termes, si on choisit le point de départ x0 “assez près” de x∗ , alors

l’algorithme converge vers x∗ .

Preuve. Comme F est C1 et DF (x∗) est inversible, il existe une boule centrée en x∗ :

B(x∗, r0) sur laquelle DF (·) est inversible et DF (·)−1 est uniformément bornée par m.

Appliquons la formule de Taylor avec reste intégral entre x∗ et un itéré xk en supposant

que xk ∈ B(x∗, r0) :

F (x∗)− F (xk) = DF (xk)(x∗ − xk) +

1∫0

D2F (x∗ + t(xk − x∗))·(x∗ − xk)2tdt.

Comme F est C2, D2F est continue et uniformément bornée sur B(x∗, r0) par un réel

M > 0, et nous avons∣∣∣∣ 1∫0

D2F (x∗ + t(xk − x∗))·(x∗ − xk)2tdt

∣∣∣∣ ≤ M

2‖x∗ − xk‖2 .

Par conséquent, comme

xk+1 − x∗ = xk − x∗ −DF (xk)−1 [F (xk)− F (x∗)]

= DF (xk)−1[F (x∗)− F (xk)−DF (xk)(x

∗ − xk)]

= DF (xk)−1

[1∫0

D2F (x∗ + t(xk − x∗))·(x∗ − xk)2tdt

],

on obtient

‖xk+1 − x∗‖ ≤ mM

2‖x∗ − xk‖2 . (3.5)

Posons r = min(r0,2

mM, 1) ; il est alors facile de voir par récurrence que si x0 ∈

B(x∗, r) alors pour tout k, xk ∈ B(x∗, r) : la suite des itérés est bien définie et reste dans

Dr.BelloufiMohammed - U Souk Ahras 50 Optimisation

Page 56: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

la boule. Posons alors ek =mM

2‖xk − x∗‖. La relation (3.5) donne

ek+1 ≤ e2k.

La suite ek converge donc vers 0 si e0 =mM

2‖x0 − x∗‖ < 1, cad si x0 est dans la

boule B(x∗, r∗) où r∗ = min(r,1

mM) par exemple.

Pour obtenir une méthode qui converge superlinéairement, il est nécessaire d’approxi-

mer l’étape de Newton asymptotiquement. C’est le principe de Dennis et Moré. Comment

peut-on y aboutir sans évaluer la matrice Hessienne dans chaque itération ?

La réponse à été découverte par Davidon en 1959 et a été développée et popularisée par

Fletcher et Powell en 1963. Elle consiste à commencer par n’importe quelle approximation

de la matrice Hessienne et à chaque itération, on améliore la matrice en introduisant la

courbure du problème mesuré tous au long de l’étape. Si cette amélioration est faite

correctement, on obtient quelques méthodes remarquablement robustes et effi caces, qu’on

appelle les méthodes de la variable métrique ou quasi Newton. Ils ont libéré l’optimisation

non linéaire en procurant une alternative à la méthode de Newton, qui est très coûteuse

pour plusieurs applications.

Il y a plusieurs méthodes de variable métrique, on s’étalera particulièrement sur les trois

plus importantes, la méthode de correction de rang un, la méthode DFP (Davidon, Fet-

cher, Powell), et la méthode BFGS (Broyden, Fletcher, Goldfarb, Shano).

3.4 Méthode de quasi Newton ou quasi-Newtonniennes

Une méthode de quasi Newton est une méthode de type :xk+1 = xk + λkdk,

dk = −Bkgk,(3.6)

ou bien xk+1 = xk + λkdk,

dk = −S−1k gk,

(3.7)

où Bk (respectivement Sk) est une matrice destinée à approcher l’inverse du Hessien de f

(respectivement le Hessien) de f en xk. Le problème posé est : quelle stratégie à adopter

pour faire cette approximation ? On peut par exemple poserB1 = I, mais comment ensuite

mettre à jour l’approximation Bk au cours des itérations ?

L’idée est la suivante :

Dr.BelloufiMohammed - U Souk Ahras 51 Optimisation

Page 57: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

Prenons f ∈ C2 (Rn), et faisons un développement de ∇f (x) au voisinage de xk.

∇f (x) = ∇f (xk) +H (xk) (x− xk) + 0 (‖x− xk‖)' ∇f (xk) +H (xk) (x− xk) ,

ce qui implique

[H (xk)]−1 [∇f (x)−∇f (xk)] ' x− xk.

Les approximations sons exacts si f est quadratique. En particulier avec x = xk+1 et si

Bk était une bonne approximation de [H (xk)]−1 alors

Bk [g (xk+1)− g (xk)] ' xk+1 − xk.

On peut imposer que Bk+1 satisfait cette équation exactement d’où

Bk+1 [g (xk+1)− g (xk)] = xk+1 − xk. (3.8)

3.4.1 Formules de mise à jour de l’approximation du Hessien

Le principe de la mise à jour consiste à une itération donnée de l’algorithme

xk+1 = xk + λkdk,

dk = −Bkgk,

à appliquer une formule de type

Bk+1 = Bk + ∆k, (3.9)

avec ∆k symétrique, assurant la relation de quasi Newton. ainsi que Bk+1 définie positive,

sous l’hypothèse que Bk est définie positive.

La formule (3.9) permet d’utiliser les nouvelles informations obtenues lors de l’étape k

de l’algorithme, c’est à dire essentiellement le gradient gk+1 = ∇f (xk+1) au point xk+1,

obtenu par une recherche linéaire (exacte où approchée) dans la direction dk. Il existe

différentes formules de type (3.6). Suivant que ∆k est de rang un ou deux, on parlera de

correction de rang un ou de rang deux.

Dr.BelloufiMohammed - U Souk Ahras 52 Optimisation

Page 58: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

3.4.2 Méthode de correction de rang un

Etend donné que [H (xk)]−1est symétrique, la formule de mise à jour de l’approximation

du Hessien Bk est la suivante :

Bk+1 = Bk + akukuTk , uk ∈ Rn,

donc la condition de quasi Newton s’écrit comme suit

sk =(Bk + akuku

Tk

)yk,

ou encore

sk −Bkyk = akukuTk yk.

D’ou l’on déduit que uk est proportionnel à sk −Bkyk, avec un facteur qui peut être pris

en compte dans ak. Un choix évident pour vérifier cette dernière équation est de prendre

uk = sk −Bkyk et ak tel que ak(uTk yk

)= 1, on obtient :

Bk+1 = Bk +(sk −Bkyk) (sk −Bkyk)

T

(sk −Bkyk)T yk

. (3.10)

Algorithme 2.2

Etape initiale : Soit ε > 0, déterminer le critère d’arrêt. Choisir un point initial x1 et

une matrice symétrique définie positive B1 poser k = 1, et aller aux étapes principales.

Etape principale :

Etape 1 : Si ‖∇f (xk)‖ < ε. stop ; sinon, poser dk = −Bk∇f (xk) et soit λk solution

optimale du problème min f (xk + λdk) , λ ≥ 0. et poser xk+1 = xk + λkdk.

Etape 2 : Construire Bk+1 comme suit :

Bk+1 = Bk +(sk −Bkyk) (sk −Bkyk)

T

(sk −Bkyk)T yk

,

avec

sk = xk+1 − xk,yk = ∇f (xk+1)−∇f (xk) .

Remplacer k par k + 1 et aller a l’étape 1.

Théorème 3.4.1 Si f est quadratique, de matrice Hessienne H définie positive et si

Dr.BelloufiMohammed - U Souk Ahras 53 Optimisation

Page 59: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

s1,s2, . . . sn sont des vecteurs indépendants, alors la méthode de correction de rang un

converge au plus dans (n+ 1) itérations et (Bn+1)−1 = H.

Avantages

Cette méthode présente l’avantage, que le point xk+1 n’a pas besoin d’être choisi

comme le minimum exact, c’est à dire qu’on n’a pas besoin d’effectuer des recherches

linéaire exactes.

Inconvénients

-Même si la fonction est quadratique, et même si son Hessien est défini positif, il se

peut que la matrice Bk ne soit pas définie positive.

-Le dénominateur (sk −Bkyk)T yk peut devenir nul ou très petit, ce qui rendre le

procédé instable.

3.4.3 Méthode de Davidon Fletcher Powell (DFP)

Cette méthode a été proposée par Davidon en 1959 et développé plus tard en 1963 par

Fletcher. La formule de mise à jour de DFP est une formule de correction de rang deux.

De façon plus précise construisons Bk+1 en fonction de Bk de la forme :

Bk+1 = Bk + Ak + ∆k, (3.11)

avec ∆k et Ak deux matrices de rang un tel que

Ak = akukuTk , ∆k = bkvkv

Tk ,

ak, bk sont des constantes, uk, vk sont deux vecteurs de Rn.

Bk+1 doit satisfaire la condition quasi Newton c’est à dire

xk+1 − xk = Bk+1 [gk+1 − gk] .

Si on pose par suite

sk = xk+1 − xk, yk = gk+1 − gk,

donc

Dr.BelloufiMohammed - U Souk Ahras 54 Optimisation

Page 60: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

sk = Bk+1yk (3.12)

=(Bk + akuku

Tk + bkvkv

Tk

)yk,

par suite

akukuTk yk + bkvkv

Tk yk = sk −Bkyk,

Un choix évident pour satisfaire cette équation est de prendre

uk = sk, vk = Bkyk, akuTk yk = 1, bkvTk yk = −1,

d’où

Bk+1 = Bk +sks

Tk

sTk yk− Bky

Tk ykBk

yTkBkyk. (3.13)

Remarque 3.4.1 Le résultat suivant montre que sous certaines conditions, la formule(3.13) conserve la définie positivité des matrices Bk.

Théorème 3.4.2 On considère la méthode définie parxk+1 = xk + λkdk,

dk = −Bkgk,

où λk optimal, B1 définie positive est donnée ainsi que x1, alors les matrices Bk sont

définies positives.

Exemple 3.4.1 La propriété sTk yk > 0 est vérifiée également par des méthodes de re-

cherche linéaires approchées comme par exemple la règle de Wollf et Powell.

En effet :

Dans ce cas on détermine un point xk+1 tel que

θ′(λk) = ∇f (xk+1)T dk ≥ σ2∇f (xk)

T dk 0 < σ2 < 1,

d’où

gTk+1

xk+1 − xkλk

> gTkxk+1 − xk

λk,

(gk+1 − gk)T sk > 0.

Dr.BelloufiMohammed - U Souk Ahras 55 Optimisation

Page 61: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

Algorithme 2.3

Etape initiale :

1-Soit ε > 0, déterminer le critère d’arrêt. Choisir un point initial x1 et une matrice

symétrique définie positive B1 quelconque (par exemple B1 = I) poser k = 1, et aller aux

étapes principales

Etapes principales.

Etape 1 :Si ‖∇f (xk)‖ < ε stop ; sinon, poser dk = −Bkgk et déterminer le pas optimal

λk solution optimale du problème min f (xk + λdk), λ ≥ 0. et poser xk+1 = xk + λkdk

Etape 2 :Construire Bk+1 comme suit :

Bk+1 = Bk +sks

Tk

sTk yk− Bkyky

TkBk

yTkBkyk,

avec

sk = xk+1 − xk.yk = ∇f (xk+1)−∇f (xk) .

Remplacer k par k + 1 et aller a l’étape 1.

Cet algorithme a un comportement remarquable dans le cas où f est une fonction qua-

dratique

Théorème 3.4.3 Appliqué à une forme quadratique f , l’algorithme DFP décrit par larelation

Bk+1 = Bk +sks

Tk

sTk yk− Bkyky

TkBk

yTkBkyk,

engendre des directions conjuguées s1, s2...........sk vérifiant

sTi Hsj = 0 1 ≤ i < j ≤ k, (3.14)

Bk+1Hsi = si 1 ≤ i ≤ k. (3.15)

Avantages

1-Pour des fonctions quadratiques (avec une recherche linéaire exacte) :

-L’algorithme converge dans au plus n étapes avec Bn+1 = H−1.

-elles engendrent des directions conjuguées.

2-Pour les fonctions quelconques :

-la matrice Bk reste définie positive, ce qui est nécessaire pour que la direction soit

une direction de descente.

Dr.BelloufiMohammed - U Souk Ahras 56 Optimisation

Page 62: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

Inconvénients

-la méthode DFP est sensible à la précision de la recherche linéaire.

3.4.4 Méthode de Broyden, Fletcher, Goldfarb et Shanno(BFGS)

La formule de mise à jour de Broyden, Fletcher, Goldfarb et Shanno est une formule de

correction de rang deux, qui s’obtient à partir de la formule DFP en intervertissant les

rôles de sk et yk. La formule obtenue permet de mettre à jour une approximation Bk de

Hessien lui meme et non de son inverse comme dans le cas de la méthode DFP. On exigera

que posée dans les mêmes propriétés, à savoir Bk+1 reste définie positive si Bk l’est et bien

sur l’équation d’approximation de quasi Newton doit etre vérifiée, c’est à dire :

Bk+1sk = yk.

On obtient donc

Bk+1 = Bk +yky

Tk

yTk sk− Bksks

TkBk

sTkBksk. (3.16)

Algorithme 2.4

Etape initiale : Soit ε > 0, déterminer le critère d’arrêt. Choisir x1 point initial et

B1 définie positive quelconque (par exemple B1 = I).

Poser k = 1 et aller aux étapes principales

Etapes principales.

Etape 1 : Si ‖∇f (xk)‖ < ε stop ; sinon, poser dk = −Bkgk et déterminer le pas

optimal λk solution optimale du problème min f (xk + λdk), λ ≥ 0 et poser xk+1 = xk +

λkdk

Etape 2 : Construire Bk+1 comme suit :

Bk+1 = Bk +yky

Tk

yTk sk− Bksks

TkBk

sTkBksk,

avec

sk = xk+1 − xk,yk = ∇f (xk+1)−∇f (xk) .

Remplacer k par k + 1 et aller a l’étape 1.

Dr.BelloufiMohammed - U Souk Ahras 57 Optimisation

Page 63: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

Exemple 3.4.2 1-Notons que la direction dk est obtenue par une résolution d’un systèmelinéaire. En particulier la mise à jour de Bk est faite directement sur le facteur de Cholesky

Ck où Bk = CkCTk ce qui ramène le calcule de dk au même coût que pour la formule de

DFP

2-La méthode BFGS possède les mêmes propriétés que la méthode DFP dans le cas

quadratique. Les directions engendrées sont conjuguées. Cette méthode est reconnue comme

étant beaucoup moins sensible que la méthode DFP aux imprécisions dans la recherche

linéaire, du point de vue de vitesse de convergence. Elle est donc tout à fait adaptée quand

la recherche linéaire est faite de façon économique, avec par exemple la règle de Goldstein

ou la règle de wolf et Powell.

3-La relation Bk+1 = Bk +yky

Tk

yTk sk− Bksks

TkBk

sTkBkskpermet de construire une approximation

de la matrice Hessienne elle même (et non pas son inverse).

En effet : Posons

Ck =yky

Tk

yTk sk− Bksks

TkBk

sTkBksk. (3.17)

Nous avons

Hk+1 = [Bk+1]−1 = [Bk + Ck]−1 .

Par application de la formule de Sherman-Morrison-Woodbury suivante

(A+ abT

)−1= A−1 − A−1abTA−1

1 + bTA−1a, (3.18)

où A est une matrice inversible, et b est un vecteur de Rn, et en supposant que bTA−1a 6=−1, alors on a

Sk+1 = [Bk+1]−1 = [Bk + Ck]−1 =

[Bk +

ykyTk

yTk sk− Bksks

TkBk

sTkBksk

]−1

.

Posons

A = Bk +yky

Tk

yTk sk, a =

BksksTkBksk

, bT = sTkBk,

donc

Hk+1 =

[Bk +

ykyTk

yTk sk

]−1

[Bk +

ykyTk

yTk sk

]−1BksksTkBksk

sTkBk

[Bk +

ykyTk

yTk sk

]−1

1 + sTkBk

[Bk +

ykyTk

yTk sk

]−1BksksTkBksk

. (3.19)

Dr.BelloufiMohammed - U Souk Ahras 58 Optimisation

Page 64: Cours d™Optimisation Sans Contraintes

3.4. MÉTHODE DE QUASI NEWTON OU QUASI-NEWTONNIENNES

On doit calculer[Bk +

ykyTk

yTk sk

]−1

, pour cela on applique la formule de Sherman-Morrison-

Woodbury une deuxième fois, on pose

A = Bk , a =ykyTk sk

, bT = yTk ,

[Bk +

ykyTk

yTk sk

]−1

= [Bk]−1 −

[Bk]−1 ykyTk sk

yTk [Bk]−1

1 + yTk [Bk]−1 ykyTk sk

= [Bk]−1 − [Bk]

−1 ykyTk [Bk]

−1

yTk sk + yTk [Bk]−1 yk

.

Remplaçons cette dernière dans la formule (3.19) et d’après un calcule on obtient

Hk+1 = [Bk+1]−1 = [Bk]−1

+

[1 +

yTk [Bk]−1 yk

sTk yk

]− sky

Tk [Bk]

−1 + [Bk]−1 yks

Tk

sTk yk

= Hk +

[1 +

yTkHkyksTk yk

]sks

Tk

sTk yk− sky

TkHk +Hkyks

Tk

sTk yk. (3.20)

3.4.5 Les méthodes de classe Broyden

Une méthode de classe Broyden est une méthode de quasi-Newton où l’approximation de

l’inverse du Hessien prendre la formule suivant :

Bk+1 = Bk −Bksks

TkBk

sTkBksk+yky

Tk

yTk sk+ φ

(sTkBksk

)vkv

Tk , (3.21)

tel que φ ∈ [0, 1] , vTk =

[ykyTk sk

− BksksTkBksk

].

Si φ = 0 on obtient la méthode BFGS, car la formule (3.20) devient

Bk+1 = Bk −Bksks

TkBk

sTkBksk+yky

Tk

yTk Sk,

c’est exactement la formule de l’approximation de la méthode BFGS.

Si φ = 1 on obtient la méthode DFP.

Dr.BelloufiMohammed - U Souk Ahras 59 Optimisation

Page 65: Cours d™Optimisation Sans Contraintes

3.5. MÉTHODE DE RELAXATION

3.5 Méthode de relaxation

La dernière méthode que nous présentons permet de ramener un problème de mini-

misation dans Rn à la résolution successive de n problèmes de minimisation dans R (àchaque itération).

On cherche à minimiser J : Rn → R ; posons X = (x1, ..., xn). Le principe de la

méthode est le suivant : étant donné un itéré Xk de coordonnées (xk1, ..., xkn), on fixe

toutes les composantes sauf la première et on minimise sur la première :

min J(x, xk2, xk3, ..., x

kn), x ∈ R .

On obtient ainsi la première coordonnée de l’itéré suivant Xk+1 que l’on note xk+11 ;

on peut, pour effectuer cette minimisation dans R, utiliser par exemple la méthode deNewton dans R.On recommence ensuite en fixant la première coordonnée à xk+1

1 et les n − 2 der-

nières comme précédemment. On minimise sur la deuxième coordonnée et ainsi de suite.

L’algorithme obtenu est le suivant :

Méthode de relaxation successive1. Initialisationk = 0 : choix de X0 ∈ Rn.2. Itération kpour i variant de 1 à n, on calcule la solution xk+1

i de

min J(xk+11 , xk+1

2 , ..., xk+1i−1 , x, x

ki+1, ..., x

kn), x ∈ R .

3. Critère d’arrêtSi ‖xk+1 − xk‖ < ε , STOP

Sinon, on pose k = k + 1 et on retourne à 2.

Dr.BelloufiMohammed - U Souk Ahras 60 Optimisation

Page 66: Cours d™Optimisation Sans Contraintes

3.6. TRAVAUX PRATIQUES

3.6 Travaux pratiques

TP 011- Programmer et tester les algorithmes suivante :.

—Gradient à pas constant.

—Algorithme de Newton.

—Relaxation avec sous-programme Newton (pour R).2- Pour chacun d’entre eux, une étude de sensibilité sur le point de départ (initialisa-

tion) et le pas éventuel sera menée le plus rigoureusement possible. On fera une compa-

raison numérique des trois méthodes surtout en termes de :

—Vitesse de convergence - nombre d’itérations - temps CPU.

—Robustesse et domaine de validité en particulier sur les exemples suivants (f de R2

dans R).a) f (x, y) = x2 − 5xy + y4 − 25x− 8y,

b) f (x, y) = 5x2 − 5y2 − xy − 11x+ 11y + 11,

c) f (x, y) = (x4 − 3) + y4,

d) f (x) = x41 − 4x3

1 + 6 (x21 + x2

2)− 4 (x1 + x2) ,

e) f (x) = 12xtGx+ ctx avec

G =

2 −1 0 0 .. ..

−1 2 −1 0 .. ..

0 −1 2 −1 0 ..

... . . . . . . . . .. ..

.. .. 0 −1 2 −1

.. .. .. 0 −1 2

c =

1

1......

1

1

.

TP 02Programmer l’algorithme du gradient conjugué pour résoudre Ax = b ; comparer avec

les procédures de MATLAB en terme de précision et de temps CPU.

On fera des tests sur des matrices définies positives de grande taille et sur l’exemple

suivant :

A =

0, 78 −0, 02 −0, 12 −0.14

−0, 02 0, 86 −0, 04 0, 06

−0, 12 −0, 04 0, 72 −0, 08

−0, 14 0, 06 −0, 08 0, 74

et b =

0, 76

0, 08

1, 12

0, 68

.

Dr.BelloufiMohammed - U Souk Ahras 61 Optimisation

Page 67: Cours d™Optimisation Sans Contraintes

3.6. TRAVAUX PRATIQUES

On considére le problème de minimisation sans contraintes sur Rn

(P )

minx∈Rn

f (x) .

a) Initialisation : i = 0

z0 ∈ Rn est tel que l’ensemble Cz0 = z ∈ Rn | f (z) ≤ f (z0) est borné et le HessienH(z) = ∂2f(z)

∂z2est défini positif sur cet ensemble.

Soit α ∈[0, 1

2

].

b) Itération i

♠ Calcul de ∇f(zi) : Si ∇f(zi) = 0 , STOP

SINON : calcul de H(zi)

♠ On pose : h(zi) = −H(zi)−1∇f(zi)

♠ Calcul de λi par la procédure suivante :Soit θ1 (µ, z) = (f (z + µh(z))− f (z))− µ (1− α) 〈∇f(z), h(z)〉 et

θ2 (µ, z) = (f (z + µh(z))− f (z))− µα 〈∇f(z), h(z)〉1. µ = 1

2. Calcul de θ1 (µ, zi)

3. ISi θ1 (µ, zi) = 0, on pose λi = µ et STOPISi θ1 (µ, zi) < 0 , on pose µ = µ+ 1 et RETOUR à b.

I Si θ1 (µ, zi) > 0 on continue à 4.

4. Calcul de Calcul de θ2 (1, zi)

5. ISi θ2 (1, zi) ≤ 0, on pose λi = µ et STOP

ISinon on pose t0 = µ− 1 ,r0 = µ et on continue à 6.

6. ( on a λi ∈ [t0, r0])

On pose j = 0

7. Calcul de νj =tj+rj

2, de θ1 (νj, zi) et de θ2 (νj, zi)

8. Si θ1 (νj, zi) ≥ 0 et θ2 (νj, zi) ≤ 0 on pose λj = νj et STOP

SINON on va à 9.

9. Si θ1 (νj, zi) > 0 alors tj+1 = tj et rj+1 = νj , j = j + 1 et on va à 7.

SINON tj+1 = νj et rj+1 = νj , j = j + 1 et on va à 7.

c) zi + 1 = zi + λih(zi), i = i+ 1.

Dr.BelloufiMohammed - U Souk Ahras 62 Optimisation

TP 03

Page 68: Cours d™Optimisation Sans Contraintes

3.7. TRAVAUX DIRIGÉS 3

3.7 Travaux dirigés 3

Exercice 01a) Soient p1 = 52 et p2 = 44 les prix respectifs de deux produits . Soient q1 et q2 les

quantités respectives de ces produits. Le revenu issu de la vente est donc : R = p1q1 +p2q2.

La fonction coût est : C = q21+ q1q2 + q2

2 et le bénéfice réalisé est :∏

= R − C. Trouverles quantités q1 et q2 maximisant le bénéfice.

b) Même problème avec des prix adaptatifs , i.e. variant en fonction de la quantité de

produits : p1 = 256− 3q1 − q2,

p2 = 222 + q1 − 5q2,

Exercice 02On veut résoudre le système suivant par une méthode de gradient à pasramètre opti-

mal : 12x = 0c2y = 0

où c ≥ 1.

a) Ecrire le système sous la forme Ax = b et calculer les valeurs propres de A.

b) Soit r le résidu : b−Ax. Calculer r et le paramètre α correspondant à la minimisationsur R de la fonction qui à α associe J(xk + αrk).

c) Soit Pk le point de coordonnées xk et yk. Exprimer xk+1 et yk+1 en fonction de xket yk.

Exercice 03On veut résoudre le système Ax = b, x ∈ Rn (avec A symétrique, définie, positive)par une méthode

de gradient à pas constant.

Soit x la solution de ce système.

On propose l’algorithme suivant :x0, r0 = b− Ax0,

xk+1 = xk + αrk,

ou rk = b− Axk,

α est un réel constant.

a) Soit ek = xk − x (pour k ≥ 0); montrer que ek = (I − αA)ke0,

(pour k ≥ 0).

b) soient 0 < λn ≤ λn−1 ≤ ... ≤ λ1 les valeurs propres de A.

Montrer que l’lgorithme converge si et seulement si 0 < α < 2λ1.

Dr.BelloufiMohammed - U Souk Ahras 63 Optimisation

Page 69: Cours d™Optimisation Sans Contraintes

3.7. TRAVAUX DIRIGÉS 3

c) Montrer que le meilleur choix de α est : αopt = 2λ1+λn

et qu’alors :

ρ (I − αoptA) =λ1 − λnλ1 + λn

.

Exercice 04On veut résoudre le système suivant par une méthode de gradient à pasramètre opti-

mal : 12x = 0c2y = 0

où c ≥ 1.

a) Ecrire le système sous la forme Ax = b et calculer les valeurs propres de A.

b) Soit r le résidu : b− Ax.

Calculer r et le paramètre α correspondant à la minimisation sur R de la fonction quià α associe J(xk + αrk).

c) Soit Pk le point de coordonnées xk et yk. Exprimer xk+1 et yk+1 en fonction de xket yk.

d) Soit tk = ykxkla pente de la droite (OPk) , tq O (0, 0). Exprimer tk+2 en fonctio de

tk.

Interprétation géométrique. Conclusion ?

e) Soit t ∈ tk, tk+1 (k donné).

On appelle τ le facteur moyen de réduction de l’erreur : τ 2 = yk+2yk

= xk+2xk.

Montrer que :

τ 2 =

[c− 1

c+ 1

]1

1 + c(c+1)2

(ct− 1

ct

)2 .

Pour quelle valeur de t , τ est-il maximum?

Exercice 05On considere la fonction

f (x, y) =1

2x2 +

1

2y2.

En partant du point initial (x0, y0) = (1, 1) et en appliquant la méthode du gradient

avec ρk optimale, calculez (x1, y1) , (x2, y2) et (x3, y3) .

Exercice 06Soit f : R2 → R définie par

f (x, y) =1

2

(x2 + αy2

),

Dr.BelloufiMohammed - U Souk Ahras 64 Optimisation

Page 70: Cours d™Optimisation Sans Contraintes

3.7. TRAVAUX DIRIGÉS 3

et (P ) le problème de minimisation sans contraintes suivant :

(P ) :

1

2

(x2 + αy2

): (x, y) ∈ R2

.

1) Pour quelles valeurs de α, f est quadratique strictement convex.

2) On suppose que α = 1. En partant du point (x0, y0) = (1, 1) , appliquez la méthode

du gradient conjugué au problème (P ) et trouvez la solution minimale globale du

problème (P ).

Exercice 07On considére f (x) = 1

2xTQx− btx, avec Q symétrique définie positive, x ∈ Rn, b ∈ Rn

et αk est obtenue par une recherche linéaire exacte.

a) Ecrire l’algorithme du gradient conjugué quadratique

b) Montrez que gTk dk−1 = 0 ∀kc) Montrer que dk est une direction de descente

d) Si βk =gTk+1Qdk

dTkQdk, montrez que βk = βHSk = βPRPk = βFRk = βCDk .

(gTk+1gk = 0)

( βHSk =gTk+1(gk+1−gk)

dTk (gk+1−gk), βPRPk =

gTk+1(gk+1−gk)

‖gk‖2, βFRk = ‖gk+1‖2

‖gk‖2et βCDk = − ‖gk‖2

dTk−1gk−1)

Exercice 08Vérifier que le calcul de l’inverse d’un scalaire par la méthode de Newton correspond

à la méthode itérative :

xk+1 = xk (2− αxk) , k ≥ 0.

Construire , par analogie , une méthode itérative d’approximation de l’inverse d’une

matrice inversible A , de la forme :B0 matrice arbitraire,

Bk+1 = fonction(Bk, A), k ≥ 0.

Démontrer qu’une CNS de convergence de cette méthode est : ρ(I − AB0) < 1 où

ρ(I − AB0) désigne le rayon spectral de la matrice I − AB0.

Supposant la matrice A symétrique , définie, positive et supposant connu son rayon

spectral, comment choisir simplement la matrice B0 pour vérifier la condition précédente ?

Dr.BelloufiMohammed - U Souk Ahras 65 Optimisation

Page 71: Cours d™Optimisation Sans Contraintes

3.8. SUGGESTIONS ET CORRIGÉS

Exercice 09Une variante de la méthode de Newton pour la résolution des systèmes d’équations

non linéaires est la méthode de Gauss-Seidel qui se présente sous la forme suivante :

x(k+1)1 = x

(k)1 −

f1

(x

(k)1 , x

(k)2 , ..., x

(k)n

)∂1f1

(x

(k)1 , x

(k)2 , ..., x

(k)n

) ,

x(k+1)2 = x

(k)2 −

f2

(x

(k+1)1 , x

(k)2 , ..., x

(k)n

)∂2f2

(x

(k+1)1 , x

(k)2 , ..., x

(k)n

) ,...

x(k+1)n = x(k)

n −fn

(x

(k+1)1 , x

(k+1)2 , ..., x

(k+1)n−1 , x

(k)n

)∂nfn

(x

(k+1)1 , x

(k+1)2 , ..., x

(k+1)n−1 , x

(k)n

) ,où ∂i = ∂

∂xi.

Montrer que si les fonctions fi sont affi nes : fi(x) =n∑j=1

aijxj − bi, cette méthode n’est

autre que la méthode itérative de Gauss-Seidel pour le résolution des systèmes linéaires.

3.8 Suggestions et Corrigés

Exercice 01a) q1 = 20 et q2 = 12.

b) q1 = 30 et q2 = 16.

Exercice 031. Comme ek = xk − x , on obtientek+1 = ek + rk = ek + (b− A(ek + x))

= ek + α(b− Ax︸ ︷︷ ︸=0

− Aek) = (I − αA)ek .

On conclut par récurrence.

2. Dire que ek converge vers 0 est équivalent à dire que le rayon spectral de I − αAest strictement inférieur à 1. Les valeurs propres de I − αA sont (1− αλi)i=1,...,n où

(λi)i=1,...,n sont les valeurs propres de A rangées de manière croissante. On doit donca-

voir :

maxi=1,...,n

|1− αλi| < 1 c’est-à-dire :

−1 < 1− αλ1 ≤ ....1− αλn−1 ≤ 1− αλn < 1.

Dr.BelloufiMohammed - U Souk Ahras 66 Optimisation

Page 72: Cours d™Optimisation Sans Contraintes

3.8. SUGGESTIONS ET CORRIGÉS

On doit donc avoir d’une part α > 0 (car les valeurs propres de A sont toutes stricte-

ment positives), et d’autre part

− 2

α< −λ1 ≤ ....− λn−1 ≤ −λn,

c’est-à-dire 2α> λ1 ≥ ....λn−1 ≥ λn ; il suffi t donc que α < 2

λ1.

3. Le meilleur choix de correspond au cas où le rayon spectral ρ(I −αA) est minimal.

Or ρ(I − αA) = max |1− αλ1| , |1− αλn| . Une résolution graphique montre quemin max |1− αλ1| , |1− αλn| est atteint lorsque 1 − αλn = αλ1 − 1 , c’est-à-dire

lorsque α = 2λ1+λn

.

Exercice 041. A =

(12

0

0 c2

)et les valeurs propres sont 1

2et c

2.

2. r =

(−x

2

− cy2

)et la fonctionnelle J associée est :

J(x, y) =1

2

(x2cy2

)(x

y

)=

1

4

(x2 + cy2

).

Cherchons le minimum de ϕ(α) = J(xk + rk).

ϕ(α) =1

4

(x2k

(1− α

2

)2

+ cy2k

(1− αc

2

)2).

On vérifie que le minimum de ϕ est atteint pour ϕ = 2x2k+c2y2kx2k+c3y2k

.

3. Un calcul élémentaire donne

xk+1 =c2(c− 1)xky

2k

x2k + c3y2

k

et yk+1 = −(c− 1)x2kyk

x2k + c3y2

k

.

4. tk+1 = − 1c2tk

pour tout k. Donc tk+2 = tk ce qui signifie que les droites OPk+2 et

OPk sont parallèles. Par conséquent, pour tout k, les points O,Pk et Pk+2 sont alignés.

5. Calcul de τ 2 :yk+1

yk=

(1− c)x2k

x2k + c3y2

k

=(1− c)1 + c3t2k

.

Donc

τ 2 =(1− c)2

(1 + c3t2k)(1 + c3t2k+1

) =(1− c)2

(1 + c3t2)(1− 1

ct2

) .On retrouve après calcul la formule annoncée. La quantité τ est maximale quand

(ct− 1ct

)2 est minimum c’est-à-dire nul. La valeur de t correspondante est 1c.

Dr.BelloufiMohammed - U Souk Ahras 67 Optimisation

Page 73: Cours d™Optimisation Sans Contraintes

3.8. SUGGESTIONS ET CORRIGÉS

Exercice 08Si on cherche les zéros de la fonction f : x 7−→ α − 1

x, la méthode de Newton donne

précisément l’itération indiquée.

En généralisant aux matrices, l’algorithme devient :B0 donnée,

Bk+1 = Bk(2I − ABk).

Si on pose Ck = ABk, l’itération k s’écrit Ck+1 = 2Ck − C2k , c’est-à-dire I − Ck+1 =

(I−Ck)2 et par récurrence : I−Ck = (I−C0)2k = (I−AB0)2k . Donc la méthode converge

si et seulement si (I − AB0) < 1.

Lorsque A est symétrique, définie positive elle admet N valeurs propres réelles stricte-

ment positives λi. Si on choisit pour B0 = 1ρ(A)

I, un calcul rapide montre que ρ(I−AB0) <

1.

Exercice 09Dans le cas où les fonctions fi sont affi nes on obtient

∂ifj(x1, x2, ..., xn) = aij.

La méthode de Newton relaxée s’écrit alors pour 1 ≤ i ≤ n

xk+1i = xki −

i−1∑j=1

aijxk+1j +

n∑j=i

aijxkj − bi

aii,

c’est-à-direi∑

j=1

aijxk+1j = −

n∑j=i+1

aijxkj + bi.

On reconnait la forme matricielle : (D − L)xk+1 = Uxk + b , caractéristique de la

méthode de Gauss-Seidel (où D est la diagonale de A, L (respectivement U) l’opposée de

la partie triangulaire inférieure (respectivement supérieure) de A.

Dr.BelloufiMohammed - U Souk Ahras 68 Optimisation

Page 74: Cours d™Optimisation Sans Contraintes

Bibliographie

[1] M. Bergounioux, Optimisation et controle des systèmes linéaires, Dunod, Paris, 2001.

[2] M. Bierlaire, Introduction à l’optimisation différentiable, PPUR, 2006.

[3] M. Bazaraa, N. Sherali, and C. Shetty, Nonlinear Programming, Theory and Appli-

cations, John Wiley & Sons, New York, Second ed, 1993.

[4] J-F. Bonnans, J-C. Gilbert, C. Lemaréchal, C. Sagastizàbal, Optimisation Numé-

rique, Aspects théoriques et pratiques, Springer M&A 27, 1997.

[5] R. Fletcher (1987), Practical methods of optimization, John Wiley&Sons, Chichster.

[6] R. Fletcher, Practical Methods of Optimization vol. 1 : Unconstrained Optimization,

John Wiley & Sons, New York, 1987.

[7] J. C. Gilbert , Eléments d’optimisation différentiable : théorie et algorithmes, Notes

de cours, École Nationale Supérieure de Techniques Avancées, Paris, (2007).

[8] J-B. Hiriart-Urruty, Optimisation et analyse convexe, exercices corrigés, EDPs-

ciences, 2009.

[9] J. Nocedal, and S. J. Wright, Numerical Optimization, Springer Series in Operations

Research and Financial Engineering, second ed, 2006.

[10] Y. Yuan, Numerical Methods for Nonlinear Programming, Shanghai Scientific &

Technical Publishers, 1993.

69