Minimisation Sans Contraintes

Minimisation sans contraintes
BELGACEM Rachid
UHBC. Uni de Chlef.
27 janvier 2021
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 27 janvier 2021 1 / 29
Soit f : Rn → R une fonction continûment différentiable.

Definition
On appelle problème de minimisation sans contraires le problème (P)
suivant :
(P) min f (x ) : x ∈ Rn .
Definition
1 On dit que x ∗ est un minimum global de f sur S si
∀x ∈ S, f (x ∗ ) ≤ f (x ) .
2 On dit que x ∗ est un minimum global strict de f sur S si
∀x ∈ S, avec x 6= x ∗ , f (x ∗ ) < f (x ) .
3 On dit que x ∗ est un minimum local strict de f sur S, s’il existe

r > 0 tel que
∀x ∈ B (r , x ∗ ) ∩ S, f (x ∗ ) ≤ f (x ) .
4 On dit que x ∗ est un minimum local strict de f sur S, s’il existe

r > 0 tel que
∀x ∈ B (r , x ∗ ) ∩ S avec x 6= x ∗ , f (x ∗ ) < f (x ) .
Figure – Exemples de minima et de maxima locaux et globaux
Figure – Infinité de minima et de maxima globaux
Figure – Pas de maximum global- Infinité de minima et de maxima locaux
Figure – Graphe de x 7−→ x 2 , x ∗ = 0 est un minimum global
Figure – Maximum au point P

Figure – Minimum au point P
Proposition
Si x ∗ réalise un maximum (local ou global) de f sur S, x ∗ réalise un
minimum (local ou global) de −f sur S. Plus précisément
max {f (x ), x ∈ S} = − min {−f (x ), x ∈ S}
Donnons la preuve pour un maximum global : c’est exactement la même

pour un maximum local.
Soit x ∗ tel que f (x ∗ ) = max {f (x ), x ∈ S}. On a donc
∀x ∈ S : f (x ) ≤ f (x ∗ ) ⇔ ∀x ∈ S : −f (x ) ≥ −f (x ∗ )
⇔ −f (x ∗ ) = min {−f (x ), x ∈ S}
⇔ f (x ∗ ) = − min {−f (x ), x ∈ S}.
Proposition
Si x ∗ réalise un maximum (local ou global) de f sur S, x ∗ réalise un
minimum (local ou global) de −f sur S. Plus précisément
max {f (x ), x ∈ S} = − min {−f (x ), x ∈ S}
Donnons la preuve pour un maximum global : c’est exactement la même

pour un maximum local.
Soit x ∗ tel que f (x ∗ ) = max {f (x ), x ∈ S}. On a donc
∀x ∈ S : f (x ) ≤ f (x ∗ ) ⇔ ∀x ∈ S : −f (x ) ≥ −f (x ∗ )
⇔ −f (x ∗ ) = min {−f (x ), x ∈ S}
⇔ f (x ∗ ) = − min {−f (x ), x ∈ S}.
Theorem
Soient S un ensemble convexe de Rn et f une fonction convexe de S dans
R. Alors, tout minimum local de f est aussi global.
Soit x ∗ un minimum local. Raisonnons par absurde et supposons que x ∗

n’est pas un minimum global, donc
∃x ∈ S : f (x ) < f (x ∗ ) . (1)
On peut donc choisir un λ suffisamment petit dans ]0, 1[ tel que

y = x ∗ + λ (x − x ∗ ) soit dans B (r , x ∗ ). De la convexité de f on déduit que
f (y ) = f (x ∗ + λ (x − x ∗ )) ≤ (1 − λ) f (x ∗ ) + λf (x ) ,
on aura
f (y ) < (1 − λ) f (x ∗ ) + λf (x ∗ ) = f (x ∗ ) .
Ceci étant en contradiction avec le fait que x ∗ est un minimum local.
Theorem
Soient S un ensemble convexe de Rn et f une fonction convexe de S dans
R. Alors, tout minimum local de f est aussi global.
Soit x ∗ un minimum local. Raisonnons par absurde et supposons que x ∗

n’est pas un minimum global, donc
∃x ∈ S : f (x ) < f (x ∗ ) . (1)
On peut donc choisir un λ suffisamment petit dans ]0, 1[ tel que

y = x ∗ + λ (x − x ∗ ) soit dans B (r , x ∗ ). De la convexité de f on déduit que
f (y ) = f (x ∗ + λ (x − x ∗ )) ≤ (1 − λ) f (x ∗ ) + λf (x ) ,
on aura
f (y ) < (1 − λ) f (x ∗ ) + λf (x ∗ ) = f (x ∗ ) .
Ceci étant en contradiction avec le fait que x ∗ est un minimum local.
Résultats d’existence et d’unicité
On considère le problème d’optimisation

(
min f (x )
(2)
x ∈ S ⊂ Rn .
Avant d’étudier les propriétés de la solution (ou des solutions) de ce

problème il faut s’assurer de leur existence. Nous donnerons ensuite des
résultats d’unicité.
Nous voyons dans la suite deux conditions suffisantes d’existence d’extrema
globaux : la compacité du domaine et la coercivité de la fonction.
Pour une fonction f et un ensemble S quelconques, la solution du problème
(2) peut ne pas existée.

(
min f (x )
(2)
x ∈ S ⊂ Rn .


(
min f (x )
(2)
x ∈ S ⊂ Rn .

Résultats d’existence et d’unicité Existence
Existence : Compacité du domaine
Theorem (Weierstrass)
Soient S un compact (i.e fermé et borné ) de Rn et f : S −→ R. Si f est
continue alors f atteint ces bornes (i.e f admet un minimum ainsi qu’un
maximum global sur S) c.à.d
∃x ∗ ∈ S : inf f (x ) = min f (x ) = f (x ∗ ) ,
x ∈S x ∈S
et
∃x ∗∗ ∈ S : sup f (x ) = max f (x ) = f (x ∗∗ ) .
x ∈S x ∈S
Rappelons que si S = Rn , le problème

(
min f (x )
(3)
x ∈ Rn .
est dit problème d’optimisation sans contraintes.

Le théorème de Weierstrass ne peut s’appliqué dans cette situation, vue la
non compacité de S.
La notion de fonction coércive devient primordiale.

(
min f (x )
(3)
x ∈ Rn .


(
min f (x )
(3)
x ∈ Rn .

Fonction Coercive
Definition (Fonction Coercive)

Soit f : Rn −→ R, f est dite coercive si
lim f (x ) = +∞.
kx k→+∞
Figure – Exemples de fonction coercives
Figure – Exemples de fonction non coercives

Example
1 x 7→ x 2 , est coercive (car : lim|x |→+∞ x 2 = +∞).
2 (x1 , x2 ) 7→ x12 + x22 , est coercive (car
x12 + x22 = k(x1 , x2 k2 → +∞).
k(x1 ,x2 k→+∞
3 (x1 , x2 ) 7→ x12 − x22 ,
n’est pas coercive. En effet, si on considère la suite
∀n, xn = (0, n), on a bien limn→∞ kxn k = +∞, or
limn→∞ f (xn ) = limn→∞ −n2 = −∞.

4 Soit A une matrice carrée d’ordre n symétrique, définie positive et b un

vecteur de Rn . Alors la fonction f définie par
1
f (x ) = hAx , bi − hb, x i,
2
est coercive.
Une application coercive a un minimum
Theorem (Existence)
Soit f : Rn −→ R, continue et coercive. Alors le problème (3) admet au
moins une solution a .
a. Si −f est coercive, f admet un maximum global.
Résultats d’existence et d’unicité Unicité
Unicité
Theorem
Soit f : Rn −→ R, si le problème (3) admet une solution et si f est
strictement convexe, alors la solution est unique.
Raisonnons par absurde et supposons qu’ils existent deux solutions pour (3)
x1 , x2 avec x1 6= x2 et f (x1 ) = f (x2 ) = d. Comme f est strictement convexe
et en particulier pour λ = 21 , on aura
1 1 1 1

f x1 + x2 < f (x1 ) + f (x2 ) = d,
2 2 2 2
ceci étant en contradiction avec le fait que d est le minimum. Donc x1 = x2 .
Unicité
Theorem
Soit f : Rn −→ R, si le problème (3) admet une solution et si f est
strictement convexe, alors la solution est unique.
Raisonnons par absurde et supposons qu’ils existent deux solutions pour (3)
x1 , x2 avec x1 6= x2 et f (x1 ) = f (x2 ) = d. Comme f est strictement convexe
et en particulier pour λ = 21 , on aura
1 1 1 1

f x1 + x2 < f (x1 ) + f (x2 ) = d,
2 2 2 2
ceci étant en contradiction avec le fait que d est le minimum. Donc x1 = x2 .
Exercice 1
Exercice
Soit f : R2 −→ R telle que
f (x , y ) = x 2 + y 2
1 Prouver la coércivité et la convexité stricte de f .

2 Trouvez en utilisant la définition une solution minimum globale.
Corrigé 1
1 On a f (x , y ) = k(x , y )k2 , alors lim f (x , y ) = +∞, d’ou la

k(x ,y )k→+∞
coércivité de f . !
2 0
D’autre part, la matrice ∇2 f (x , y )
= est définie postive
0 2
alors la fonction f est strictement convexe.
2 Soit (x ∗ , y ∗ ) la solution global, f (x , y ) = x 2 + y 2 ≥ f (x ∗ , y ∗ ),
∀ (x , y ) ∈ R2 .
On a :
∀ (x , y ) ∈ R2 , f (x , y ) = x 2 + y 2 ≥ 0 = f (0, 0),
∀ (x , y ) ∈ R2 , f (x , y ) ≥ f (0, 0),
donc (0, 0) est une solution minimum global et f (0, 0) = 0 la valeur

minimal global.
Figure – Graphe de z = f (x , y ) = x 2 + y 2
Exercice 2
Exercice
Les fonctions J suivantes sont-elles coercives ?
1 J : R → R définie par J(x ) = x 3 + x 2 + 1.
2 : Rn → R définie par J(x ) = ha, x i + b avec a ∈ Rn et b ∈ R.
3 J : R2 → R définie par J(x ) = 2x12 + x2 − 1.
4 J : R2 → R définie par J(x ) = 2x12 + x23 + 2x12 .
5 J : R2 → R définie par J(x ) = x12 + x22 − 1000x1 − 5000.
6 J : R2 → R définie par J(x ) = x14 + x24 − x12 .
Corrigé 2
1 Non, car lim x 2 = −∞ quand x −→ −∞.

2 Si a = 0 alors J est constante et ne peut pas être coercive. Si a 6= 0, il
existe i0 , 1 ≤ i0 ≤ n tel que ai0 6= 0. On prend la suite xk = −kai0 ei0
(où ei est le i ème vecteur de base). Lorsque k −→ +∞, on a
kxk k −→ −∞ et J(xk ) −→ +∞. J n’est donc jamais coercive.
3 Non : prendre la suite xn = (0, −n).
4 . Non : prendre la suite xn = (0, −n).
5 Oui car J(x1 , x2 ) = (x1 − 500)2 + x22 − 255000.
Exercice 3
Exercice
Soit A une matrice symétrique à coefficients réels .
1 Montrer que si A ∈ Mn (R), symétrique et définie positive alors il existe
une constante α > 0 vérifiant :
hx , Ax i ≥ αkx k2 , ∀x ∈ Rn .
où h., .i est le produit scalaire de Rn et k.k la norme euclidienne

associée.
2 Soit H ∈ Mn (R), symétrique et définie positive. En déduire que la
fonction quadratique
1
f (x ) = hx , Hx i + hx , bi + c
2
est coércive.
Corrigé 3
1) A est une matrice symétrique, donc il existe une base orthonormé

(vi )i=1,2,...,n , formée de vecteurs propres de A.
Comme la matrice A est définie positive, les valeurs propres (λ)i=1,2,...,n
associées, sont strictement positives.
Soit x = ni=1 xi vi , nous avons
P
n X
X n
hx , Ax i = λi xi xj hui , uj i
i=1 j=1
Xn
= λi xi2
i=1
≥ λmin kx k2 . (α = λmin >0)
Corrigé 3
2) H est une matrice symétrique et définie positive, alors il existe une

constante α = λmin >0 telle que :
hx , Hx i ≥ αkx k2 , ∀x ∈ Rn .
et d’après l’inégalité de Cauchy-Schwarz (ICS), on a
−kx kkbk ≤ hx , bi ≤ kx kkbk,
alors
λmin kbk c

2
f (x ) ≥ kx k − + −→ +∞ (kx k −→ +∞) .
2 kx k kx k2
Donc f est coercive.

Minimisation Sans Contraintes

Transféré par

Droits d'auteur :

Formats disponibles

Minimisation Sans Contraintes

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Minimisation Sans Contraintes

Transféré par

Droits d'auteur :

Formats disponibles

Minimisation sans contraintes

UHBC. Uni de Chlef.

Soit f : Rn → R une fonction continûment différentiable.

2 On dit que x ∗ est un minimum global strict de f sur S si

3 On dit que x ∗ est un minimum local strict de f sur S, s’il existe

4 On dit que x ∗ est un minimum local strict de f sur S, s’il existe

Figure – Exemples de minima et de maxima locaux et globaux

Figure – Infinité de minima et de maxima globaux

Figure – Pas de maximum global- Infinité de minima et de maxima locaux

Figure – Graphe de x 7−→ x 2 , x ∗ = 0 est un minimum global

Figure – Maximum au point P

Figure – Minimum au point P

max {f (x ), x ∈ S} = − min {−f (x ), x ∈ S}

Donnons la preuve pour un maximum global : c’est exactement la même

max {f (x ), x ∈ S} = − min {−f (x ), x ∈ S}

Donnons la preuve pour un maximum global : c’est exactement la même

Soit x ∗ un minimum local. Raisonnons par absurde et supposons que x ∗

On peut donc choisir un λ suffisamment petit dans ]0, 1[ tel que

Soit x ∗ un minimum local. Raisonnons par absurde et supposons que x ∗

On peut donc choisir un λ suffisamment petit dans ]0, 1[ tel que

Résultats d’existence et d’unicité

On considère le problème d’optimisation

Avant d’étudier les propriétés de la solution (ou des solutions) de ce

Résultats d’existence et d’unicité

On considère le problème d’optimisation

Avant d’étudier les propriétés de la solution (ou des solutions) de ce

Résultats d’existence et d’unicité

On considère le problème d’optimisation

Avant d’étudier les propriétés de la solution (ou des solutions) de ce

Existence : Compacité du domaine

Rappelons que si S = Rn , le problème

est dit problème d’optimisation sans contraintes.

Rappelons que si S = Rn , le problème

est dit problème d’optimisation sans contraintes.

Rappelons que si S = Rn , le problème

est dit problème d’optimisation sans contraintes.

Definition (Fonction Coercive)

Figure – Exemples de fonction coercives

Figure – Exemples de fonction non coercives

4 Soit A une matrice carrée d’ordre n symétrique, définie positive et b un

Une application coercive a un minimum

1 Prouver la coércivité et la convexité stricte de f .

1 On a f (x , y ) = k(x , y )k2 , alors lim f (x , y ) = +∞, d’ou la

donc (0, 0) est une solution minimum global et f (0, 0) = 0 la valeur

1 Non, car lim x 2 = −∞ quand x −→ −∞.

où h., .i est le produit scalaire de Rn et k.k la norme euclidienne

1) A est une matrice symétrique, donc il existe une base orthonormé

2) H est une matrice symétrique et définie positive, alors il existe une

et d’après l’inégalité de Cauchy-Schwarz (ICS), on a

−kx kkbk ≤ hx , bi ≤ kx kkbk,

Donc f est coercive.

Vous aimerez peut-être aussi