Chapitre 2 Optimisation Unidimentionnelle

Chapter 2
Optimisation unidimentionnelle
2.1 Définitions
Définition 1: Un programme non-linéaire à une variable réelle se présente sous la forme :
𝑚𝑖𝑛 𝑓(𝑥)
(PSC) { ; où 𝑓 : IR → IR. Ce problème est dit sans contrainte.
𝑥 ∈ 𝐼𝑅
Il sera avec contraintes :
min 𝑓(𝑥)
(PC) { 𝑠. 𝑐 ; K  IR.
𝑥∈𝐾
Example:
min 𝑓(𝑥)
𝑠. 𝑐
{ ; si K= [a,b].
𝑥≥𝑎
𝑥≤𝑏
Nous tenterons de répondre aux questions suivantes :
1) Existe-t-il une solution (locale ou globale) ? si oui a-t-on l’unicité ?
2) Comment la caractériser ? (conditions d’optimalité).
3) Comment la calculer ? avec quel type d’algorithme ?
Définition 2 :
i) Une fonction 𝑓 admet un minimum local en x*, s’il existe un
Voisinage de x*, V(x*) tel que : 𝑓(x*) ≤ 𝑓(x) xKV(x*) min.
avec V(x*) = {xIR / |x – x*|  }. local
ii) Un minimum global sur un intervalle (borné ou non-borné) A min.
𝑓 admet un minimum global sur K en x* si 𝑓(x*) ≤ 𝑓(x) xK. global
iii) 𝑓 admet un minimum strict en x* si 𝑓(x*)  𝑓(x), xx*, xKV(x*). B
Remarque : un minimum global correspond au plus petit des minimums 
locaux dans le cas où K = IR. a1 b1 a2 b2

K
2.2 Condition suffisante d’existence d’un minimum.
Il existe principalement deux théorèmes :
1) Cas où l’ensemble des contraintes K est fermé et borné.
2) Cas où l’ensemble des contraintes K est fermé mais non-borné.

2.2.1 Cas où l’ensemble K des contraintes est fermé et borné.

Théorème 1: (Wieistrass)
Si 𝑓 est continue sur un intervalle fermé et borné (compact) alors, elle admet sur cet intervalle un minimum
global et un maximum global.

2.2.2 Cas où l’ensemble K est fermé et non-borné (éventuellement K = IR).

Definition 3 :
Une application 𝑓 : IR → IR est coercive sur IR si lim 𝑓(𝑥) = +.
|𝑥|→+∞
Eviter le minimum non atteint car il se trouve à l’infini.
1
Exemple : lim 𝑥 = 0 sur IR+ .
𝑥→+∞
Proposition : 𝑓 : IR → IR une application et 𝑔 : IR → IR vérifiant 𝑓(x) ≥ 𝑔(|x|) avec lim 𝑔(𝑡) = +, alors
𝑡 →+∞
𝑓est coercive sur IR.
Chapitre 2 Optimisation Unidimentionnelle

Théorème 2 :
Soient K un ensemble fermé et non-borné, 𝑓 : K → IR une application continue et coercive sur K, alors 𝑓 admet
un minimum global sur K.

2.3 Condition nécessaire d’optimalité.

Théorème 3 : C.P.O (non suffisante)
Soit 𝑓C1(I), I ouvert. Si x* est un optimum local alors 𝑓′(x*) = 0.
Théorème 4 :
I intervalle ouvert et 𝑓 : I → IR de classe C2(I). Si x*I vérifiant : 𝑓′(x*) = 0 et 𝑓′′(x*)  0 alors x* est un
minimum local de 𝑓 (voir §1.6.2).
Théorème 5 :
Si 𝑓 est convexe sur I alors,
x* est un minimum local  x* est un minimum global.
Commentaire :
Le minimum local est global sur I, c’est une condition suffisante (convexité) mais aucunement nécessaire (voir
figure page 1). Si en plus I est fermé et borné, le maximum de 𝑓 est l’une des bornes de I.
Si x* est un minimum local strict ou 𝑓est strictement convexe alors, x* est un minimum global unique.

2.4 Résolution analytique :

min 𝑓(𝑥)
Soit à résoudre le problème { 𝑠. 𝑐 ; K est un ensemble fermé et borné.
𝑥 ∈ [𝑎, 𝑏]
 On calcule 𝑓(a), et 𝑓(b) car le bord (frontière) de K = [a,b] est K = {a,b}.
 On calcule 𝑓(x) pour xI, telle que 𝑓′(x) = 0 sur l’intervalle (l’intérieur) où 𝑓 est dérivable ou bien 𝑓′(x)
n’existe pas, puis,
 Comparer les valeurs 𝑓(a), 𝑓(b) et 𝑓(x).
La méthode analytique est inefficace lorsque la recherche des racines de 𝑓′(x) = 0 est difficile. Il faut alors
chercher numériquement les racines de 𝑓′(x) = 0.
Exemples :
𝑚𝑖𝑛 𝑓(𝑥) 𝑚𝑖𝑛 𝑓(𝑥)
1) Soit 𝑓(x) = x4. Déterminer : i) { ; puis ii) { .
𝑥 ∈ 𝐼𝑅 𝑥 ∈ [−1,3]

i) 𝑓 est dérivable sur IR. C.P.O : 𝑓′(x) = 0  x = 0, 𝑓′ change de signe au voisinage de x = 0, x* = 0 est un
minimum local. Puisque 𝑓′′(x) ≥ 0 xIR, 𝑓 est convexe sur IR. Alors x* = 0 est un minimum global
sur IR.
ii) 𝑓 admet un minimum global au point x* = 0 sur [-1,3], comme f est convexe, 𝑓(-1) = 1 et 𝑓(-3) =81 sont
des maximums locaux et x* = 3 est un maximum global.
𝑚𝑖𝑛 𝑔(𝑥)
2) Soit 𝑔(x) = x2. Déterminer { ;
𝑥 ∈ [1,2]
𝑔(1) = 1, 𝑔(2) = 4. 𝑔′(x) = 2x  0 x]1,2[ (dans l’intérieur).
min 𝑔(𝑥) = min{𝑔(1), 𝑔(2)}= 𝑔(1) = 1.
𝑥∈[1,2]
x* = 1 solution optimale et la valeur optimale 𝑔(1) = 1.
𝑚𝑖𝑛 ℎ(𝑥)
3) ℎ(x) = cosx. Déterminer { ; la recherche des optimums de ℎ sur [2,10] est difficile, car la
𝑥 ∈ [2,10]
résolution de l’équation ℎ′(x) = cosx – xsinx = 0 est difficile. Il faut recourir aux méthodes itératives.
Chapitre 2 Optimisation Unidimentionnelle

2.5 Résolution itérative.

i) Méthodes utilisant seulement la fonction (pas de calcul de dérivée).
min 𝑓(𝑥)
Soit à chercher { 𝑠. 𝑐 ; où 𝑓 est donnée sur [a,b]. Le principe de la méthode consiste à trouver une suite
𝑥 ∈ [𝑎, 𝑏]
d’intervalles imbriqués qui contiennent la solution recherchée.
a1 b1

a1 b2
a2 b2 Intervalles imbriqués (example: dichotomie).
a2 b3
Pour éviter que les méthodes de recherche ne convergent vers des optimums locaux, on suppose que la fonction
est unimodale (c.-à-d. qu’elle possède un seul minimum) sur l’intervalle. Les fonctions convexes sont
unimodales pour la recherche de minimum.
ii) Méthodes utilisant le calcul des dérivées :
Les résolutions itératives permettent simplement la résolution de l’équation 𝑓′(x) = 0, c.-à-d. la recherche
d’un point critique. C’est la raison pour laquelle nous supposons l’unimodalité de la fonction.

2.6 Fonctions unimodales :

Définition 4 : Soit 𝑓 : IR → IR une fonction à minimiser sur l’intervalle [a,b]. f est unimodale dans l’intervalle
[a,b], s’il existe x*[a,b] minimisant 𝑓 et x1,x2[a,b] tel que x1 x2 alors :
x1  x2 ≤ x*  𝑓(x1)  𝑓(x2) 𝑓 est décroissante sur [a,x*] et
x* ≤ x1  x2  𝑓(x1)  𝑓(x2) 𝑓 est croissante sur [x*,b].

2.6.1 Unimodalité et recherche de minimum :

Lemme 1 : 𝑓 une fonction unimodale. Si 𝑓 admet un minimum local en x* alors x* est un minimum global.
Lemme 2 : 𝑓 : [a,b] → IR unimodale
,  tels que a      b alors,
Si 𝑓()  𝑓()  x* [a, ]
Si 𝑓()  𝑓()  x* [, b] a   b a   b
∗
𝑥 ∈ [𝑎, 𝜇]
Si 𝑓() = 𝑓()  { 𝑜𝑢
𝑥 ∗ ∈ [, 𝑏]
a   b a = b

2.6.2 Algorithmes de recherche de minimum :

𝑓 fonction unimodale sur l’intervalle [a,b].
er
1 algorithme : Méthode de la suite de Fibonacci.
𝐹0 = 1, 𝐹1 = 1 F0 F1 F2 F3 F4 F5
La suite de Fibonacci est définie par : { ;
𝐹𝑛+1 = 𝐹𝑛 + 𝐹𝑛−1 , 𝑛 ≥ 1 1 1 2 3 5 8
On se donne n le nombre total de fois où l’on évaluera 𝑓 en un point.
Initialisation: a1 = a , b1 = b , x*[a1, b1],
Itération k, x*[ak, bk]
𝐹
𝑘 = 𝑎𝑘 + 𝐹𝑛−1−𝑘 (𝑏𝑘 − 𝑎𝑘 )
𝑛+1−𝑘
{ 𝐹𝑛−𝑘
𝜇𝑘 = 𝑎 𝑘 + 𝐹 (𝑏𝑘 − 𝑎𝑘 )
𝑛+1−𝑘
Chapitre 2 Optimisation Unidimentionnelle

Tests :
𝑓(k)  𝑓(k)  ak+1 = ak et bk+1 = k , x*[ak, k] = [ak+1, bk+1]
𝑓(k)  𝑓(k)  ak+1 = k et bk+1 = bk , x*[k, bk] = [ak+1, bk+1]
𝑎𝑛−1 +𝑏𝑛−1
Itération n-1 : n-1 = n-1 = , x*[an-1, bn-1]
2
Pour une évaluation, on pose : n-1 = n-1 +  ,   0.
Test d’arrêt :
𝑛−1
𝐹𝑛−𝑖 1
𝑏𝑛 − 𝑎𝑛 = ∏ (𝑏 − 𝑎) = (𝑏 − 𝑎) ≤ 𝛼
𝐹𝑛+1−𝑖 𝐹𝑛
𝑖=1
1
𝑏𝑛 − 𝑎𝑛 = (𝑏 − 𝑎) + 𝜀 ≤ 𝛼 , 𝛼 𝑑𝑜𝑛𝑛é (𝛼 > 0)
{ 𝐹𝑛
ème
2 algorithme : Méthode de la section dorée.
Initialisation: a1 = a , b1 = b , x*[a1, b1],
Itération k, x*[ak, bk]
 = 𝑎𝑘 + (1 − )(𝑏𝑘 − 𝑎𝑘 )
{ 𝑘 ; ( = 0,618 et 1- = 0,382).
𝜇𝑘 = 𝑎 𝑘 +  (𝑏𝑘 − 𝑎𝑘 )
Tests :
𝑓(k)  𝑓(k)  ak+1 = ak et bk+1 = k , x*[ak, k] = [ak+1, bk+1]
𝑓(k)  𝑓(k)  ak+1 = k et bk+1 = bk , x*[k, bk] = [ak+1, bk+1]
𝑥 ∗ ∈ [𝑎𝑘 , 𝜇𝑘 ]
Si 𝑓(k) = 𝑓(k)  { 𝑜𝑢
𝑥 ∗ ∈ [𝑘 , 𝑏𝑘 ]
Test d’arrêt :
bn − an = n-1 (b – a) ≤  ,  donné (  0)

3ème algorithme : Méthode de dichotomie (sans la dérivée)

Initialisation: a1 = a , b1 = b , x*[a1, b1],
Itération k, x*[ak, bk]
𝑎𝑘 +𝑐𝑘 3ak +b𝑘 ak +bk ck +bk ak +3bk
dk = = ; ck = ; ek = = .
2 4 2 2 4
Tests:
𝑓(ck)  𝑓(ek)  ak+1 = ck et bk+1 = bk
𝑓(ck)  𝑓(dk)  ak+1 = ak et bk+1 = ck
Sinon : ak+1 = dk et bk+1 = ek
Test d’arrêt :
bn − an ≤  (  0).
Pour plus d’efficacité, on utilise un tableau de 5 points :

Itération k

xk ak dk ck ek bk
𝑓(xk) 𝑓(ak) 𝑓(dk) 𝑓(ck) 𝑓(ek) 𝑓(bk)
Chapitre 2 Optimisation Unidimentionnelle

Algorithme 4 : Méthode de Newton

Les points critiques satisfont à la condition nécessaire d’optimalité : C.P.O, 𝑓′(x) = 0
Les points critiques qui satisfont à la condition suffisante d’optimalité : C.S.O, 𝑓′′(x*)  0, x* est un minimum
local de𝑓.
Recherche des points critiques : les racines de 𝑓′(x) = 0.
Soit x0[a,b] qui ne satisfait pas aux conditions d’optimalité, on va produire une suite (xn) qui s’approche de
l’optimum x*.
Théorème de convergence globale de la méthode de Newton :
1) 𝑓C3([a,b])
2) 𝑓′(a). 𝑓′(b)  0 (i.e : ]a,b[ / 𝑓′() = 0)
3) 𝑓′′(x)  0 x[a,b] (𝑓′′ garde un signe constant)
4) 𝑓′′′(x)  0 x[a,b] (𝑓′′′ garde un signe constant)
f′ (c)
5) | |  b – a ou c est tel que : |𝑓 ′′ (𝑐)| = min{|𝑓 ′′ (𝑎)|,|𝑓 ′′ (𝑏)|}.
f′′ (c)
𝑥0 ∈ [𝑎, 𝑏]
Alors, le processus itératif ; { 𝑓 ′ (𝑥 ) , n ≥ 0 , converge x0[a,b].
𝑥𝑛+1 = 𝑥𝑛 − 𝑓′′ (𝑥𝑛 )
𝑛

On a : lim 𝑥𝑛 = x* =  , racine de 𝑓′(x) = 0.

𝑛→ ∞
Remarque : pour la converge locale, choisir x0[a,b] tel que : 𝑓′(x0).𝑓′′′(x0)  0.

Algorithme 5 : Méthode de dichotomie avec dérivée.

𝑓 ∈ 𝐶 1 ([𝑎, 𝑏])
Rappel : ′ }, alors :]a,b[ tel que 𝑓′() = 0.
𝑓 (𝑎). 𝑓 ′ (𝑏) < 0
1) Initialisation: a1 = a , b1 = b , x*[a1, b1].
ak +bk
2) Itération k : calcul de xk = puis 𝑓′(xk).
2
3) Tests :
𝑓′(ak). 𝑓′(xk)  0  x*[ak, xk],
Sinon : 𝑓′(bk). 𝑓′(xk)  0  x*[xk, bk].
4) Test d’arrêt :
b−a
|xn – x*| ≤ ≤ .
2n
b−a
Le nombre d’itérations N : N = ⌈ ⌉.
ε Ln2
Algorithme 6 : Méthode de bisection.
𝑓 est unimodale et dérivable sur [a,b].
1) Initialisation: a1 = a , b1 = b , x*[a1, b1].
2) Itération k : 𝑓′(ak)  0 et 𝑓′(bk)  0  x*[ak, bk],
ak +bk
Calcul de k : k = .
2
3) Tests :
𝑓′(k)  0  x*[ak, k] = [ak+1, bk+1]
𝑓′(k)  0  x*[k, bk] = [ak+1, bk+1]
ak +bk
𝑓′(k) = 0  x* = , solution optimale.
2
Chapitre 2 Optimisation Unidimentionnelle

2.6.3 Propriétés des différentes méthodes.

1/ Dans la méthode de Fibonacci, il suffit de calculer un seul point à chaque itération sauf à la première.
Calcul de k+1 et k+1 : cas 𝑓(k)  𝑓(k).
ak+1 = ak et bk+1 = k .
Fn−k−1 Fn−1−k
k+1 = ak+1 + (bk+1 – ak+1) = ak + (k – ak)
Fn+1−k−1 Fn−k
Fn−1−k Fn−k Fn−1−k
= ak + (ak + (bk – ak) – ak) = ak + (bk – ak)
Fn−k Fn+1−k Fn+1−k
= k
Conclusion : seulement 𝑓(k+1) doit être évalué à l’itération k+1. De la même manière pour le cas 𝑓(k)  𝑓(k),
seul 𝑓(k+1) doit être évalué à l’itération k+1.
2/ Même propriété pour la méthode de la section dorée.
Calcul de k+1 et k+1 dans le cas 𝑓(k)  𝑓(k)
ak+1 = ak et bk+1 = k .
k+1 = ak+1 +  (bk+1 – ak+1)  k+1 = ak +  (k – ak) = ak +  (ak +  (bk – ak) – ak)
= ak + 2 (bk – ak) = ak + (1 - ) (bk – ak) car 2 = 1 - ,
= k
Conclusion : seulement 𝑓(k+1) doit être évalué à l’itération k+1. Dans le cas 𝑓(k)  𝑓(k), seul 𝑓(k+1) doit
être évalué à l’itération k+1.
3/ Les différents cas de figures des tableaux de la méthode de dichotomie sans dérivée.

1er cas : 2éme cas: 3éme cas:

Itération k Itération k Itération k

xk ak* dk ck* ek bk xk ak dk* ck ek* bk xk ak dk ck* ek bk*

f(xk) f(ak) f(dk) f(ck) f(ek) f(bk) f(xk) f(ak) f(dk) f(ck) f(ek) f(bk) f(xk) f(ak) f(dk) f(ck) f(ek) f(bk)

f(ak)  f(dk)  f(ck)  f(ek)  f(bk) f(ak)  f(dk)  f(ck)  f(ek)  f(bk) f(ak)  f(dk)  f(ck)  f(ek)  f(bk)

alors : x*[ak, ck] = [ak+1, bk+1] alors : x*[dk, ek] = [ak+1, bk+1] alors : x*[ck, bk] = [ak+1, bk+1]

4éme cas: 5éme cas:

Itération k Itération k

xk ak dk ck ek* bk* xk ak dk ck* ek* bk

f(xk) f(ak) f(dk) f(ck) f(ek) f(bk) f(xk) f(ak) f(dk) f(ck) f(ek) f(bk)

f(ak)  f(dk)  f(ck)  f(ek)  f(bk) f(ak)  f(dk)  f(ck) = f(ek)  f(bk)
alors : x*[ek, bk] = [ak+1, bk+1] alors : x*[ck, ek] = [ak+1, bk+1].