République Algérienne Démocratique et populaire

Ministère de l’enseignement Supérieur et de la Recherche Scientifique

Université 08 Mai 1945 Guelma
Faculté de Mathématiques et Informatique Et Science de L a Matière

Département de Mathématiques

Polycopie de Cours

Présentés aux Etudiants

Licence Académique en mathématiques Option : Analyse

Par Dr.Amel Berhail

Intitulé

Octobre 2016

Table des matières

INTRODUCTION 03

Chapitre I : NOTIONS DE CONVEXITE 04

(a) Ensembles convexe 05

i. Opérations sur les ensembles convexes. . . 06
ii. Enveloppe convexe 06
iii. Théorème de séparation. . . 09
(b) Fonctions convexes 11
i. Définitions et propriétés d’une fonction convexe 11
ii. Continuité des fonctions convexes 12

1
 iii. Différentiabilité et fonctions convexes 13
iv. Sous différentiel et fonctions convexes. . . 13
v. Caractérisation des fonctions convexe 15
(c) Exercices 22

Chapitre II : OPTIMISATION SANS CONTRAINTES 24

(a) Généralités 24
(b) Quelques exemples 26
(c) Solution Optimale 28
(d) Résultats d’existence et d’unicité 28
(e) Direction de descente 32
(f) Conditions d’optimalité 33
i. Condition d’optimalité nécessaires du premier ordre 33
ii. Condition d’optimalité nécessaires du deuxième ordre. . . 34
iii. Condition d’optimalité suffisante du deuxième ordre 35
(g) Exercices 38

Contents

2
List of Tables

INTRODUCTION

3
L’optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre
analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonc-
tion sur un ensemble. Elle est aussi un sujet très vaste qui touche aussi bien au calcul des variations
qu’a la recherche opérationnelle (domaine à la frontière entre l’informatique, les mathématiques et
l’économie), dans les mathématiques appliqué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.
Aujourd’hui, tous les systèmes susceptibles d’être décrits par un modèle mathématique sont opti-
misés. La qualité des résultats et des prédictions dépend de la pertinence du modèle, de l’efficacité
de l’algorithme et des moyens pour le traitement numérique.
De façon générale, les techniques d’optimisations jouent un rôle de plus en plus important pour la
conception des systèmes et des équipements de toute nature, et toutes les décisions technique ou
économiques. Puisque les gens en général recherchent ce qu’il ya de meilleur et lorsque plusieurs
possibilités se présentent, leur choix se porte tout naturellement vers la variante « optimal ». Ce
mot provient du latin « optimum » qui veut dire meilleur et parfait.
Euclide formulait déjà des problème d’optimisation au IIIème siècle avant J-C. Sir Isaac Newton
(1642-1727), auteur du célèbre « Mathematical Principales of Natural Philosophy », ainsi que Got-
tfried Wilhelm Leibniz (1646-1716) offrirent, si c’est à l’antiquité que remonte les premiers problèmes
de maximum et de minimum, on peut dire que c’est à la fin du dix-septième et au dix- huitième
siècle qu’apparaissent les premières méthodes générales de solutions. Le développement de l’analyse
mathématique en particulier le calcul différentiel (newton, Pappus), l’introduction de fonctionnelle
(Euler, Lagrange) a permis à l’optimisation de jouer un rôle important dans le secteur des sciences
exactes, ou la plupart des principes physiques peuvent s’énoncer sous forme variationnelle.
Optimiser, c’est donner les meilleurs conditions de fonctionnement de rendement et d’un point de vue
mathématique l’optimisation consiste à rechercher le minimum ou le maximum d’une fonction avec
ou sans contraintes, cependant on limite souvent l’optimisation à une recherche de minimum. Plus
précisément on cherche par exemple à caractériser le point qui réalise un minimum d’une fonction
différentiable dans tous l’espace ou lorsque ce minimum est réalisé à l’intérieure de l’ensemble des
contraintes.

Les problèmes considérés ici s’écrivent sous la forme standard suivant: optimiser le problème
f (x ), x Rn où la fonction f est linéaire ou non ; donc pour choisir la possibilité optimal, on est
amené à résoudre les problèmes de recherche d’un maximum ou d’un minimum qui sont appelés
« Problèmes d’extrémums ».
Dans ce cours, nous nous intéressons aux méthodes numériques pour l’optimisation continue, dif-
férentiable. Le premier chapitre traite des notions mathématiques fondamentales à maîtriser avant
de s’intéresser à la résolution à proprement parler de tout problème d’optimisation : nous allons
donner quelques définitions et concepts de la théorie convexe.
Dans le deuxième chapitre, nous entrons dans le vif du sujet en nous intéressant à la résolution
de problèmes d’optimisation sans contrainte, nous tenterons de répondre aux questions suivantes :
Existe- t-il une solution du problème considéré ? si oui, a-t-on unicité ? Comment la caractériser ?
(conditions d’optimalité). Enfin, dans le chapitre 3 ; nous donnerons quelques méthodes numériques

4
pour la résolution des problèmes d’optimisation sans contraintes où on va répondre aux questions
suivantes : Comment calculer la solution optimal? et quel type d’algorithme choisir ?

Chapitre I

NOTIONS DE CONVEXITE

En mathématiques, le mot « convexe » est utilisé dans la désignation de deux notions bien distinctes
quoique apparentées : Lorsqu’il se rapporte à une forme géométrique, un ensemble de points, il
renvoie au concept d’ensemble convexe. Lorsqu’il se rapporte à une fonction, il renvoie au concept
de fonction convexe. En économie, la convexité est un indicateur de risque de taux directement
lié au concept mathématique de fonction convexe. Dans la langue courante le mot « convexité »

5
a un sens directement relié au concept mathématique d’ensemble convexe, la convexité d’un objet
désignant la partie de celui-ci qui a une forme bombée. On retrouve ce même sens en optique
géométrique, notamment pour qualifier des miroirs ou des lentilles.
Dans ce chapitre nous introduisons la notion d’ensemble et fonction convexe, démontrons leurs
principales propriétés géométriques et topologiques.

(a) Ensembles convexes

Définition : Un ensemble S de Rn est dite convexe si :

x x S, 0, 1, x 1 x S.

où bien

1, 2 1 2

x x S, , R, 1, x x S.

1, 2 1 2

En d’autre terme, Un objet géométrique S est dit convexe lorsque, chaque fois qu’on
y prend deux points x et y de S, le segment [x ,y] qui les joint est entièrement contenu dans S.

Exemples :

Non convexe

-Tout disque, ainsi un cube plein, une boule sont convexes.

• La couronne n’est pas un ensemble convexe. Ainsi tous objet creux ne l’est pas.
• Toutes partie affine est convexe car un ensemble S de Rn est dit affine si :

x 1, x 2 S, R, x 1 1 x 2 S.

• La partie de Rn définie par {x de Rn ; x positif} est un convexe appelé orthant positif.

6
 i. Opérations sur les ensembles convexes

Proposition 1:

• Soit (S , i I N ) convexe de R n
, alors ( S

) est un convexe mais ( ∪ S

) n’est pas

nécessairement un ensemble convexe.

iI i

i1,n i

• Soit S R n un ensemble convexe, alors S est un convexe.

• Soit S Rn un ensemble convexe avec int( S )

• La somme de deux convexes est un convexe.

, alors int( S )

est un convexe.

• Le produit d’un convexe avec un scalaire est un convexe.

• L’image directe et l’image réciproque d’un convexe par une application linéaire est un
convexe.

Preuve : Exercices

Combinaison convexe

Définition : On appelle combinaison convexe d’un ‘n’ éléments x R n

tout élément y de Rn
s’écrit sous la forme:

7
 y

i1

i xi

avec les points

i 0 et

i 1

i 1.

i. Enveloppe convexe

Définition :

L’enveloppe convexe d’un ensemble S R n d’éléments x R n est l’ensemble de toutes les combi-
naisons convexes des points x R n .
C’est aussi le plus petit convexe contenant S qui est donc l’intersection de tous les convexes con-
tenants S, on le note par H(S) ou Conv(S) :

x H (S ) x , x ,. ,x

S et ,..., R

1 et x x .

1 2 n

et

1 n i1 i

i i

i 1

Exemple :

8
 • Soit S x,
H (S ) ∩A, A est un convexe contenant S
y alors H(S) est le segment [x, y].

• Soit S x, y, z alors H(S) est un triangle fermée de sommets x, y, z.

Proposition 2:

Soit S Rn quelconque alors H(S) est convexe. De plus, H(S) est le plus petit convexe qui contient
S.

Preuve :

p p

Soit

et

x H (S ) 1 ,...p R et

y H (S ) 1 ,...l R et

x 1 ,..., x p S tq

y 1 ,..., y l S tq

1 et

i1

9
1 et

j 1

x i xi .

i1

y j y j .

j 1

Soit 0,1 : x (1 ) y (1 x 1 ... p x p )(1 )(1 y 1 ... l yl )

= 1 x 1 ... p x p (1 )1 y 1 ... (1 )l yl

Avec i 0,

(1 ) j 0,

i 1,. , p;

j 1,...., l et

1 ... p (1 )1 ... (1 )l (1 ... p ) (1 )(1 ... l )

= .1 (1 ).1=1

Donc x (1 ) y H (S ) H (S ) convexe.

Remarque: L’enveloppe convexe d’un ensemble fini non vide de R n

s’appelle un polytope.

Un cas particulier d’un polytope est le simplexe : l’enveloppe convexe de (n+1) points (v 1 ,...,
v n1)

affinement indépendants de R n
:

Conv (v ,..., v

) n1 v,

0,
k

10
 1 n1

i i i

i1

i i1

1.

Les points (v 1 ,..., v n1) s’appellent les sommets du simplexe.

Théorème de Carathéodory : Soit S une partie de Rn ( ou d’un espace vectoriel E de dimension

n). Alors tout élément de conv (S) peut s’écrire comme une combinaison convexe de ( n + 1)
éléments de S

Remarques

S R n , Conv(S)= { y

k n1 i1

i xi ,

xi S

i 0 et

n1 i1

i 1. }

1-Un ensemble S Rn est dite strictement convexe s’il vérifie

x 1, x 2 S ;

x1 x2 ,

0,1,

x 1 1 x 2 int( S ).

2–Un ensemble S Rn est dite fortement convexe s’il vérifie

x 1, , x 2 S ;

11
x1 x2 ,

0,1,

0;

B (x 1 1 x 2 ,) S. 1

S Rn est fortement convexe S strictement convexe S convexe

1 c’est la boule de centre x 1 1 x 2 et de rayon .

i. Théorème de séparation
Supposons que nous avons deux ensembles convexes dans R n , quand pouvons nous les
séparer par un hyperplan ? c’est-à-dire trouver une forme linéaire non nulle qui en tout
point d’un des ensembles est supérieur ou égale a sa valeur en n’importe quel point de
l’autre ensemble ?
La réponse forme, dans un sens, le cœur de l’analyse convexe.

Définition : Soit

p Rn ,

p 0 et R. On appelle Hyperplan H l’ensemble suivant :

P : s’appelle vecteur normal à H.

H ( p,) x Rn ,

( p,

x) .

A tout hyperplan H on associé H+ et H- définie comme suit :

12
H x Rn ,

H x Rn ,

pt x demi espace supérieure fermé.

pt x demi espace inferieure fermé.

Remarque : Si x ^ H donc

pt x ^

et puisque x H,

pt x donc : pt (x x ^) 0, donc

Définition :

H x Rn ,

pt (x x ^) 0.

1. Soient S1, S2 deux ensembles non vide de Rn on dit que l’hyperplan H ( p, ) sépare
simplement les

ensembles S1, S2 sii

pt x pt x , x S , x S

c-à-d :

1 2 1 1 2 2

pt x ,

x S1

(S H ) et

13
pt x ,

x S2

(S H )

1. Si, en plus de (a) on a : S 1 S 2 H , on dit que H sépare proprement S1 et S2.

2. On dit que l’hyperplan H ( p, ) sépare strictement S1, et S2 ssi :

pt x ,

x S 2 et

pt x ,

x S1

c)L’hyperplan H ( p, ) sépare fortement S1, et S2 ssi :

Exemple :

0, pt x ,

x S 2 et

pt x ,

x S1

• L’hyperplan donné par

pt x 1 dans R, sépare proprement les ensembles convexes

S x R / x 1 et T x R / x 1.

• L’hyperplan donné par

pt x x

14
 •
x1

1 dans R2 ,

sépare proprement les ensembles convexes

S x R 2 , 0 x 1, 3 x

1 2

5 et T x R 2 ,

x 1 1,

x 0.

Remarque :

La séparation forte la séparation propre.

Théorème de séparation fondamental

Soit S R n
convexe fermé non vide et

y S , alors il existe p Rn ,

p 0 et R, tel que

pt y ,

pt x ,

x S

15
En d’autres terme, il existe un hyperplan H du vecteur normal p et une constante qui sépare le
point

y et S.

Preuve : D’après le théorème de meilleure approximation x ^ S tel que

Prenons

( y x ^)t (x x ^) 0,

x S

(∗)

p y x ^, p 0 et ( y x ^)t x ^

Donc

pt y (y x ^)t y (y x ^)t x ^ (y x ^)t (y x ^)

y x^
• 0,

On obtient de (∗) que

pt y 0,

(non nul si non y S contrad iction) pt y .

pt (x x ^) 0 pt x pt x ^ pt x . .

(a) Fonctions convexes Définition :

Soit une fonction f : S → R défini sur un sous-ensemble S convexe non vide de Rn à valeurs
réelles. La fonction f est dite convexe sur S si et seulement si pour tous x1, x2 ∈ S

0,1,

f (x 1 (1 )x 2 ) f (x 1 ) (1 ) f (x 2 )

16
f(x2)

f (x 1 ) (1 ) f (x 2 )

f (x 1 (1 )x 2 )

f(x1)

x1 x 1 1 x 2 x2

-Si l’inégalité ci-dessus est stricte quelques soient x 1 x 2 et 0 < λ < 1, la fonction f s’appelle
Strictement convexe c’est à dire

x 1 , x 2 S, x x , 0,1, f (x 1 (1 )x 2 ) f (x 1 ) (1 ) f (x 2 ) .

-La fonction f est dite fortement convexe ou convexe sur S s’il existe 0 tel que :

x , x S, x x

, 0,1,

f (x (1 )x ) f (x ) (1 ) f (x ) 1 ..(1 ) x x 2 .

1 2 1 2

1 2 1

2 2 1 2

Remarque :

• La fonction f sera dite concave si et seulement si (-f ) est convexe.

17
 • Une fonction réelle d’une variable réelle est dite convexe si son graphe est « tourné vers le
haut » ; on veut dire par là que si A et B sont deux points du graphe de la fonction le segment
[A,B ] est entièrement situé au-dessus du graphe. À l’inverse, une fonction dont le graphe est
« tourné vers le bas » est dite concave.

• Une fonction fortement convexe est donc strictement convexe avec une inégalité de convexité
renforcée par un terme quadratique lui donnant une courbure au moins égale à . Donc :

convexe Strictement convexe Convexe.

3-Si f et g sont deux fonctions convexes, alors (f+g ) est une fonction convexe (il suffit de s’appuyer
sur la définition et de sommer les deux inégalités).
Exemples :

• La fonction

f : x x

est convexe puisque d’après l’inégalité triangulaire

x 1, x 2 R, x 1 (1 )x 2

x 1 (1 ) x 2

; 0;1.

• Toute fonction affine est convexe et concave à la fois.

Proposition : Soit S R n
convexe non vide et

f : S R,

R,

et S l’ensemble de niveau

donné par :

si f est convexe alors S

S x S,

est convexe.

f (x ) ,

18
Preuve : Soient

x1 , x2 S
donc :

f (x 1 )

et f (x 2 ) . On veut démontrer que

x 1 1 x 2 S , avec 0,1

En effet,

f (x 1 (1 )x 2 ) f (x 1 ) (1 ) f (x 2 )

(car

f est convexe )

x 1 1 x 2 S , d’où S

est un convexe.

I .2.1. Définitions et propriétés d’une fonction convexe Epigraphe d’une fonction

convexe

Définition : Soient S un ensemble de Rn non vide et f : S →R. L’épigraphe de f qu’on note «

epi(f) »

est un sous ensemble de Rn+1 défini par :

qui est équivaut à

19
epi ( f ) (x, y) Rn 1 / x S, y R, y f (x )

epi ( f ) (x, y) S R, y f (x )

C’est à dire l’ensemble des points qui sont au-dessus du graphe de f.

Théorème :

Soient S un ensemble convexe de Rn non vide et f : S → R, alors

La fonction f est convexe L’ensemble (epi(f)) est convexe.

epi(f) Convexe epi(f) Non convexe

Preuve :

• La fonction f est convexe epi(f ) est convexe

Soientx 1 , y 1 , x 2 , y 2 epi ( f ) y 1 f (x 1 ), y f (x ) , et pour tout 0,1, on a

y 1 (1 ) y 2 f (x 1 ) (1 ) f (x 2 ) f (x 1 (1 )x 2 ) car f est convexe

Donc (x 1 (1 )x 2 , y 1 (1 )y 2 )epi ( f )

x 1 , y 1 , x 2 , y 2 epi( f ),

0,1,

(x 1 , y 1 ) (1 )x 2 , y 2 epi( f ).

• epi(f ) est convexe f est convexe

Soit epi(f ) un ensemble convexe, donc :

x 1 , f (x 1 ), x 2 , f (x 2 )epi ( f ) (0,1) , (x 1 , f (x 1 )) (1 )(x 2 , f (x 2 )) epi( f )

(x 1 , f (x 1 )) (1 )(x 2 , f (x 2 )) (x 1 (1 )x 2 , f (x 1 ) (1 ) f (x 2 )) epi( f )

f (x 1 (1 )x 2 ) f (x 1 ) (1 ) f (x 2 ) . On obtient la convexité de f.

20
Remarque :

• À l’inverse, une fonction est dite concave c’est alors son hypergraphe - l’ensemble des
points qui sont en-dessous du graphe - est convexe.

• La projection de epi(f ) sur Rn est appelé domaine effectif de f

dom( f ) x Rn ; f (x )

x Rn ; R,

(x ;) epi ( f )

Dans ce cas, si f est une fonction convexe alors dom(f ) est un convexe (image du convexe par une
application linéaire).

Inégalité de Jensen

Proposition : Soit f une fonction convexe et soit S le domaine de f. Alors pour n’importe quelle
combinaison convexe

i xi i 1

n n

des points de S, on a

f ( i xi ) i f (xi )

i 1 i1

Cette inégalité est appelée « inégalité de Jensen ».

Preuve : La preuve est immédiate :

les points (f(xi), xi) appartiennent clairement à l’épigraphe de f ; comme f est convexe, son épigraphe
est un ensemble convexe, de sorte que la combinaison convexe

n n n

i ( f (xi ), xi ) ( i f (xi ), i xi )

i 1

21
 i 1

i 1

de ces points appartient également à l’ensemble epi(f ). Par la définition de l’épigraphe, ça implique

i1

f (xi )

f ( i xi ) .

i 1

i. Continuité des fonctions convexes Proposition :

Soient S un ensemble de Rn non vide et f : S → R une fonction convexe ; alors f
est continue dans
int( S ) .
Preuve : Une fonction convexe définie sur un ouvert de Rn est localement lipchitzi-
enne, donc localement absolument continue, et donc continue

i. Différentiabilité et fonctions convexes Dérivée directionnelle :

En tout point de son domaine, une fonction convexe admet des dérivées directionnelles
suivant toutes directions.

Définition 1: Soient

S R n ,

f : S R,

22
x ^ S et " d "

un vecteur

de R n tq (x ^ d ) S,

pour asssez

petit

( 0). La

dérivée directionnelle de f au point x ^ dans la direction « d » qu’on note f ’ (x ^, d ) est donnée

par la

limite (si elle existe) suivante :

Définition 2:

f ’ (x ^, d ) lim

f (x ^ d ) f (x ^)

Soient S Rn , f : S R,

x^ S .

La fonction f est dite différentiable au point x ^ , s’il existe un vecteur

f (x ^) de Rn nommé « le gradient de f en x ^ » et une fonction : Rn R tq :

f (x ) f (x ^) f (x ^)t (x x ^)

x x ^ (x ^, x x ^),

23
x S,

où (x ^, x x ^) 0 quand

x x ^.

Remarques

• Le gradient d’une fonction f en un point x ^ x , x ,..., x t est le vecteur de Rn donné par :

1 2 n

f f t

f (x ^) x (x ^),..., x (x ^)

1 n

• On dit que f est différentiable dans Rn si elle est différentiable en tout point de Rn . 3-Si f est
différentiable en un point x ^ de Rn alors f est continuent au point x ^ .

i. Sous différentiel et fonctions convexes

En mathématiques, le sous-différentiel est un concept permettant de décrire la
variation locale d’une fonction convexe (à valeurs réelles) non nécessairement dif-
férentiable, donc ; le sous- différentiel est un substitut de la notion de gradient pour
les fonctions convexes non différentiables.
Au lieu d’être la pente de l’application linéaire tangente (c’est-à-dire, la dérivée) au
point considéré, qui n’existe pas nécessairement, le sous-différentiel d’une fonction
convexe est l’ensemble des pentes de tous les minorants de la fonction, qui sont
exactes en ce point, c’est-à-dire qui ont en ce point la même valeur que la fonction
convexe qu’elles minorent.
La convexité de la fonction assure qu’on peut lui trouver des minorants exacts en
presque tout point de son domaine ; on met donc à profit cette propriété pour définir
le sous-différentiel.

a-Sous différentiel d’une fonction à une seule variable

Une sous-dérivée d’une fonction convexe nombre réel tel que

24
f : I R, en un point x ^ de l’intervalle ouvert I de R est un

pour tout x dans I.

f (x ) f (x ^) (x x ^).

On peut montrer que l’ensemble des sous-dérivées en x ^ est un ensemble non vide qui et un intervalle
fermé de la forme a, b , avec a et b les bornes :

a lim

xx

que l’on sait exister et vérifier. a b

f (x ) f (x ^)

x x^

b lim

xx

f (x ) f (x ^)

x x^

L’ensemble a, b

de toutes les sous-dérivées est appelé le sous-différentiel de la fonction f en x ^ , on

le note par : f (x ^) .

Exemple : La fonction

f (x ) x

n’est pas différentiable en 0. On calcule f (0)

25
f (0) f (x ) f (0) (x 0),
x R. x x,
x R f (0) 1,1.

Le sous-différentiel en n’importe quel point x 0<0 est le singleton {−1} et le sous-différentiel en

n’importe quel point x 0>0 est le singleton {1}.
b-Sous différentiel d’une fonction de plusieurs variables Définition :

-Soient S Rn un ensemble convexe, et

f : S R,
Rn est appelé sous-gradient de f au point

x^ S
sii
t
f (x ) f (x ^) (x x ^),
x S.

-L’ensemble de tous les sous gradient de f au point x ^ S

par : f (x ^) .
s’appelle : « sous-différentiel » et on le note

Les sous gradient en rouge On dit que f est sous différentiable en x si f (x ) 0

26
Exemple :

On considère la fonction

f : R 2
R définie par

f (x, y) x 2 y

. Déterminer le sous-différentiel de f

au point (1,0) ?

f (1,0) (1, ), 2,2

i. .Caractérisation des fonctions convexe A-Fonction d’une seule variable

Soit f une fonction dérivable sur un intervalle I de R. On dit que f est convexe si et seule-
ment si sa courbe représentative est au-dessus de chacune de ses tangentes, autrement
dit, si l’image du barycentre est plus petit que le barycentre des images.
Proposition :

Soit f une fonction dérivable sur un intervalle I de R. On dit que f est convexe si et seulement si
sa dérivée est croissante sur I, c-à-d :

La fonction f est convexe f ’ est croissante sur I

Preuve :

• Supposons que f convexe et montrons que f ’ est croissante.

Soient 0 1 2

. Alors, par la convexité de f

1 1 1 1

f (x 1 d ) f 1 x (x 2d ) 1 . f (x )

f (x 2 d)

27
 2 2 2 2

Donc

f (x d ) f (x ) f (x
1 2 d ) f (x )

1 2

D’où le résultat.

• Supposons que f croissante, et montrons que f est convexe. Soient donc x,y tel que y > x.
Montrons que l’application : t → tf(x) + (1 − t)f(y) − f(tx + (1 − t)y)

est positive sur [0, 1]. On constate que (0) = (1) = 0. De plus,

(t) = f(x) − f(y) + (y − x)f((x − y)t + y).

Or y − x > 0, donc on a (t) = k + af(y − at), avec a > 0. Cette fonction est décroissante,
puisque f

est croissante. Si (1) > 0, alors quelque soit t ∈ [0, 1],

(t) > 0 et (1) = (0) +

(t) dt > (0) = (1),

ce qui est absurde. D’où (1) ≤ 0.

Par un raisonnement analogue, on montre que (0) ≥ 0. De là, on déduit facilement que :
∀t ∈ [0, 1], (t) ≥ 0 (sinon, en raisonnant sur les valeurs de la dérivée notamment, on trouve
rapidement une contradiction). Donc f est convexe.

Corollaire :

Soit f une fonction deux fois dérivable sur un intervalle I de R. La fonction f est convexe si et
seulement si sa dérivée seconde f ” est à valeurs positives ou nulles.

28
 La fonction f est convexe f ” 0 sur I.

La fonction f est concave f ” 0 sur I.

Exemples :

• la fonction

f (x ) x 2

est convexe car

f ’ ’ (x ) 2 0,

x R.

• la fonction

f (x ) exp x est convexe car

f ’ ’ (x ) exp x 0,

x R.

• la fonction f (x ) ln x est concave car

Inégalité de pentes

f ’ ’ (x ) 1

x 2

0,

x 0;.

• Soit

x0 I ,

29
 P désigne la fonction réelle, définie sur I /x 0 par :

x I /x 0 ,

P (x )

f (x ) f (x 0 ) .

x x0

On dit que P

est une fonction de pente issue de

x0 .

• Soit f une fonction réelle, dérivable et convexe, x 0 , y 0 I avec x 0 y 0 , alors

Proposition :

f ’(x 0 ) Px ( y 0 ) f ’( y 0 )

Soit f une fonction réelle, dérivable. IL ya une équivalence entre 1-La fonction f est convexe sur I.

2-Pour tout (a, b, c) I 3

tel que

a<b<c ; on a

f (b) f (a)

b a

f (c) f (a)

c a

f (c) f (b)

30
 c b

3-Pour tout x 0 I ,

P est croissante sur son ensemble de définition.

B-Fonction de plusieurs variables Théorème 1 :

Soient S Rn convexe non vide et f : S R , On suppose que f admet en chaque point x ^ int( S )
un

sous-gradient tel que

Alors f est convexe dans int(S).

t
f (x ) f (x ^) (x x ^),

x S.

Preuve :

Soient x 1 , x 2 int( S )

et 0,1.

31
int( S ) est convexe donc x 1 1 x 2 int( S ) et comme f a un sous

gradient en x 1 1 x 2

, c’est-à-dire

Prenons x=x1 on obtient

f (x ) f (x 1

1 x2

) t (x (x

1 x 2 )),

x S.

f (x ) f (x 1 x ) t 1 (x x ),

x S.

1 1 2 1 2

Prenons maintenant x=x2 on obtient

(1)

f (x ) f (x 1 x ) t (x x ),

x S.

2 1 2 1 2

(2)

Multipliant (1) par et (2) par 1 on aura :

f (x 1 (1 )x 2 ) f (x 1 ) (1 ) f (x 2 )

32
Donc, f est convexe dans int(S).

Remarque :

Si l’ensemble S est ouvert, l’existence du sous gradient est assurée partout dans S.

Théorème 2 :

Soient S Rn un ouvert, convexe et non vide et

f : S R une fonction différentiable, alors :

1. La fonction f est convexe sur S si et seulement si

x^ S;

f (x ) f (x ^) (f (x ^))t (x x ^),

x S.

1. La fonction f est strictement convexe sur S si et seulement si

x^ S;

f (x ) f (x ^) (f (x ^))t (x x ^),

x S, x x ^.

33
Preuve :

• Nécessité
Comme la fonction f est différentiable sur l’ouvert S donc elle est différentiable en chaque
point x ^ de

S alors f admet en x ^ un seul sous gradient qui est f (x ^). (f (x ^) f (x ^)).

Soit f convexe ; alors pour toutes paire de points x, x ^

de S et pour tout (0,1)

Ce qui s’écrit sous la forme

f (x (1 )x ^) f (x ) (1 ) f (x ^)

f (x ^ (x x ^)) f (x ^) ( f (x ) f (x ^))

Se référent au théorème de Taylor, il existe (0,1) tel que

f (x ^ (x x ^)) f (x ^) f (x ^ (x x ^) (1 )x ^t ( y (x x ^) x ^)

f (x ^ (x x ^)) f (x ^) f x ^ (x x ^)t (x x ^) .

Combinant les deux relations,

f x ^ (x x ^)t (x x ^) ( f (x ) f (x ^))

Par conséquent, en prenant la limite lorsque 0 on obtient

lim f x ^ (x x ^)t (x x ^) lim ( f (x ) f (x ^))

Ou encore

• Suffisance

(f (x ^))t (x x ^) ( f (x ) f (x ^)) f (x ) f (x ^) (f (x ^))t (x x ^),

34
Puisque donc

f (x ) f (x ^) (f (x ^))t (x x ^),

x S

f (x ) f (x (1 )x ^) (f (x (1 )x ^))t (x x (1 )x ^),

f ( y) f (x (1 )x ^) (f (x (1 )x ^))t ( y x (1 )x ^),

Les deux inéquations s’écrivent respectivement

f (x ) f (x (1 )x ^) (1 )(f (x (1 )x ^))t (x x ^),

et

f ( y) f (x (1 )x ^) f (x (1 )x ^))t (x x ^),

Multipliant la première par (lamda) et la deuxième par (1-lamda)

f (x ) f (x (1 )x ^) (1 )(f (x (1 )x ^))t (x x ^),

(1 ) f (x ^) (1 ) f (x (1 )x ^) (1 )f (x (1 )x ^))t (x x ^),

Additionnons les deux relations résultantes

f (x (1 )x ^) f (x ) (1 ) f (x ^)

Remarque :

Du théorème précédent, on conclut que la fonction

f (x ^) est monotone sur S c’est-à-dire :

f (x ) f (x ^), x x ^

Fonction convexe deux fois différentiable Définition :

0,

35
x, x ^ S.

Soient S Rn , f : S R,

x^ S .

La fonction f est dite deux fois différentiable au point x ^ , s’il existe un

vecteur

f (x ^)

de Rn nommé « le gradient de f en x ^ » et une matrice symétrique H (x ^)

d’ordre (n ,n)

appelé « matrice Hessienne » et une fonction : Rn R tq :

f (x ) f (x ^) (f (x ^)) t (x x ^) 1 (x x ^)t H (x ^)(x x ^) x x ^ 2 (x ^, x x ^),

x S,

où (x ^, x x ^) 0

quand

x x ^.

La matrice Hessienne du vecteur x ^ (x , x ,..., x )t

est donnée par

2
f

2
x

36
(x ^),. ,

2
f

x x

(x ^)

1 n 1

...................................

H (x ^)

..................................

2 2
f f

,.......,

x x

2
x

(x ^)

1 n n

Remarque :

Si f est une fonction de classe C² ( admet des dérivées partielles d’ordre 2 continues) donc

2
f

xi x j

2
f

(x ^) x x

(x ^),

37
i, j 1,..., n

et le hessien de f est une matrice symétrique.

Définition :

Soit H (x ^) la matrice Hessiene de la fonction f au point x ^ , alors

• La matrice H (x ^) est dite semi-définie positive (SDP) et on note « H (x ^) 0 » ssi :

x Rn , xt H (x ^)x 0

Donc , toutes les valeurs propres de la matrice H (x ^)

sont positives.

• La matrice H(x) est dite définie positive (DP) et on note « H (x ^) 0 » ssi :

x Rn ,

xt H (x ^)x 0

Donc, toutes les valeurs propres de la matrice H (x ^)

sont strictement positives.

Remarque :

• Soit « H » une matrice définie positive. Alors, il existe une matrice orthonormée « G » telle
que « Gt HG » étant une matrice diagonale dont les éléments sont les valeurs propres de H,
et donc positifs.

38
 • Si la matrice « H » est définie positive alors elle est inversible car les valeurs propres

( i 1,..., n) sont strictement positives et comme det H donc

i1

det H 0

Théorème :

Soient S Rn ouvert convexe non vide et S, alors

f : S R, une fonction réelle deux fois différentiable dans

1. La fonction f est convexe dans S si et seulement si la matrice hessienne est semi définie
positive (s.d.p) en tout point de S.

2. La fonction est strictement convexe dans S si et seulement si la matrice hessienne est définie
positive (d.p) en tout point de S.

Preuve :

a) 1-Supposons que f est convexe dans S et montrons que H (x ^)

La fonction f est convexe sur S si et seulement si
semi définie pour tout x ^

x^ S;

f (x ^ x ) f (x ^) .(f (x ^))t x,

x S.

(1)

Et comme la fonction f est deux fois différentiable dans S, alors

f (x ^ x ) f (x ^) .(f (x ^))t .x 1 .2 .xt H (x ^).x 2 x 2 (x ^, x ),

x S,

39
(2)

De (1) et (2), on a

1 .2 .xt H (x ^).x 2 x 2 (x ^, x ) 0,

On devise par et lorsque 0 , on obtient xt .H (x ^).x 0.

• Supposons que H (x ^)

montrons que
semi définie pour tout x ^ et montrons que f est convexe dans S c-à-d

x^ S;

f (x ) f (x ^) (f (x ^))t (x x ^),

x S.

En effet, soient x, x ^

quelconques de S

f (x ) f (x ^) (f (x ^))t (x x ^) 1 (x x ^)t H ( )(x x ^);

où x, x ^ donc

tx (1 t)x ^,

t 0,1

40
f (x ) f (x ^) (f (x ^))t (x x ^) 1 (x x ^)t H ( )(x x ^) 0;

car

H est s.d.p

D’où la convexité de f.

Exemple :

Soit la fonction

f : R 3 R 3 définie par

f (x, y, z ) (x 1)2 ( y 1)2 z 2

.

f est-elle convexe ?
On sait que la fonction f est 2 fois différentiable sur R3 , et

f est convexe H (x, y, z ) 0,

• Calculons le gradient

(x, y, z ) R 3

x (x, y, z ),

2(x 1

f (x, y, z ) (x, y, z ), 2( y 1) .

41
 2z

f (x, y, z )

– Calculons la matrice hessienne

H (x, y, z ) 0

0 0

2 0

1 0

201

0 0;

(x, y, z ) R 3 .

La matrice hessienne a trois valeurs propres :

1 2 3 2 0

42
Donc, elle est semi définie positive, on conclut que la fonction f est convexe.

Exercices du chapitre 1

Exercice 1 :
–——————————————————————————————————

Les quels parmi les ensembles ci-dessous sont convexes

S x, y R 2 ;

x 0 et y 0; 1.

S x, y, z R 3 ;

y 0, z 0

S x, y R 2; x y 3 et 1 x 2. ,

S x, y R 2 ; (x 2 1)2 y 2 4

S x, y R 2 ;

y x2

0.

S x R n ;

xi 1

i1

S x, y R 2 ; x 0, y 0, x y 1

43
. S (x , x ) R 2 , x 2 x 2 5,

3x x 6 .

S y y,y,y t R3,

1 2 1 2

y 1, y 2 y 1

1 2

1 2 3

1 2 3

Exercice 2 :
–——————————————————————————————————--

Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse (justifier)

• La somme de deux convexes est un convexe.

• Le produit de deux convexes est un convexe

• Soit S

Rn , (i 1,..., n), convexe. Alors ( ∩ S ) et ( ∪ S ) est un convexe.

i i

i 1,n

i1,n i

• Soit un ensemble S Rn convexe. Alors S convexe.

44
 • Soient un ensemble S Rn convexe et deux réels positifs ,

• Tout ensemble affine est convexe. La réciproque est vraie.

. Alors :

S S ( )S .

• Les polyèdres vecteur de Rm .

S x /

Ax b

sont des convexes de Rn où A est une matrice (m.n) est b un

Exercice 3
:————————————————————————————————————

Les fonctions suivantes sont-elles convexes ?

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

•
f (x ) x ,

( N )

•
f (x ) ln x

– f (x ) e x

2
x 2x f (x )

•
f (x ) 2x 3 3x 2

3 x 1

45
x 1 , . f (x, y) x

x 3 où x 1

sur l ’ensemble

(x, y) R 2 ,

y 0

• f (x ) x 2 , S x R, 2x 5 0.

• f (x, y) x 2 2 y 2 5xy, S (x, y) R 2 ,

x 0,

y 0,

x y 1

• f (x, y) (x 2)2 (y 1)2 , R, S (x, y) R 2 , x 0, y 0, x 2 (y 1)2 2

Exercice 4:

• La composée de deux fonctions convexes est-elle convexe ?

• Soient f et g convexes sur intervalle I de R, que dire de sup( f , g) et

inf( f , g)

• Soit N une norme sur Rn , et S une partie convexe de Rn . On définit par

46
 d (x, S ) inf N (x y)

yS

Montrer que la fonction x d (x, S )

est une fonction convexe sur Rd ?

• Soit f : R 3 R 3 la fonction définie par :

f (x 1 , x 2 , x 3 ) x 1
2 3
x x

S’agit-il d’une fonction convexe ? Strictement convexe ? Écrire son sous-différentiel.

Exercice 5 :

Soit C un sous-ensemble ouvert convexe non vide de Rn et

f : Rn R une application différentiable sur

C. Montrer que les propositions suivantes sont équivalentes:

1. f est convexe sur C ; 2. Pour tout x ; y C,

f ( y) f (x ) f ( y), y x

1. L’application f est monotone sur C, c’est-à-dire ∀ x,y∈ C, f ( y) f (x ), y x 0.

Montrer que si, de plus, f est deux fois différentiable sur Rn , alors

f est convexe sur Rn ⇔∀ x∈ Rn , 2f (x) est semi-définie positive

Exercice 6 :

Soit

f : RN RN

47
la fonction définie par, N N est une matrice Aavec

f (x ) 1 ( Ax, x ) (b, x )

symétrique, b RN .

(a) Montrer que f est différentiable sur RN .

(b) Calculer le gradient et la matrice Hessienne de f.
(c) Montrer que f est convexe ssi A est semi définie positive.
(d) Montrer que f est strictement convexe ssi A est définie positive.

Exercice 7 :

Soit

f ; I R . Pour a I

on définit la fonction :

p a ( f )(x )

f (x ) f (a)

pour tout x I / a

x a

• Montrer que f est convexe sur I ssi pour tout

I /a .

a I ,

p a ( f ) est une fonction croissante sur

• En déduire que, si f est convexe sur I, pour tout a I , f est dérivable a droite et à gauche
en a

48
 ◦

et que fg ’ (a) fd ’ (a) . Montrer aussi que, si a b I , fd ’ (a) pa ( f )(b) fg ’ (b) .

Chapitre II

OPTIMISATION SANS CONTRAINTES

L’optimisation sans contraintes est une sous-discipline de l’optimisation mathématique, dans laque-
lle l’ensemble admissible est l’espace tout entier. Ces problèmes sont plus simples à analyser et à
résoudre que les problèmes d’optimisation avec contraintes.

(a) Généralités
L’optimisation a un vocabulaire particulier, pour cela nous allons introduire quelques
notations et définitions classiques. Tout d’abord, nous donnons la formulation générale
d’un problème d’optimisation, donc on a besoin d’:

-Une fonction objective ou fonction de coût ou critère, à minimiser, noté

f : Rn R

-Un ensemble
S Rn où l’on va chercher la solution, on dit que S est l’ensemble des éléments

admissibles du problème ou bien l’ensemble des contraintes.

On cherche à minimiser f sur S c’est à dire on cherche x de S tel que :

Remarque :

f (x ) min

yS

f ( y) f (x ) f ( y),

y S

49
Lorsque l’on utilise la notation « inf » pour un problème d’optimisation c’est à-dire "inf f(x)" cela
indique que l’on ne sait pas, si la valeur du minimum est atteinte. On utilise de préférence la notation
"minf(x)" mais il ne s’agit pas d’une convention universelle. Pour les problèmes de maximation, les
notations "sup et max" remplace "inf et min" respectivement.
L’optimisation se scinde en deux type de problèmes: sans et avec contraintes, dans les deux cas, le
but est de trouver les valeurs qui maximisent ou minimisent une fonction.
a-Optimisation sans contrainte
Nous allons étudier le problème d’optimisation sans contraintes où on effectue la minimisation de
la

fonction suivante :
f : Rn R sur tout l’espace R. Nous considérons donc le problème formulé de la façon

qui peut réécrire sous la forme

(P ) min

f ( y);

y Rn

trouver x Rn tel que

f (x ) f ( y),

y Rn

b-Optimisation sous contrainte

Le problème d’optimisation avec contraintes s’écrit sous la forme :

(P )

min

f ( y);

y S

50
trouver x S tel que

f (x ) f ( y),

y S

S est l’ensemble des contraintes sous forme d’égalité et d’inégalité telle que pour (p,q) de N

x Rn ,

g i (x ) 0, i 1,. ,p

tel que:

h (x ) 0; j 1,. ,q ,

-La fonction g(x ) g (x ); g (x ),....., g (x ) est une fonction de plusieurs variables x de R à

valeurs dans R, qui représente les contraintes en égalités.

-La fonction h(x ) h (x ); h (x ),....., h (x )est une fonction de plusieurs variables x de R

1 2 q

à valeurs dans R, qui représente les contraintes en inégalités.

Nous noterons ces types de problèmes ainsi :
-(PCE) Problème avec contraintes d’égalité.
-(PCI) Problème avec contraintes d’inégalité.

Exemple :

1-Quelle est la valeur maximale de la fonction :

f ( A, B, C ) sin Asin B sin C ,

sous la contrainte :

A B C .

51
C’est un problème d’optimisation avec contraintes d’égalité. 2-Maximiser la fonction objective

f (x 1 , x 2 ) 1200 x1 + 1000 x2

sous les contraintes : 3 x1 + 4 x2 160, 6 x1 + 3 x2 180, x1 0 ; x2 0. C’est un problème d’optimisation

avec contraintes d’inégalité.

Remarque :

• Plus généralement, on peut remplacer l’espace R par un espace vectoriel topologique sur R
de dimension fini.

• Pour la maximisation, faire la minimisation de la fonction (-f ):

max

f (x ) min

f (x ).

(a) Quelques exemples d’optimisation

II.2.a : Exemple 1
On veut acheter les aliments au plus bas prix possible qui fourniront les besoins journaliers de
calories ( au moins 2000) protéines ( 30 unités) et fibre ( 20 unités), les aliments disponibles
sont la viande ( un kilo à un prix de 500 dinars fournit 800 calories, 10 unités de protéines et
2 de fibre) des fruits ( 200 cal, 6 et 4 unités à prix de 200 dinars) et du riz (100 cal, 5 et 4
unités à un prix de 150 dinars).
Pour répondre à la question, on va donner un modèle mathématique à ce problème.
Modélisation :
Un modèle mathématique est une traduction des données du problème dans le but de lui
appliquer les outils, les techniques et les théories mathématiques.

Dans la modélisation mathématique de problème d’optimisation, on distingue trois étapes :

52
 • Identification des variables de décisions ; ce sont les paramètres sur lesquels l’utilisateur peut
agir pour faire évoluer le système considéré.

• Définition d’une fonction coût ou fonction permettant d’évaluer l’état du système (ex :
rendement, performance,. . .).

• Description des contraintes imposées aux variables de décision.

Le problème d’optimisation consiste alors à déterminer les variables de décision conduisant aux
meilleures conditions de fonctionnement du système (ce qui revient à minimiser ou maximiser la
fonction coût), tout en respectant les contraintes d’utilisation définies à l’étape 3
Donc ; pour donner le modèle mathématique du problème précédent il faut passer par les trois
étapes suivantes :
-Les variables
- La fonction économique (objective)
-Les contraintes

1. Les variables : Notons par :

x : la quantité de la viande
y : la quantité de fruit
z : la quantité du riz

2. La fonction objective :

Le prix total est : c)Les contraintes :

f (x, y, z ) (500x 200 y 150z )

800x 200 y 100z 2000

10x 6 y 5z 30

2x 4 y 4z 20, ,

x 0,

53
y 0,

z 0

Donc, notre problème est modélisé en un problème mathématique de la façon suivante :

(P )

min

(500x 200 y 150z ); x, y, z S

tel que S x, y, z R 3 / 800x 200 y 100z 2000, 10x 6 y 5z 30, 2x 4 y 4z 20

II .2.b. Exemple 2 : Un problème classique du sac à dos

Soit n objets de poids respectifs p,...,pn ∈, et d’utilités respectives u,...,un ∈, et P∈ un poids maximal
que l’on est disposé à porter. On pose xi =1 si on met le i-ème objet dans le sac-à-dos, et xi =0
sinon. On veut maximiser l’utilité du sac-à-dos sous contrainte de poids. Donc, notre problème est
modélisé en un problème mathématique de la façon suivante :

max x iui

sous les contraintes

xi pi P

I .2.c. Exemple 3 :

x i 0,11in

1in

On a besoin d’au moins 60 litres de peinture pour peindre les corridors d’un édifice. Pour effectuer
ce travail, on utilise de la peinture blanche et de la peinture bleue. Selon le contremaître, on doit
utiliser au plus 2 fois plus de peinture bleue que de peinture blanche. On évalue la surface à peindre
à au plus 240 m2 . Selon le fournisseur de peinture, un litre de peinture blanche couvre 2 m2 et
coûte 10 d, tandis qu’un litre de peinture bleue couvre 3 m2 et coûte 12 d.
Combien de litres de chaque couleur le contremaître doit-il utiliser pour minimiser ses dépenses ?

54
II. 3. Solution Optimale

Soit
f : Rn R, On appelle problème d’optimisation sans contraintes, le problème (P) suivant :

(P ) : min

f (x ),

x Rn

C’est un problème d’optimisation sans conditions sur les variables. Les minima locaux et globaux
de f
sur R sont définis de la manière suivante :

Définition :

• On dit que la fonction f du problème (P ) possède un minimum global en x ^ R n

ssi :

x Rn , f (x ) f (x ^).

• On dit que le point x ^ R n

est un minimum locale du (P) ssi il existe un voisinage V (x ^)
de x ^ tel

que :

x V (x ^),

f (x ) f (x ^).

• On dit que x ^ R n
est un minimum local strict de (P) ssi : il existe un voisinage V (x ^)
de x ^ tel que :

x V (x ^),

x x ^,

f (x ) f (x ^).

• On dit que x ^ R n est un minimum local isolée de (P) s’ il existe un voisinage V (x ^) de

x ^ tel que x ^ est la seule solution optimal de (P).

55
Maximum global
Minimum global

Remarque :
• Un minimum global est clairement un minimum local
• Si on dit simplement minimum on comprend minimum global.
• Toute solution optimale isolée est une solution optimale locale stricte. La réciproque n’est
pas toujours vraie.

Exemples :
– Soit la fonction : f (x ) Cte,
x R . Tout point x de R est un minimum local et global

mais il n’existe aucune solution stricte ou isolée.

– Soit la fonction : f (x ) x ,
aussi isolée.
x R . Le point x=0 est un minimum locale, globale, stricte et

– Pour la fonction f (x ) cos(x ) , il existe une infinité de minima et maxima globaux.

56
 – Pour la fonction f (x ) x cos x , il existe une infinité de minima et maxima locaux
mais aucun minimum ou maximum global.

Remarque : Les questions qui nous intéressent dans les problèmes d’optimisation sont les
suivantes :

– Existence et unicité de la solution du problème (P).

– Caractérisation des solutions (les points réalisant le minimum)
– Calcul, expression explicite du minimum et algorithmes permettant de l’approcher.

On utilise la plupart du temps des outils de nature différente pour répondre a chacune de
ces questions, par exemple le problème de l’existence se résout en général en exploitant les propriétés
topologiques de l’ensemble S ( dans le cas sans contraintes S=Rn ) et de la fonction f.

(a) Résultats d’existence et d’unicité

Avant d’étudier les propriétés de la solution du problème (P), il faut assurer de leur existence.
Le théorème le bien connu sur l’existence des minima et des maxima est

Théorème d’existence 1 : (Théorème de Weierstrass)

Soient S un ensemble compact (fermé et borné) non vide de Rn et

f : S R une fonction continue sur

S, alors f admet au moins un min x ^ sur S. Autrement dit, il existe un point x ^ de S minimum
global de
f sur S i.e. :

x S, f (x ) f (x ^).

Preuve : Soit (x n ) une suite minimisante de f sur S c’est-à-dire d’éléments de S telle que

xn S,

n N et

lim

57
f (x ) inf

xS

f (x )

Comme S est borné, la suite minimisante soit bornée, donc on peut extraite une sous-suite notée
(x n )
qui converge vers un élément x ^ de S car S est un ensemble fermé. Cette suite extraite vérifie

car f est continue,

lim

f (xn ) f (x ^)

d’où par unicité de la limite

Donc f réalise son minimum dans S.

f (x ^) inf

xS

f (x )

Remarque :
i. De la même façon, il existe un point de maximum global de f sur S.
ii. Si la fonction f n’est pas continue alors elle n’admet pas un minimum.
iii. Une fonction continue sur un fermé borné n’atteint pas toujours son minimum dans
un espace de dimension infinie.
iv. L’existence d’une suite minimisante provient de la définition de l’inf.
v. Rappelons qu’un compact S de Rn est caractérisé par la propriété que toute suite de
points de l’ensemble S admet une valeur d’adhérence dans l’ensemble.
Intuitivement, on comprend qu’un fermé borné vérifie une telle propriété : une suite de
points de l’ensemble S ne peut pas partir "à l’ infini" puisque l’ensemble est borné, elle
doit donc s’accumuler quelque part dans Rn et un point d’accumulation de la suite est
nécessairement dans l’ensemble puisque l’ensemble S est fermé.
Dans le cas des problèmes d’optimisation sans contraintes (S=Rn ), on va utiliser le
théorème suivant

58
Théorème d’existence 2 :

Soit
f : Rn R une fonction continue et coercive ( i.e. infini à l’infini : lim

f (x ) ) alors f admet

au moins un minimum sur Rn . Autrement dit, il existe un point x ^ de Rn minimum global de f

sur Rn

Preuve :

x Rn ,

f (x ) f (x ^).

Soit (x n ) une suite minimisante dans Rn c’est à dire

lim

f (x n ) inf

x Rn

f (x )

Comme f est coercive, la suite (x n ) ne peut pas partir a l’infini donc elle est bornée et il existe une

sous-suite extraite notée (xn ) de Rn qui converge vers un x ^ de Rn : Or f est continue, donc

x x^ R n
.

lim

f (x n ) f (x ^)

d’où par unicité de la limite

Donc ; f réalise son minimum dans Rn .

59
f (x ^) inf

x Rn

f (x ) .

Théorème d’unicité :

Si de plus f : Rn →R strictement convexe, alors il existe un unique minimum x ^ R n

de f tel que :

Preuve :

x Rn ,

f (x ) f (x ^).

Soit f strictement convexe, supposons qu’il existe x ^, x ∈ Rn deux min de la fonction f sur Rn
tels que

x x ^ et

f (x ^) f (x ) inf

x Rn

f (x ) .

Soit ∼x x (1 )x ^ Rn avec (0,1) et comme f est strictement convexe

f (∼x ) f (x ^) (1 ) f (x ) f (x ^) min

x Rn

Ceci fournit une contradiction, ce qui est impossible; donc x ^ x .

f (x ).

Nous pouvons maintenant énoncer un deuxième résultat d’existence et d’unicité

Théorème 2 :

Soit f une fonction C1 (Rn ,R), on suppose que f est elliptique

60
la constante d’ellipticité) tel que :
c’est dire qu’il existe 0 (appelée

(x, y) Rn Rn ,

(f (x ) f ( y), x y) x y 2 .

Alors, f est strictement convexe et coercive. En particulier le problème (P) admet une solution
unique.

Preuve : Exercice

Il faut maintenant donner des conditions d’optimalités pour pouvoir calculer la ( ou les) solutions,
mais avant ça, on a besoin de quelques définitions.

1. 5.Direction de descente
Une direction de descente est une direction le long de laquelle la fonction à minimiser a une
dérivée directionnelle strictement négative. Ces directions sont utilisées par les méthodes à
directions de descente.

Définitions3 :

Soit f : Rn →R,
x ^ R n et « d » un vecteur de Rn /{0}. Le vecteur « d » est dit de descente au point

x^ R n
si et seulement si

Théorème :

0,

0, ,

f (x ^ d ) f (x ^).

61
Soit f : Rn → une fonction différentiable au point x ^ R n et d R n
tel que

f ’ (x ^, d ) (f (x ^), d ) 0

Alors, ‘d’ est une direction de descente de f en x ^ R n

.

Preuve : Soit f une fonction différentiable au point x ^ R n

, donc

f (x ^ d ) f (x ^) .f (x ^)t .d . d .(x ^, d ),

x S,

où (x ^, d ) 0

quand 0.

Donc et

f (x ^ d ) f (x ^) = f (x ^)t .d d .(x ^, d )

et comme

lim

f (x ^ d ) f (x ^) f (x ^)t .d f ’ (x ^, d ) (f (x ^), d )

(f (x ^), d ) 0 f ’ (x ^, d ) 0,

donc :

0, tq

f (x ^ d ) f (x ^) 0, 0,

0,

0, ,

f (x ^ d ) f (x ^).

62
Donc le vecteur « d » est une direction de descente.

Remarques :

(a) Par définition du gradient, il revient au même de dire que ‘d’ fait avec l’oppose du
gradient (−f(x)) un angle θ, appelé angle de descente, qui est strictement plus petit
que 90◦ :

arccos (f (x ), d ) 0,

La notion d’angle définie ci-dessus dépend du produit scalaire et n’est pas invariante par rotation
des
vecteurs. L’ensemble des directions de descente de f en x,

d Rn , f (x ), d 0

forme un demi-espace ouvert de Rn .

(a) Par définition de la dérivée, on voit que si d est une direction de descente

f (x ^ d ) f (x ^) pour tout > 0 suffisamment petit.

et donc que f décroit strictement dans la direction « d ». De telles directions sont intéressantes
en optimisation car, pour faire décroitre f, il suffit de faire un déplacement le long de « d ».
Les méthodes a directions de descente utilisent cette idée pour minimiser la fonction f.

(a) Conditions d’optimalité :CO

Dans cette section, nous allons chercher à obtenir des conditions nécessaires et parfois suff-
isantes de minimalité. L’objectif est d’une certaine manière beaucoup plus pratique puisque
ces conditions d’optimalité seront le plus souvent utilisées pour tenter de calculer un mini-
mum ou le maximum. Ces conditions vont donc s’exprimer à l’aide de la dérivée première ou
seconde.

63
 i. Condition d’optimalité nécessaires du premier ordre :CON1
Les conditions que nous allons donné sont des conditions différentiables qui portent
sur la dérivée de la fonction à minimiser.
Théorème :
Soit f :→ une fonction différentiel au point x ^ de Rn . Si x ^ est un optimum local du
problème (P),

alors

Preuve :

f (x ^) 0

Supposons le contraire c’est-à-dire f (x ^) 0 donc on un vecteur d f (x ^) qui est une direction de

descente i.e

0,

0, ,

f (x ^ d ) f (x ^).

et x ^ R n
est un optimum local du f donc :

V (x ^) , x V (x ^),

f (x ) f (x ^).

Soit V (x ^)

un voisinage quelconque de x ^ :

V (x ^) x ^, x ^ f (x ^) ,

0,

x x ^ d V (x ^),

f (x ) f (x ^).

Contradiction avec le fait que x ^ R n

est une solution optimale locale du (P).

64
On conclut que f (x ^) 0

Remarque :

A. La réciproque du théorème précédent n’est pas vraie.

B. Tout point x ^ R n vérifiant f (x ^) 0 est appelé « point critique » ou « point
stationnaire ». 3- La relation f (x ^) 0 est aussi appelée « équation d’Euler ».
• Ce théorème n’a pas de sens si la fonction f n’est pas différentiable.
• Il faut bien noter que la condition du premier ordre ne fournit qu’une condition
nécessaire d’optimalité. Autrement dit, l’application de ce critère fournira en
général trop de points parmi lesquels il faudra déterminer la ou les solutions du
problème (P) usuellement en comparant les valeurs de la fonction objective f
en ces points.
• Si f est convexe, la condition nécessaire du premier ordre est également
suffisante pour que
x ^ R n soit un minimum de f .
Théorème :
Soit f : R→R une fonction convexe et différentiel au point x ^ de Rn . Un point x ^
réalise un optimum de
f sur Rn si et seulement si
f (x ^) 0
Preuve : On a vu que la condition est toujours nécessaire, montrons qu’elle est
suffisante.

Soit

x ^ Rn

tel que f (x ^) 0 et comme f est convexe donc

x Rn , f (x ) f (x ^) (f (x ^))t (x x ^) f (x ) f (x ^),

On a donc immédiatement le fait que x ^ réalise un minimum de f sur Rn :

Nous donnons maintenant une condition nécessaire permettant de préciser encore les éventuels
minima. Cette condition va faire intervenir la dérivée seconde de f.

65
 i. Condition d’optimalité nécessaires du deuxième ordre CON2
Dans le cas où f est deux fois différentiable, une autre condition nécessaire est donnée
par le théorème suivant :
Théorème :
Soit f : R→R une fonction deux fois différentiable au point x ^ R n
. Si f possède
un minimum local en
x ^ alors :
1- f (x ^) 0 et
2- La matrice Hessienne H (x ^) soit semi définie positive

Preuve :

Soit f une fonction deux fois différentiable au point x ^ R n

petit, on a
et d un vecteur de Rn , donc pour assez

f (x ^ d ) f (x ^) f (x ^), d 1 2 .d t H (x ^).d 2 . d .2 (x ^, d ), 2

le point x ^ R n
est le minimum de f c’est-à-dire f (x ^) 0

x S,

où (x ^, d ) 0

quand 0.

donc

f (x ^ d ) f (x ^) 0, 0,

1d t H (x ^).d d .2 (x ^, d ) 0 , 0,

66
2

Par passage à la limite lorsque

1d t H (x ^).d 0, 2

d R n

Donc, la matrice hessienne H (x ^) est semi définie positive.

Remarque :
La réciproque du théorème précédent n’est pas vraie (pour la fonction f(x)=x3 , les conditions
d’optimalité du premier et de deuxième ordre sont vérifiées pour x=0 mais « 0 » n’est pas un
minimum local.

i. Condition d’optimalité suffisante du deuxième ordre COS2

Les conditions données précédemment sont nécessaires, c’est-à-dire qu’elles doivent être satisfaites
pour tout minimum local, cependant, tout vecteur vérifiant ces conditions n’est pas nécessairement
un minimum local. Le théorème suivant établit une condition suffisante pour qu’un vecteur soit un
minimum local, si f est deux fois continuellement différentiable.

Théorème :

Soit f : R→R une fonction deux fois différentiable au point x ^ R n

. Si

f (x ^) 0 et la matrice

hessienne H (x ^) est définie positive, alors f possède un minimum local en x ^ R n

.

Preuve :

Soit f une fonction deux fois différentiable au point x ^ R n

, donc f s’écrit sous la forme

f (x ) f (x ^) (f (x ^))t (x x ^) 1 (x x ^)t H (x ^)(x x ^)

2
2
x x^ (x ^, x x ^),
n
x R ,

67
où (x ^, x x ^) 0

quand

x x ^.

Supposons que x ^ R n
n’est pas un min local stricte c’est-à-dire

(x ^) , xk

(x ^),

f (x k

) f (x ^).

Notons

d xk x^

, donc : d

1,

k 2
x x^ k

d’après le théorème de Bolzano Weierstrass

N 1 N, d k

∼, k

N1

donc

68
k

f (x k

) f (x ^) 1 (x

2 k

x ^)t H (x ^)(x

x ^)
2
x x^ (x ^, x

x ^), ,

f (x k ) f (x ^) 1 d

t
H (x ^).d

(x ^, d )

2
x x^ 2 k k

Or f (x k ) f (x ^) f (x k ) f (x ^) 0 ,

donc

k,

2d k

t
H (x ^).d

(x ^, x k

x ^) 0,

passant à la limite

k ∼t ^ ∼

∼ 0 car d d ^ et d 1

69
 d H (x ).d
0, d k k

Donc, la matrice hessienne H (x ^) n’est pas définie positive.

Exemple :

Considérons la fonction f : R2 →R

f(x)=f(x1,x2)=6x²+x³+6xx+3x²
Nous allons identifier tous les points critique de cette fonction, et allons utiliser la première condition
d’optimalité afin de déterminer leur nature (min, max, ou ni min ni max). La fonction f est
différentiable, alors

Etape 1 : Identification des points critiques :

La fonction f est différentiable et son gradient est: f(x)=( 12x +6x ,3x ²+6x +6x )

La condition nécessaire de premier ordre : f(x ,x )=(0,0) nous permet d’identifier deux points
critique : x=(0,0)t et x=(1/2,-1)t

Etape 2 : Nature des points critiques

La matrice hessienne de cette fonction est

12 6

H (x, y)
6

6x 2
6

Les conditions de deuxième ordre nous permettent de classer ces points critiques

- Pour x=(0,0)t on a det H(0,0)=36>0 et ses valeurs propres sont positives.

La matrice hesienne est alors définie positive, et donc x=(0,0)t est un minimum local.

- pour x=((1/2),-1)t don det H((1/2),-1)=-36<0.

La matrice hesienne n’est pas semi-définie positive, et donc x=((1/2),-1)t n’est pas un minimum
local.

Remarques :

70
Si f (x) = 0 et la matrice hessienne H (x) est indéfinie (n’est ni semi-définie positive, ni définie
positive, ni semi-définie négative, ni définie négative). Alors, le point x est appelé point selle.

Optimisation classique sans contrainte

On considère ici des fonctions f définies dans (une fonction d’une variable réelle). Si la fonction
f et sa dérivée f sont continues en un point x ou la croissante de la fonction devient décroissante,
alors elle possède un maximum. Le raisonnement contraire est valable pour un minimum.
Il existe deux critère pour déterminer si un point candidat (le point qui annuler la première dérivée
de f ) est un point extrémum (minimum ou maximum).

• Premier critère est:

-Si le signe de la dérivée est positif puis devient négatif quand x croit, alors le point candidat
est un maximum de la fonction.
-Si le signe de la dérivée est négatif puis devient positive quand x croit, alors le point candidat
est un minimum de la fonction.

• Deuxième critère :

fait appel à la dérivée seconde de la fonction f(x). Soit P(x ;f(x )) le point en lequel f(x )=0. Alors
si en ce point:

1- f(x )<0, il s’agit d’un maximum. 2- f(x )>0, il s’agit d’un minimum.

Exemple : Soit la fonction y=f(x)=x³-3x²+5

f est dérivable sur R, Calculons sa première et sa deuxième dérivée

f(x)=3x²-6x=3x(x-2), f(x)==6x-6=6(x-1).

On obtient les points candidats de la fonction f en résolvant l’équation

f(x)=0 donc 3x(x-2)=0 ⇒x =0 et x =2,

et les valeurs correspondantes de y sont y=5 et y=1.

Déterminons la nature des points candidats en utilisant le résultat précédent

f(0)=-6<0 et f"(2)=6>0.

La fonction a donc un maximum en x =0 et un minimum en x =2. Les coordonnées du maximum

sont (0;5) et celles du minimum (2;1).
Par conséquent, dans un voisinage convenablement choisi du point x =0, la valeur de la fonction est
plus petite que f(x). On dit que la fonction possède un maximum local ou relatif au point x =0. Au
point x =2, on dit que la fonction possède un minimum local ou relatif. Ces deux valeurs, maximum
et minimum, sont appelées des extremums locaux ou relatifs.

Exercices du chapitre 2

71
Exercice 1 :
–——————————————————————————————————

Déterminer les minima et les maxima, s’ils existent, de la fonction f définie sur IR 2 par

1- f (x , x ) ax 2
bx 2
, (a, b R) , 2-
2
f (x , x ) x 3x x

•
x2

1 2 1 2

1 2 1

1 2 1

3- f (x, y) x /(1 x 2 y 2 ) , 4-

f (x, y x (ln x 2 y 2 )

Exercice 2
:———————————————————————————————————-

Dans le théorème d’existence du minimum (sans contraintes) d’une fonction f, montrer que l’on
peut remplacer la propriété « infinie à l’infini » par la condition plus faible

inf

f (x ) lim (inf

f (x )),

r 0

x Rn

r x r

72
Exercice 3
:———————————————————————————————————-

Soit f une fonction C 1 de Rn dans R, et (P ) est le problème { min

f (x ), x Rn }, on suppose qu’il

existe 0 tel que : (x, y) Rn Rn , (f (x ) f ( y), x y) x y 2 (on dit que f est -elliptique)

• Montrer que :

f ( y) f (x ) (f (x ), y x )

x y 2 , (x, y) Rn RN

• Montrer que f est strictement convexe et coercive.

• Déduire que le problème (P) admet une solution unique.

• On suppose que f est deux fois différentiable en tous points de Rn , montrer que f est

-elliptique ssi :

(x, y) Rn Rn ,

(D 2 f (x ).y, y) y 2

Exercice 4 :

Soient u et v deux vecteurs non de R2 . On considère la fonction g de R dans R, telle que

(x, y) R 2 , g(x, y) xu yv

Montrer que g est minorée par un réel strictement positif m sur l’ensemble

C (x, y) R 2 ,

73
x2 y 2
1

En déduire que

(x, y) R 2 ,

g(x, y) m

• Soit (p1„ „ pk) une suite de k points de R2 avec k > 2. On pose

p i (i , j ) et on suppose que la suite

( ) est strictement croissante. On considère alors la fonction f de R2 telle que

(x, y) R 2 ,

f (x, y) ( x y)2

i i

i 1

-Montrer que f est coercive. En déduire qu’il existe (x0; y0) dans R2 tel que :

f (x , y ) min

f (x, y)

0 0 ( x, y)R2

• Calculer un tel (x0; y0) et montrer qu’il est unique.

74
Exercice 5 :

– Soient
p 1 52,

p 44 les prix respectifs de deux produits. Soient q 1 , q 2 les quantités

respectives de ces produits. La fonction coût est C q 2

qq

q 2
.

Trouver les quantités q 1 , q 2 maximisant le bénéfice.

1 2 2

– Un fabricant de postes de télévision produit q postes par semaine à un coût total :

C=6q2 +80q+5000. C’est un monopoleur et son prix s’exprime par la relation
P=1080-4q Montrons que le bénéfice net maximum est atteint lorsque la production est
de 50 postes par semaine.

Exercice 6 :

On considère la fonction f définie sur R3 par : f (x, y, z ) 3x 2 3y 2 3z 2 2xy 2x 10y

• Montrer que f est coercive sur R3 . Que peut-on en déduire ?

• Calculer les points où f est minimale sur R3 .

Exercice 7:

On considère le problème suivant : Trouver u ∈ Rn tel que

Bu C

inf

v Rn

75
Bv C

(1)

où B est une matrice réelle de taille m ∗ n, c ∈ Rn et désigne la norme euclidienne sur Rn .

Dans la suite on note aussi par (., .) le produit scalaire sur Rn .

• Montrer que (1) admet toujours au moins une solution.

• Montrer que cette solution est unique si et seulement si B est injective. Quelle est la
Condition nécessaire sur m et n pour que B soit injective ?

• Montrer que le problème (1) est équivalent au problème (2) ci-dessous :

Trouver u ∈ Rn tel que

f (u) inf

vR n

f (v )

(2)

où on a posé f(v) =1/2 (Bt Bv, v) − (Bt c, v).

– La fonction f est-elle différentiable ?

– Si cela est possible, calculer le gradient et la hessienne de f.
– Donner la condition d’optimalité au premier ordre pour le problème (2).
Cette condition est-elle suffisante ici pour obtenir un minimum?
– Dans le cas où B est de rang n, montrer que f est strictement convexe. Que peut-on
alors conclure ?

Exercice 8:

On considère la fonction f de Rn dans R définie par la relation :

x Rn ,

f (x ) sin( x 2 ) sin n

i 1

76
 ∗ Montrer que la fonction f est différentiable sur Rn et calculer son gradient.
∗ Montrer que la fonction f est C2 et calculer sa matrice Hessienne.
∗ Déterminer tous les extrema (minima et maxima) de f sur Rn . Représenter
graphiquement ces extrema dans le cas où n = 2.

Exercice 09 :———————————————————————————
————————–

Soit

f : R 3 R, f (x, y, z ) x 2 y 2 z 2 xy yz xz 3x 4y z 4

• Mettre f sous la forme d’une fonction quadratique

f (x ) 1 ( Ax, x ) (b, x ) c

avec A est une matrice symétrique, b R 3, c R.

• Soient min et max la plus petite et la plus grande valeur propre de A. Montrer que

3
x R ,

min

2
x ( Ax, x )

max

2
x ,

• Montrer que si A est définie positive alors f « infinie à l’infini » et admet un minimum
unique sur R3

• En déduire que si A est non positive alors f n’admet pas de minimum sur R3

Exercice 10:

On 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 ou (a,b,c) sont trois réels à déterminer.
1- Exprimer le problème ci-dessus sous forme de problème de minimisation. 2- Ce problème de
minimisation a-t-il une solution ? est-elle unique ?

77
 • Ecrire la condition d’optimalité permettant de trouver le minimum

Exercice 11:

A- On considère la fonction g de R2 dans R définie par la relation :

(x, y) R 2 ; g(x; y) = x2 + y2 + xy

• Montrer que la fonction g est coercive et strictement convexe sur R2 .

• En déduire que g possède un unique minimum sur R2 .
• Donner la condition d’optimalité.

Exercice 12:

1. Soit f la fonction numérique à variable réelle définie par :

f (x ) x 3

1. Montrer que f admet un minimum sur R et Déterminer les points critiques de f.

3. Parmi les points critiques, lesquels correspondent à des minima ?

1. Soient p et q deux réels strictement positifs tels que : 1 1 1. En utilisant la concavité de

pq

la fonction logarithme, montrer que:

∗ x p x q

x, y R ,
xy .
p q

78
Chapitre III

METHODES ITERATIVES d’OPTIMISATION SANS

CONTRAINTES

Ce chapitre introduit une classe importante d’algorithmes de résolution des problèmes d’optimisation
sans contrainte. Le concept central est celui de la direction de descente.
Après avoir décrit le fonctionnement d’un algorithme a directions de descente, nous donnons quelques
exemples d’algorithmes de ce type, nous énonçons des critères qui permettent d’estimer la qualité
de la direction de descente proche d’une solution : celui de l’admissibilité, du pas unité et celui de
la convergence super-linéaire.

(a) Notion d’algorithme

Considérons le problème consistant à minimiser une fonction f(x) où x de Rn , un algo-
rithme itératif permettant de résoudre ce problème est un processus itératif générant une
suite de vecteur (x0,x1,. . .,xn) de Rn en fonction d’une séquence d’instructions et d’une
condition d’arrêt, c à d qu’a partir d’un point
initial x0, on engendre ( construit) une suite (xn) qui converge vers la solution du problème

(P ) : min

f (x ),

x Rn

Un algorithme est définie par l’application h de Rn dans Rn , qui à chaque point xk fait correspondant
à
x k 1 h(x k ) . L’étude de la convergence revient à l’étude des propriétés de l’application h.

(a) Modes de Convergence

Nous dirons qu’un algorithme décrit par une application h est globalement convergeant
si : quelque

soit le point x0 choisi, la suite (xk) engendrée par :

xk 1 h(xk ) converge vers un point x ^ satisfaisant

les conditions d’optimalité (f (x ^) 0

et H (x ^)

est

79
s.d.p) . On a plusieurs modes de convergence :

1. La suite (x k

) converge vers x ^ linéairement avec un taux 1 si : lim

sup

1. La convergence est dite asymptotique si

1. La convergence est dite super-linéaire si :

xK 1 x^

lim

xk x^

0.

1. La convergence est dite super-linéaire d’ordre 1 si : lim

xk 1 x^

Si 2 la convergence de l’algorithme est dite quadratique

x x^

80
 (a) Schémas général des algorithmes d’optimalité

Il convient de souligne que la plupart des algorithmes d’optimisation, avec contrainte ou

non, fonctionnent selon un schéma général consistant, à chaque itération, à se rapprocher du
minimum par la résolution d’un sous problème de minimisation.
Les méthodes ( ou les algorithmes) itératives d’optimalité fait partie d’une classe plus grande
de méthodes numériques appelées méthodes de descente.
Un algorithme à directions de descente est un algorithme d’optimisation différentiable, destiné
à minimiser une fonction réelle différentiable définie sur un espace euclidien (par exemple Rn ,
muni d’un produit scalaire) ou, plus généralement, sur un espace hilbertien. L’algorithme est
itératif et procède donc par améliorations successives. Au point courant, un déplacement est
effectué le long d’une direction de descente, de manière à faire décroître la fonction.

Principe de cette méthode : On veut minimiser une fonction f. Pour cela on se donne un point
de

départ arbitraire x 0 , pour construire l’itéré suivant x 1 il faut penser qu’on veut se rapprocher du

min de f, on veut donc que

f (x 1 ) f (x 0 ) . On cherche alors

x 1 sous la forme :

x1 x0 0 d 0 où

d 0 est un vecteur non nul de Rn et 0

un réel strictement positif, donc on cherche

0 et d 0 pour

que f (x 0 0 d 0 ) f (x 0 ). On ne peut pas toujours trouver d 0 . Quand d 0

existe on dit que c’est une

direction de descente et 0
est le pas de descente, cette opération de détermination du pas

s’appelle la recherche linéaire. La direction 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

81
R n donné

n ∗

xk 1 xk k d k,

d k R

/0,

k R

où k

et dk sont choisis de telle sorte que :

f (xk k dk ) f (xk ) .

Une idée pour trouver une direction descente est de faire un développement de Taylor à l’ordre 2
de la

fonction f entre deux itérés x k et

xk 1 xk k dk

f (xk k dk ) f (xk ) k (f (xk ), dk ) O(k dk )

Comme on veut f (xk k dk ) f (xk ) , on peut choisir, par exemple :

i. d k f (x k ) : la méthode obtenue s’appelle L’algorithme du Gradient.

ii. d [H (x )]1 f (x ) : la méthode obtenue s’appelle L’algorithme de Newton

1. 4. Méthode de Gradient

82
L’algorithme du gradient désigne un algorithme d’optimisation différentiable. L’algorithme est
itératif et procède donc par améliorations successives. Au point courant, un déplacement est effectué
dans la direction opposée au gradient, de manière à faire décroître la fonction. Cette description
montre que l’algorithme fait partie de la famille des algorithmes à directions de descente.
L’algorithme du gradient est également connu sous le nom d’algorithme de la plus forte pente ou
de la plus profonde descente (steepest descent, en anglais) parce que le gradient est la pente de
la fonction linéarisée au point courant et est donc, localement, sa plus forte pente (une notion qui
dépend du produit scalaire).
La direction de descente choisis sera à chaque itération

d k f (x k ) ,

les points sont ainsi successivement générés par cette méthode de la manière suivante :

R n donné

xk 1 xk k f (xk ),

k 0

L’algorithme de Gradient est donné pas :

• Initialisation K=0

choix de x0 , 0 0

• Itération k

xk 1 xk k f (xk )

• Critère d’arrêt

et

si xk 1 xk

ou si

f (xk )

83
stop

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

avec est un réel positif (petit) donné qui représente la précision désirée (la valeur que nous devons
fixer pour dépend du problème considéré).

i. Méthode de Gradient à pas optimal

Cette méthode consiste à faire les itérations suivantes :
d k f (xk )
xk 1 xk k d k, k 0

où k est choisi par le règle de minimisation, il consiste à choisir, à chaque itération k comme étant
la solution optimal du problème de minimisation monodimensionnelle de f le long de la demi-droite

définie par le point x k et la direction d k . Donc, k

est choisi de manière à ce que :

f (x k k d k ) f (x k d k ),

0,

dans ce cas les directions de descente d générées vérifient : d t .d 0 car si on introduit la fonction

on a

g() f (xk dk ),

k 1 k

g’ () f (x d )t .d ,

et puisque g est dérivable on a nécessairement g’ (k ) 0 donc :

84
 f (x d )t .d f (x )t .d d .d 0 .

Cette opération de détermination du pas s’appelle la recherche linéaire.

Remarque :

A. La méthode de gradient à pas optimal propose un choix du pas qui rend la

fonction de coût minimale le long de la direction de descente choisie, Plus
précisément le calcul de
x k 1 x k k f (x k ).
B. Deux directions de descente successives calculées par l’algorithme de plus
profonde descente (gradient) sont orthogonales ce qui traduisant les zig-zags
des itérés.

Exemple :

Soit la fonction quadratique suivante:

f (x ) 1 xt Ax bt x avec A>0 ( c’est-à-dire A est une matrice

définie positive), on note g() f (xk dk ), où le optimal k est caractérisé par g’ (k ) 0 , on a donc

f (x d )t .d ( A(x d ) b) t
.d 0

(f (x ))t .d

Soit

f (xk k Adk ) .d 0

k 0

d t .Ad

car d k

est une direction de descente et d t .Ad

85
k k

• 0.

d k b Axk

La méthode du gradient à pas optimal peut s’écrire :

xk 1 xk k dk

avec

k k

d .A

Théorème de Convergence :

Soit f une fonction C1 (Rn ,R), coercive et strictement convexe. On suppose qu’il existe une constante
M>0 tel que

(x, y) Rn Rn , f (x ) f (y) M x y

Alors, si on choisit le pas k dans un intervalle ,

tel que 0

86
2 , la méthode du gradient

converge vers le minimum de f.

Preuve :

La fonction f admet un minimum x ^ unique sur Rn caractérisé par f (x ^) 0 puisque f est stricte-
ment convexe. Montrons que la suite ( xk ) engendrée par l’algorithme converge vers x ^ ,
on a :

f ( y) f (x ) (f (x ), y x ) (f (x t( y x ) f (x ), y x )dt

On applique cette relation à

y x k 1,

x xk

f (x k 1) f (x k ) (f (x k ), x k 1 x k ) (f (x k t(x k 1 x k ) f (x k ), x k 1 x k )dt

Comme x k 1 xk k f (x k ), on obtient

f (x ) f (x ) 1

xk 1 xk

f (x k t(x k 1 x k ) f (x k ) . x k 1 x k dt

87
1 2 2 M 1 2 .

xk 1 xk

xk 1 xk

. xk 1 xk

Si on choisit k
dans un intervalle [ 1 , 2

] tq 0 1

2 , nous obtenons alors

M 1 2

f (xk 1 ) f (xk )

. xk 1 xk

La suite
f (x k ) est alors strictement décroissante, comme elle est minorée car

f (xk ) f (x ^), k

88
elle est converge. Cela entraîne d’une part que f (x k 1 ) f (x k ) tends vers « 0 » et d’autre part,
la suite (x k ) est bornée (car f est coercive). On peut donc extraire une sous suite converge vers x
. De plus, comme

xk 1 xk

2 1

. f (xk 1 ) f (xk )

La suite x k 1 x k tend également vers 0. Par conséquent

f (x k

) xk 1 xk 0

Par continuité de f (x ) 0 , donc x est l’unique minimum x ^ de f. Ceci étant vrai pour toute valeur
d’adhérence de la suite xk cela prouve que toute la suite xk converge vers x ^ .

i. Méthode de Gradient à pas fixe

On peut utiliser un pas fixé a priori 0, k on obtient alors la méthode de gradient simple :

dk f (x k )

k 1

89
xk
• dk

Pour
f C 1 , cette méthode converge si est choisi assez petit.

Le choix de pas :

• Un pas « bien choisi » donne des résultats à ceux obtenus par la plus profonde descente.

• Un pas plus petit atténue les zigzags des itérés mais augmente significativement le nombre
d’itérations.

• Un pas trop grand fait diverger la méthode.

Inconvénient de la méthode de Gradient :

L’algorithme du gradient peut rencontrer un certain nombre de problèmes, en particulier celui

de la convergence lorsque le minimum de la fonction se trouve au fond d’une vallée étroite (plus
précisément lorsque le conditionnement de la matrice hessienne est élevée). Dans un tel cas, la suite

des {xk } oscille de part et d’autre de la vallée et progresse laborieusement, même lorsque les k

choisis de sorte à minimiser f (x ).

La figure ci-dessous illustre ce type de comportement pour une fonction à 2 dimensions.

sont

90
Les points faibles de l’algorithme du gradient sont :

– L’algorithme peut nécessiter de nombreuses itérations pour converger vers un minimum

local, notamment si la courbure est très différente dans des directions différentes.

– La recherche du pas optimal, généralement effectuée par une recherche linéaire, peut
se révéler très longue. Inversement, utiliser un pas fixe peut conduire à de mauvais
résultats.
– L’inconvénient majeur de cette méthode survient lorsque la direction du gradient y est
presque orthogonale à la direction menant au minimum. Celle-ci adopter alors le com-
portement bien connu du « zig-zag » et progresse extrêmement lentement.
– Cette méthode a pour avantage d’être très facile à mettre en œuvre. Malheureusement 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.
– Pour construire les méthodes de gradient, nous avons remplacé f par son approximation
linéaire au voisinage de l’itéré courant. Nous avons vu que ces méthodes ne sont pas très
performantes, en partie parce qu’elles ne tiennent pas compte de la courbure (ou de la
Hessienne) qui est une information de second ordre.

Exemple :

Comparaison de la vitesse de l’algorithme de gradient à pas fixe et à pas optimal pour la résolution
du Problème :

min f (x ) min 1 ( Ax, x ) (b, x )

xR n

xR n 2

avec A est une matrice symétrique carré (n.n) et b est un vecteur de Rn . Ce problème équivaut a
la résolution du système Ax=b
On a choisi A = diag([1 : 1 : 100]), xsol = ones(N, 1) et x0 = rand(N, 1).

//Gradient a pas optimal pour problème quadratique

clear clf N=100;

//A=2∗diag(ones(N,1),0)-diag(ones(N-1,1),-1)-diag(ones(N-1,1),1); A=diag([1:1:N]);
xsol=ones(N,1); b=A∗xsol; x0=rand(N,1); itermax=100;

91
//1.Gradient pas fixe

x=x0;
Tfixe=[norm(x-xsol,’inf’)]; mu=0.01;
for k=1:itermax d=A∗x-b;
x=x-mu∗d; err=norm(x-xsol,’inf’); Tfixe=[Tfixe err];
end

//2.Gradient pas optimal

x=x0;
Topt=[norm(x-xsol,’inf’)]; for k=1:itermax
d=A∗x-b;
mu=d’∗d/(d’∗A∗d); x=x-mu∗d; err=norm(x-xsol,’inf’); Topt=[Topt err];
end

plot2d([0:1:itermax]’,[Tfixe’ Topt’],logflag=’nl’,style=[1 2]); xtitle(”,’k’,’||xk-x||’)

legends([’pas fixe’;’pas optimal’],[1 2],opt=’ll’)

1. 5. Méthode des gradients conjuguées

La méthode du gradient conjugué est un algorithme pour résoudre des systèmes d’équations linéaires
dont la matrice est symétrique définie positive. Cette méthode, imaginée en 1950 simultanément
par Cornelius Lanczos et Magnus Hestenes, est une méthode itérative qui converge en un nombre
fini d’itérations (au plus égal à la dimension du système linéaire).

Principe de la méthode

On considère f une fonction quadratique de Rn dans R : symétrique définie positive (n.n), b est un
vecteur de Rn

92
f (x ) 1 xt Ax bt x où A est une matrice

L’idée est de reprendre la méthode de plus forte pente ( i.e. la méthode de Gradient) mais d’éviter
les “mauvaises" directions de descente trouvées précédemment qui faisaient “rebondir" le chemin
de descente sur les parois de f. Pour éviter les zigzags et accélérer la convergence, on cherche des
directions de descente « di » mutuellement conjuguées par rapport « A » pour prendre en compte
la géométrie de la fonction f.

Directions conjuguées Définition :

(a) On dit que deux directions x et y de Rn sont conjuguées par rapport à la matrice « A »
si

xt .Ay 0 .
(b) Si la matrice « A » est symétrique et définie positive, on déduit un produit scalaire :

(x, y) (Ax, y) (x, Ay) xt Ay.

(c) Des vecteurs d1 ,d2. . .,dk de Rn sont dits A-conjugués si pour tous i j , on a :

d ;d 0

Remarque :

• Les vecteurs x et y sont conjugués par r apport A s’ils sont orthogonaux pour ce produit
scalaire de A, donc la notion de conjugaison équivaut à la notion d’orthogonalité pour le
produit scalaire associé à la matrice A

• La conjugaison est une relation symétrique.

• (dk) est une suite de « n » directions conjuguée deux à deux, forment une base orthonormée
de Rn , donc

93
d t Ax ^ d t b d t Ad

d t Ad

d t b

dk

,b

dk

,b

k k i k i

i 1

k k d

k d t Ad

dk , dk A d

n
x^ R ,

x^ i d i i1

Ax ^ b i Ad i

i1

Donc l’idée de la méthode de gradient conjuguée est de

94
 1. Trouver une suite de n-directions conjuguée et

2. Calculer le coefficient i .

Théorème :

Soient d1,d2,. . .. ,dk un ensemble de vecteurs non nuls de Rn , A-conjugués. Alors les vecteurs

d1 ,d2. . .,dk sont linéairement indépendants.

Preuve :

C’est une conséquence immédiate du résultat bien connu : si des vecteurs non nuls sont orthogonaux
par rapport à un produit scalaire, alors ils sont indépendants

Méthode des directions conjuguées

L’idée est que si on arrive à définir un algorithme itératif utilisant n-directions conjuguées,
alors on aura parcouru tout l’espace Rn dans toutes les directions possibles (ce qui n’était pas le
cas pour l’algorithme de plus profonde descente).

Étant donnés un point initial x0 de Rn et n-directions A-conjuguées d1 ,d2. . .,dk on définit le

-schéma

suivant :

xk 1 xk k dk

où k est le scalaire minimisant f(x) selon la direction x k k dk

r t .d

et qui est défini par

k k
k d t .Ad

k k

et rk f (xk ) b Axk

L’algorithme ci-dessous résout Ax = b, où A est une matrice réelle, symétrique, et définit positive.
Le vecteur d’entré x0 peut être une approximation de la solution initiale ou 0.

95
Algorithme de la méthode de Gradient Conjuguée

(a) Initialisation k=0,

Choix de x0 dans Rn ; r 0 b Ax 0 ;

(b) Itération k

r t .r

p0 r 0

k k

k pt Ap

k k

xk 1 xk k pk ,

(a) Critère d’arrêt

rk 1 rk k Apk

Si r k 1est suffisamment petit, alors on sort de la boucle

r t .r

k 1 k 1

k r t r

pk 1

rk 1
• k pk

k k

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

Propriétés :

96
1. i j ;

d t .Ad

0 : les directions de descentes sont toutes mutuellement conjuguées.

• L’algorithme des gradients conjuguées converge en au plus ‘n’ itérations.

• On va noter pour tout k N, G L(f (x ),....f (x )) Rn avec di f (xi ) .La méthode des

gradients conjugués consiste à chercher x k 1 x k Gk

tel que :

f (x k 1)

min

yx k G k

f ( y)

(en supposant qu’un tel minimum existe). Donc, on minimise la fonction f sur un espace plus
“grand"

que dans la méthode de gradient à pas optimal où on minimise f sur x k 1 x k Gk

G k L(f (x k ))

avec

Remarque :

– Si A a seulement « r » valeurs propres distinctes (avec r < n), alors l’algorithme du

gradient conjugué arrive à la solution en au plus r-itérations.
– Si A a des valeurs propres λ1 ≤ λ2 ≤ ... ≤ λn, nous avons que

2
x x^

nk 1

2
x x^

97
 k 1

A 0 A

nk 1

– Une caractéristique de l’algorithme de gradients conjugués est que la matrice A ne

nécessite aucune manipulation : pas besoin donc de stocker la matrice A, il suffit
d’implémenter (efficacement) les produits matrice-vecteur sans jamais former la
matrice.

De plus cet algorithme est surtout utilisé pour résoudre des systèmes linéaires de la forme :
Ax = b (ce qui correspond à la recherche de points critiques pour le problème quadratique
considéré) sans former la matrice A. Ceci est particulièrement intéressant pour les problèmes
de grande taille pour lesquels la matrice A est souvent creuse. A noter également, que la
méthode des gradients conjugués est une méthode dans laquelle les erreurs d’arrondis sont
amplifiées au cours des itérations. Peu à peu, les relations de conjugaison sont perdues car les
relations d’orthogonalité des gradients ne sont pas vérifiées exactement.

Théorème :

Si f : Rn R est quadratique et elliptique la méthode de gradient conjugué converge en n -itérations

au plus où n est l’ordre de A.

Remarque

Cette méthode est très stable même pour des matrices mal conditionnées. Elle demande 2n3
opérations dans le cas d’une matrice pleine et de n itérations pour une matrice creuse, le nom-
bre d’opérations diminue beaucoup.

98
 (a) Méthode de Newton

La méthode de Newton est attribuée au mathématicien, physicien et astronome anglais Issac New-
ton (1642-1727). C’est l’un des méthodes les plus anciennes utilisées pour résoudre les problèmes
d’optimisation.
Cette méthode permettant de trouver une solution d’un système (en général non linéaire) de n
équations avec n inconnues, autrement dit de trouver les zéros d’une fonction F :→ (dans le cas
évoqué, on a F f ), i.e. résoudre l’équation non linéaire F(x) = 0 dans Rn .
Dans le cas n = 1, cette méthode de Newton s’appelle également la méthode de la tangente.
L’idée est de remplacer le point xk obtenu à l’itération k, par le point d’intersection de la tangente
en
(xk; f(xk)) à la courbe représentative de f avec l’axe des abscisses.
Considérons maintenant le cas général, i.e. on dispose d’une fonction F :→ de classe (au moins)

C1 telle que l’équationF (x ) 0

positive.
admette au moins une solution x et la matrice H(x) est définie

Principe de la méthode de Newton :

L’idée de la méthode itérative de Newton est de minimiser à chaque itération l’approximation

quadratique de f ( de classe C2 ) au point courant x k et donnée par le développement de Taylor
d’ordre 2 :

f (x ) q(x ) f (xk

) (f (xk

), x xk

) 1 (x x

2 k

)t .H (x

).(x xk )

On considère le problème : min

q(x ),

x Rn .

99
Une condition nécessaire pour que le minimum de q(x) soit atteint est q(x ) 0 tel que

q(x ) f (x k ) H (x k )(x x k ) 0
Le vecteur généré à l’itération (k+1) est le vecteur minimisant q(x)

q(x k 1) 0 f (x k ) H (x k )(x k 1 x k ) 0
1
xk 1 x k (H (x k )) f (x k ),

Donc, la direction de descente choisie a chaque itération est

1
d k (H (x k )) f (x k ),

Elle est bien une direction de descente car elle vérifie la relation

En effet,

(d k ; f (x k ) 0,

k 0.

1
d (H (x )) f (x ) f (x ) H (x ).d

(d k

; f (x k

) (d k

,H (x k

).d k

t
) d .H (x

).d k 0

Car la matrice Hiessien est définie positive.

dk est appelée direction de Newton et les points sont successivement générés par cette méthode de
la manière :

100
x0

R n donné,

k 1

xk
• (H (xk

)) 1 f (x )

Remarques :

• Cette méthode est bien définie à chaque itération si la matrice hessienne H(xk) est définie
positive : ceci est vrai en particulier au voisinage de la solution x ^ cherchée si on suppose
que H ( x ^ ) est définie positive (par continuité de H ).

• La méthode de Newton est un algorithme de descente à pas fixe égal à 1.

• Si la fonctionnelle f est quadratique, strictement convexe, alors l’algorithme converge en une

seule itération.

Algorithme de la méthode de Newton

• Initialisation K=0,
choix de x0 dans un voisinage de x ^ ,

• Itération k

x x H (x )1 f (x )

• Critère d’arrêt

si xk 1 xk

101
stop

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

Remarques :

-La méthode de Newton est intéressante car sa convergente est quadratique au voisinage de la
solution

1. à-d :

xk 1 x^
2
x x^ ,
0

mais la convergence n’est assurée que si x0 est suffisamment proche de x ^ , ce qui en limite l’intérêt
pour cela nous allons donner le théorème qui garanti la convergence.

-L’étape 2 de l’algorithme revient à résoudre le système linéaire suivant:

H (x k )(x k x k 1) f (x k )

Théorème :

Soit

f : Rn R avec f C 2
(R n
) et un point x ^ de Rn tel que f (x ^) 0,
et H 1 (x ^) existe. Soit x 0 un

point initial assez proche de x ^ de sorte que cette proximité s’exprime de la façon suivante :

102
1) (H (x )) 1

K1 .

K1 , K 2 0 avec K 1 K 2 x 0 x ^

1. tel que

2) f (x ^) f (x ) H (x )(x x ^)

K 2

2
x x^ .

Pour tout x satisfaisant

x x^

x0 x^ .

Alors, l’algorithme converge d’une façon super-linéaire (quadratique) vers x ^ .

Inconvénients de la méthode de Newton :

1. Cette méthode fonctionne très bien pour les petits dimensions (1 n 10 ) lorsque on peut

calculer facilement H (x ) et

(H (x )) 1 , ce calcul nécessite des itérations plus nombreuse et

coûteuse dans les problèmes des grandes tailles.

(a) Comme x k 1 x k (H (x k )) 1 f (x k ), le point (xk 1 ) n’est pas toujours bien définie c-à-d
possible que (H (x )) 1 n’existe pas ( cela intervient typiquement lorsque la méthode
atteint un région où f est linéaire donc ses secondes dérivées partielles valent zéro), et
même elle est existe, la direction d k (H (x k )) 1 f (x k ), n’est pas toujours une direction
de descente ( si (H (x k )) est définie positive alors d k est une direction de descente).

3- L’inconvénient majeur de la méthode est sa sensibilité au choix du point de départ x0 : Si

ce
point est mal choisis (trop loin de la solution) la méthode peut soit diverger, soit converge
vers une autre solution. Pour choisir le point de départ x0 “assez prés" de x ^ on essaie de
s’approcher de x ^ par une méthode de type gradient par exemple, puis on applique la méthode
de Newton.

103
 (a) Méthode de Quasi-Newton

Les méthodes de Quasi-Newton sont élaborées pour l’optimisation et pour pallier aux inconvénients
de la méthode de Newton elle :

i. garde la rapidité de la méthode de Newton,

ii. évite le calcul (coûteux) de la matrice [H(xk)] à chaque itération.
iii. plus robustes par rapport au du point de départ. On y trouve les méthodes dites
“région de confiance" qui s’attachent à rendre la méthode robuste (i.e. peu
sensible) par rapport x0.
iv. (H(x))-1 n’est pas nécessairement connue, peut être très chère à calculer, et H(xk)
peut être très difficile à inverser. On remplace alors et (H(xk))-1 par une matrice Dk,
éventuellement constante, qui est censée approcher H (xk) ou bien son inverse. Parfois
même, on remplace H (x )1 f (x ) par un vecteur yk facile à calculer, économisant ainsi
l’encombrement de la matrice en mémoire.
Donc, l’algorithme de cette méthode est donné comme suit :

Algorithme de la méthode de Quasi-Newton

A. Initialisation K=0,
choix de x0 , 0 ,
B. Itération k
x k 1 x k k Dk f (x k )
C. Critère d’arrêt

si xk 1 xk

stop

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

Remarque :

Dans cet algorithme, on va utiliser une approximation Dk de (H(xk))-1 et puis on va trouver k ( par

une recherche linéaire) qui minimise la fonction

() f (x k k dk )

104
Exercices du chapitre III

Exercice 1 : -———————————————————————————————–

Soit
f (x ) 1 ( Ax, x ) (b, x ) où A est une matrice symétrique définie positive N N
2
de valeurs

propres 0 1

... N

et b R n
. Notons x ^ le minimum de f sur Rn . On considère la suite (uk )

d’éléments de Rn telle que u Rn quelconque et

k N, u k 1 u k f (u k )

où est un réel positif fixé.

• Montrer que

uk 1 x ^ (I n A)(u x ^) , où In désigne la matrice identité de taille N .

• Montrer que l’algorithme de gradient à pas fixe converge pour :

0 2/ N

Exercice 2
:————————————————————————————————————

Soit f(x) une fonction C 1 sur Rn . On sait que dans un voisinage d’un point a Rn , f diminue le
plus rapidement si l’on passe dans la direction de la pente négative de f à a, c’est à dire la direction
(f (a))

On commence avec une estimation, x 0, pour un minimum local de f et considère la séquence

(x 0 , x 1,.........) où

suit:

105
i N,

xi 1 x i f (x i ) tel que :

f (x 0 ) f (x 1) f (x 2 ) .......

et f(x) est définie comme

f (x ) 1

t 6

x 16

1x

1. Quel est l’unique minimum (global) x ^ de f ?

2. En commençant avec x0 = [0 0]t et = 0.1, calculer les deux itérés suivants x1 et x2.

3. Trouver la taille de pas maximum pour que la méthode converge vers x ^ quel que soit le
point

x0.

Exercice 3
:————————————————————————————————————

On cherche les minima locaux de la fonction :

J (x , x ) 1 x 2 x cos(x )

1 2 2 1 1 2

• Déterminer l’ensemble de points de minimum locaux en utilisant les conditions nécessaires.

106
 • Appliquer la méthode de Newton avec le point de départ u 0 .Observer le comportement
des

itérées et le point de convergence. Expliquer les observations.

• Déterminer le modèle quadratique de la fonctionnelle J. Y a-t-il équivalence entre

l’algorithme de Newton et la méthode utilisant le modèle quadratique ? Pourquoi ?

Exercice 4
:————————————————————————————————————

Considérons le problème d’optimisation quadratique suivant

1 t t

(P ) min

X AX b X

où A est une matrice symétrique définie positive

N N

de valeurs propres 0 1

... N

et b RN .

• Comment s’exprime dans ce cas la méthode de Newton ?

• Sa convergence dépend-elle du point initial ?

107
 • En combien d’itération converge-t-elle ? Réinterpréter la méthode de Newton.

Exercice 5
:————————————————————————————————————

On cherche à trouver le min d’une fonction f de Rn dans R, on utilise la méthode de gradient à pas

optimal : xk 1 xk k f (xk ) où k est la solution du problème min f (x f (x )), R

• On suppose que f est convexe, montrer la convergence de la méthode ?

• Quels sont les problèmes posés par la mise en œuvre numérique de la méthode ?

• Proposer un algorithme basé sur la méthode du gradient à pas constant, consistant à poser

x x f (x ) où est choisi dans une liste donnée à l’avance : , ,

,...,

k 1 k k k k

2 4 2k

Exercice 6
:————————————————————————————————————

Soit A M (R) et J la fonction définie de IRN dans IR par : J (x ) e Ax 2

euclidienne sur IRN .

• Montrer que J admet un minimum (on pourra le calculer. . . ).

, où .
désigne la norme

• On suppose que la matrice A est inversible, montrer que ce minimum est unique.

• Ecrire l’algorithme du gradient à pas optimal pour la recherche de ce minimum. [On

demande de

108
calculer le paramètre optimal k
algorithme converge-t-il ?
en fonction de A et de x k]. A quelle condition suffisante cet

Exercice 7
:————————————————————————————————————

On considère la fonction f définie par

f (x, y) x 4 y 4 4xy

– Trouver les points critiques et la nature de chacun d’entre eux.

– On applique l’algorithme de gradient à pas fixe à la minimisation de f avec un pas fixé .

Prouver que, pour toute initialisation (x0,y0), l’algorithme converge, pour assez petit, vers un

point critique de f. On choisit x0=y0=1, Que ce passe-t-il si 0.25 ? si 0.5 ?

Exercice 8 :——————————————————————————————
——————

Soit la fonction de Rosenbrock définie comme suit :

f (X ) f (x , x ) 100(x x 2 )2 (1 x )2

1 2 2 1 1

• Calculer le gradient et la matrice Hessienne de la fonction f.

• Vérifier que x ^ 1, 1t est un minimum local de f.

• Calculer les 5 premiers itérés de la méthode de Newton pour minimiser f en commençant par

x . Calculer la norme de l’erreur x x ^ à chaque itération et déterminer si le taux de

1, 2t
convergence est quadratique.

109
 Solutions des exercices

...............................................................................................................................
Chapitre I
....................................................................................................................................................................
Exercice 1 :

1) S x, y R 2 ; y x 2 0

L’ensemble S est un convexe si X 1, X 2 S,

Soit X1 ,X2 deux vecteurs de S, alors

0,1,

X1 1 X 2 S.

X S X (x , y ) R 2 tel que

y x 2 0

1 1 1 1

1 1 , on obtient

X S X (x , y ) R 2 tel que

y x2 0

2 2 2 2

X 1X

2 2

x 1 x , y 1 y R 2 tel que :

110
y 1 y

2 1 2 1 2

2 2
1 x 2 y 1 y 2 x 1 2 x 21 x x

1 y

1 x

2 2 2 2
2 x 1 x 2 x 1 2 x 21 x x

x 2 1 1x 2 21 x x

1 2 1 2

1 x 2 x 2 2x x 1 (x x )2 0

d’où le résultat.

1 2 1 2 1 2

S x, y R 2 ;

x 0,

y 0,

x y 1

L’ensemble S est un convexe si X 1, X 2 S,

Soit X1 ,X2 deux vecteurs de S, alors

111
0,1,

X1 1 X 2 S.

X S X (x , y ) R 2 tel que

x 0, y 0, x y 1

1 1 1 1

1 1 1 1

, on obtient

X S X (x , y ) R 2 tel que x 0, y 0, x y 1

2 2 2 2 2 2 2 2

X 1 X x 1 x , y 1 y R2 :

avec

1 2 1 2 1 2

et

de plus

x 1 1 x 2 0 car x 1 0, x 2 0, 0;1 et (1 ) 0;1

y 1 1 y 2 0; car y 1 0, y 2 0, 0;1 et (1 ) 0;1

x 1 1 x 2 y 1 1 y 2 (x 1 x 2 ) (1 )( y 1 y 2 ) 1

X 1 1 X 2 S.

et donc S est un convexe

Exercice 2 : Vraie ou fausse (justifier). . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .

112
 • La somme de deux convexes est un convexe : vraie
Soient S1 ,S2 deux convexes de Rn . La somme de ces convexes est l’ensemble

S S1

•
S2

x x

x2 /

x 1 S 1 et

x2 S2

Soit X ,Y deux vecteurs de S, alors

X S X x 1 x 2 tel que

Y S Y y 1 y 2 tel que

on obtient

x 1 S 1,

y1 S 1 ,

x2 S2 , ,

y2 S 2

X 1 Y (x 1 x 2 ) (1 )( y 1 y 2 )

x 1 1 y 1) (x 2 1 y 2

Comme S1 ,S2 sont des convexes de Rn ; alors

X 1 Y x 1 1 y 1) (x 2 1 y 2 S 1 S 2

Donc, la somme de deux convexes est un convexe.

• Le produit de deux convexes est un convexe : Fausse

• Soit S i

113
 Rn ,

(i 1,..., n), convexe. Alors (

i 1,n

Si ) est un convexe :vraie

• Soit un ensemble S Rn convexe. Alors S convexe : vraie.

• Soient un ensemble S Rn convexe et deux réels positifs ,

vraie.

– L’inclusion ( )S S S est toujours vraie.

. Alors

S S ( )S

– Dans le cas ,

sont positive, l’inclusion inverse provient du fait que :

x ; y S,S S x y ( ) x y ( )S

• Tout ensemble affine est convexe : vraie car un ensemble S de Rn est dit affine si :

x 1, x 2 S,

R,

x 1 1 x 2 S.

114
Exercice 4 :. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .

1. La composée de deux fonctions convexes n’est pas forcement convexe. En effet, les fonctions

g(x ) x et

Sont bien convexes sur R, et pourtant

f (x ) x 2

n’est pas convexe sur R. Remarque :

gf (x ) x 2

Soient f une fonction convexe et g une fonction convexe croissante, alors

gf

est

convexe.

1. Soient f et g deux fonctions convexes sur l’intervalle I de R, donc

x, y I ,

x, y I ,

Or si on pose h=sup(f ;g)

0,1

0,1

f (x (1 ) y) . f (x ) (1 ) f ( y)

g(x (1 ) y) .g(x ) (1 )g( y)

Donc

f (x ) h(x )

115
et g(x ) h(x )

De même Donc

. f (x ) (1 ) f ( y) .h(x ) (1 )h( y)

.g(x ) (1 )g( y) .h(x ) (1 )h( y)

sup( f (x (1 ) y), g(x (1 ) y) h(x (1 ) y) h(x ) (1 ) y

et h est bien convexe.

En revanche, pour inf (f,g) cela ne marche pas, il suffit de prendre f(x)=x ; g(x)=0 qui sont
convexes.

Exercice 7 :. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .

Soit

f : RN RN

la fonction définie par, N N est une matrice Aavec

f (x ) 1 ( Ax, x ) (b, x )

symétrique et b RN .

(a) Montrons que f est différentiable sur RN .

Pour tout h RN , on a

f (x h) 1 ( A(x h), x h) (b, x h) 2

1 ( Ax, x ) ( Ax, h) 1 ( Ah, h) (b, x ) (b, h)

2 2

116
 f (x ) ( Ax b, h) ( Ax, h) 1 ( Ah, h)

Si on pose

(h) 1 ( Ah, h) / h

2 , alors

( Ah, h)

A.h 2 lim (h) 0

Donc f est différentiable .sur R N .

2 h0

(a) Calculer le gradient et la matrice Hessienne de f.

D’après la question précédente,

df (x ).h ( Ax b, h)

et f (x ) Ax b

Il est clair que la fonction f est deux fois différentiable. Pour tout x RN

df (x k ).h (Ax b, h) (Ak, h)

117
Comme A est supposée symétrique ; on conclut que

h, k Rn

2 2
d f (x ).(h, k ) (Ah, k ) et H ( f )(x ) f (x ) A.

(a) Montrer que f est convexe ssi A est semi définie positive.
Rappelons que la fonction f est convexe si et seulement si :

∀x,y∈Rn , f ( y) f (x ), y x 0.

D’autre par, on a f (x ) Ax b ; il vient alors

f est convexe

( Ay b) ( Ax b), y x 0.

A( y x ), y x 0. x ; y Rn

Az, z 0. z Rn

Donc f est semi définie positive.

(a) Montrer que f est strictement convexe ssi A est définie positive.

La stricte convexité de f est équivalente à

Donc

x, y R;n

x y ; f ( y) f (x ), y x 0.

f est strictement convexe

118
( Ay b) ( Ax b), y x 0.

A( y x ), y x 0. x ; y Rn

Az, z 0. z Rn

Donc f est définie positive.

Chapitre 2

Exercice 2

Dans le théorème d’existence du minimum (sans contraintes) d’une fonction f, montrer que l’on
peut remplacer la propriété « infinie à l’infini » par la condition plus faible

inf f (x ) lim (inf

f (x )),

r 0

x Rn

Soit (v ) une suite minimisante de f sur Rn c’est-à-dire

x r

on a

f (v n ) inf f (x )

119
 n xR

inf

f (x ) lim (inf

f (x )),

r 0

x Rn

r x r

Donc, il existe 0; pour « r » assez grand, on a

f (vn ) lim ( inf

r x Rn

f (x ) ),

Ainsi, pour « r » assez grand, on a

f (v ) lim

f (x ),

On déduit que pour « r » assez grand, (vn ) à la boule de rayon « r », autrement dit ; la suite (vn
) reste bornée. La suite de la démonstration est alors identique à la démonstration initiale.

Exercice 8 :

Considérons la fonction

f : R n
R suivant :

x Rn ,

f (x ) sin( x 2 ) sin n

120
i 1

• Montrer que la fonction f est différentiable sur Rn et calculer son gradient.

La fonction est différentiable et même C1 par les théorèmes généraux (somme, produit, composition)
de fonction C1 .
On calcule son gradient via ses dérivées partielles

f (x ) 2x cos( A), 2x cos( A);...2x cos( A) où A x 2

1 2 n

i1

• Montrer que la fonction f est C2 et calculer sa matrice Hessienne.

La fonction est C2 par les théorèmes généraux (somme, produit, composition) de fonction C2 .
On calcule sa matrice hessienne H ( f )(x ) h via ses dérivées partielles secondes

h ii

2cos( A) 4x 2 sin( A)

H (f ) h

4x x sin( A) i j

ij i j

121
 • Déterminer tous les extrema (minima et maxima) de f sur Rn . On calcule les points
critiques : on a rf (x ) 0 si et seulement si

f (x ) 2x cos( A), 2x cos( A);...2x cos( A) (0,0,...,0)

1 2 n

i 1,...;n; 2x i cos( A) 0

Il y a donc le point x = (0,. . .., 0) et tous les points

x Rn ,

k ,k N

Réciproquement, tous ces points sont des extrema : en effet, au point x=(0,. . .,0) la hessienne vaut
2I et est donc définie positive (CS2 : il s’agit d’un minimum local) et aux points

x Rn ,

k ,2

k N f (x ) (1)k

(minimum si k impair et maximum si k pair).

Représenter graphiquement ces extrema dans le cas où n = 2.
Graphiquement, si n = 2, les minima sont situés en 0 en sur des cercles de rayon

et les maxima sur des cercles de rayon

2p ,2

p N

(2 p 1) , 2

p N

Exercice 9 :

Considérons la fonction

122
f : R 2
R suivant :

2 2
f (x , x ) 2x 2x x x x x

1 2 1 1 2 2 1 2

• La fonction f s’écrit sous la forme quadratique

1 ( Ax, x ) (b, x ) 2

avec :

42 1

,b

2 1

– Soient min

et max

la plus petite et la plus grande valeur propre de A. Montrer que

2
x R ,

min

2
x Ax, x

max

x 2,

On a la matrice A symétrique donc ses valeurs propres sont réelles positives et ses valeurs propres
forment une base orthonormée donc

x R 2 ,

123
x x 1 x 2 et

Ax x

x R2 ,

Ax (A(x x )) (Ax Ax ) x x

1 2 1 2 1 1 2 2

( Ax, x )

(x x ,x x ) 2 2

1 1 2 2 1 2 1 2

Si 1 min

et 2 max , alors

x ( 2 2 ) (Ax, x ) 2 2 ( 2 2 ) x

max 2 2

1 2 1

min 2

Si 1 max

et 2 min x , alors

124
 x ( 2 2 ) (Ax, x ) 2 2 ( 2 2 ) x

max 2 1

On en déduit que

1 2 2

min 2

Remarque :
Dans le cas général :

x R 2 ,

min

x 2 Ax, x

max 2

La matrice A est symétrique, toutes ses valeurs propres i sont réelles ( éventuellement

nulles), et elle admet une base de vecteurs propres orthonormés B v ; v .....; v

Av i i vi

pour i=1,2,. . .,n et v , v

pour i ;j=1,2,. . . ;n

Pour tout vecteur x RN , on a donc

x xv,

Ax x Av

xv

et Ax, x x 2

i i

125
i 1

i i

i 1

i i i

i 1

i i

i1

Soit finalement

n n

min x 2 Ax, x max x 2

i i

i i1

i i

i i1

– Montrer que si A est définie positive, alors f coercive et admet un minimum sur R2 .

La matrice A est définie positive alors f est strictement convexe, de plus, la fonction f est
coercive :

f (x ) 1 ( Ax, x ) (b, x )

f (x )

min

x 2 b. x

Car (b, x )

b . x .cos(b, x )

Comme

126
min 0

donc
: lim

f (x )

lim

(min
2
x b. x )

Comme f est continue ( car elle est quadratique) , coercive et strictement convexe donc elle atteint
son min.
Exercice 11 :

On considère la fonction g de R2 dans R définie par la relation : g(x, y) x 2 y 2 xy

• Montrer que la fonction g est coercive. On a

2
x y x2 y2

x2 y2 2

g(x, y)

2 2 2 2

(x, y)

et la fonction est donc coercive.

127
 • Montrer que la fonction g est strictement convexe sur R2 . La matrice hessienne de g en tout
point x de R2 est égal à

21

H (x, y)

12

Cette matrice est définie positive et donc g est strictement convexe.

• La fonction g est continue et coercive donc possède au moins un minimum sur R2 . De plus,
g est strictement convexe donc ce minimum est unique. Ce minimum est à rechercher parmi
les points critiques : ceux ci sont tels que

2x y 0

2y x 0

soit x = y = 0. Il s’agit donc du minimum de g.

Chapitre 3

Exercice 1 :

Soit
f (x ) 1 ( Ax, x ) (b, x ) où A est une matrice symétrique définie positive N N
2
de valeurs propres

0 1

... N

et b R n
. Notons x ^ le minimum de f sur Rn . On considère la suite (uk ) d’éléments de Rn

telle que u Rn quelconque et

k N, u k 1 u k f (u k ) où est un réel positif fixé.

• Montrer que

128
 uk 1 x ^ (I n A)(u k x ^) , où In désigne la matrice identité de taille N .

La fonction f est quadratique doncf (x ) Ax b et comme x ^ est le minimum de f sur Rn ,on

obtient

f (x ) Ax ^ b 0 x ^ A1 b

k N, u k 1 u k f (u k ) u k 1 u k (Au k b)

uk 1 x ^ u k (Au k b) x ^ (u k x ^) A(u k x ^)

uk 1 x ^ (I n A)(u

x ^)

• Montrer que l’algorithme de gradient à pas fixe converge pour :

0 2/ N

Supposons que 0 2 / N et notons e n u n x ^ . Pour établir la convergence de la méthode GPF,

nous allons montrer que la norme de l’erreur e n tends vers 0 lorsque n .

Observons d’abord qu’on a b Ax ^ :

e n1 u k 1 x ^ (I n A)(u x ^) (I n A).e n

On sait qu’il existe une base orthonormée de vecteurs propres de A, notons par

(v i )1i n . Soit

n n n n

129
y Rn y yv

(I A) y (I

A).y v ( y v Ay v )

(1 )yv

Ainsi

i i i 1

n n

i 1

1. i

i 1

2. i

i i

i 1

i ii i

2
(I A) y (n

(I A).y v ;

(I A).y v )

(1 )2 y 2

n 2 n i 1

i i n

i 1

i i i i

i 1

130
 n

max (1 )2

y 2 max (1 )2 y 2

i i i 2

i 1

2 2 2
e (I A)e max (1 )2 e

n1 n n i

i n 2

Donc

e n12

max 1 i . en

Notons max 1 i

B . Par raisonnement par récurrence ; on obtient

e Bn . e lim . e e

lim Bn 0

car B 1 en utilisant

n 2 0 2 n n 2

0 2/ N .

0 2 n

Exercice 2 :
Soit f(x) une fonction C 1 sur Rn . On sait que dans un voisinage d’un point a Rn , f diminue le
plus rapidement si l’on passe dans la direction de la pente négative de f à a, c’est à dire la direction
f (a)
On commence avec une estimation, x 0, pour un minimum local de f et considère la séquence

131
(x 0 , x 1 , )

suit:

où i N,

xi 1 x i f (x i ) tel que :

f (x 0 ) f (x 1) f (x 2 ) .......

et f(x) est définie comme

f (x ) 1

t 6

x 16

1x

1. Quel est l’unique minimum (global) x ^ de f ?

La fonction f est quadratique de la forme

f (x ) 1 xt Ax bt .x tel que A

1 donc f est

132
continue, de plus elle est coercive et strictement convexe (sa matrice hessiene est définie positive car
ses valeurs propres (4 et 8) sont strictement positive) ; f alors, admet un unique minimum global
x ^ caractérisé par

f (x ^) 0 Ax ^ b x ^ A1 b

x^ 1 ,

1 t

x ^ 0.25; 0.25t

1. En utilisant la méthode de gradient à pas fixe pour calculer les deux itérés suivants x1 et x2.
En commençant avec x0 = [0 0]t et = 0.1,

On a i N,

xi 1 x i f (x i )

avec

6 2

x1

f (x ) Ax b 2

133
6 x

donc

0.1

x 1 x 0 f (x 0 ) 0 (0.1)

0.1

0.1

6.(0.1) 2(0.1) 1

0.16

x 2 x 1 f (x 1 ) (0.1)

0.1

2.(0.1) 6(0.1) 1 0.16

1. Trouver la taille de pas maximum pour que la méthode converge vers x ^ quel que soit le
point x0.

134
où n

D’après l’exercice 1, l’algorithme de gradient à pas fixe converge pour :

est la valeur propre maximal de A ; qui est dans ce cas 8, donc

0 1 0; 0.25

0 2/ N

Exercice 4 :. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . ..

Considérons le problème d’optimisation quadratique suivant :

1 t t

(P ) min

X AX b X

où A est une matrice symétrique définie positive

N N

de valeurs propres 0 1

... N

et b R n
.

- Comment s’exprime dans ce cas la méthode de Newton ?

L’algorithme de la méthode de Newton s’exprime sous la forme suivante

i N, x x H (x )1.f (x )

i 1 i i i

135
 i N, x

x A1 .Ax b) A1 b

i 1 i i

x A1 b

i 1

Puisque la matrice A est définie positive; alors

x ^ A1 .b est l’unique minimum de f sur Rn ;

ainsi, la méthode de newton équivaut à la résolution directe.

- Sa convergence dépend-elle du point initial ? En combien d’itération converge-t-elle ? La
convergence de la méthode de Newton pour cette fonction quadratique se fait en une itération et
ne dépend pas du point initial.

Bibliographie

• G. Allaire, Analyse numérique et optimisation, Edition 2002.

• M. Belloufi, Cours d’optimisation sans contraintes, 2015

[3 ] M. Bergounioux, Optimisation et contrôle des systèmes linéaires, Dunod, Paris, 2001.

• M. Bierlaire, Introduction à l’optimisation différentiable, PPUR, 2006.

• 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.

[6 ] O. Brun, Eléments d’optimisation, INSA, 2010.

• P. Ciarlet, Introduction a l’analyse numérique matricielle et à l’optimisation, Masson, 1988.

• Y. Dodge, Optimisation appliquée, Springer, 2005.

• R. Fletcher, Practical Methods of Optimization vol. 1 : Unconstrained Optimization, John

Wiley & Sons, New York, 1987.

136
• 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).

• J. C. Gulioli , Introduction à l’optimisation, Ellipses, 1994.

• J-B. Hiriart-Urruty, Optimisation et analyse convexe, exercices corrigés, EDP sciences,

2009. [13 ] A. Iouditski, Optimisation et analyse convexe, Notes de cours. 2002.

• J. Nocedal, and S. J. Wright, Numerical Optimization, Springer Series in Operations

Research and Financial Engineering, second ed, 2006.

• R.T. Picard, Convexité et applications, Notes de cours. Université de Rennes 1.

• G.R.Walsh, Methods of optimization, A wiley- Interscience Publication, 1975. Sites

Internet

– http://dumas.perso.math.cnrs.fr/LSMA651-2011.html
– http://dumas.perso.math.cnrs.fr/
– http://aeropedia.enac-aerospace.eu/index.php?title=Optimisation
– https://www.ljll.math.upmc.fr/~boulmezaoud/OUTILS_PAGE/affiche_text.php?p
age=ens&lang=0ng=0

137