Cours 

: Optimisation.

Université de Med Boudiaf M’sila Année Universitaire 2016/2017

Faculté des Technologies Option : Fabrication et Construction
Département de Génie Mécanique Master 1ère Année

Chapitre 2 : Optimisation non linéaire sans contraintes

2.1 Introduction :

Soit un domaine D ⊆ Rn et une fonction f : D → R de n variables. Dans un problème de

minimisation, on cherche un point x ∈ D qui minimise la valeur de f (x) sur D. On écrit :
min f (x) ( x ∈ D )
La fonction f est appelée la fonction objectif.

En optimisation sans contraintes, on considère D = Rn . On cherche donc à résoudre

min f (x). x∈Rn

L’étude des problèmes d’optimisation sans contraintes trouve des applications dans la
résolution des systèmes non linéaires. Une grande classe d’algorithmes que nous allons
considérer dans la résolution du problème d’optimisation sans contraintes, ils ont la forme
générale suivante :
x0 étant donnée, calculer xk+1 = xk + αkdk;

Ou, le vecteur dk s’appelle la direction de descente,

αk le pas de la méthode à la k-iéme itération.

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

f(xk+1) ≤ f(xk);

qui assure la décroissance suffisante de la fonction objectif f. De tels algorithmes sont souvent
appelés méthodes de descente. La différence essentielle entre ces algorithmes réside dans le choix
de la direction de descente dk. Cette direction étant choisie et nous sommes plus où moins ramenés
à un problème unidimensionnel pour la détermination de αk: Pour s’approcher de la solution
optimale du problème (P) (dans le cas général, c’est un point en lequel ont lieu peut être avec une
certaine précision les conditions nécessaires d’optimalité de f), on se déplace naturellement à partir
du point xk dans la direction de la décroissance de la fonction f.
L’optimisation sans contraintes a les propriétés suivantes :

 toutes les méthodes nécessitent un point de départ x0 ;

 les méthodes déterministes converges vers le minimum local le plus proche ;
 plus vous saurez sur la fonction (gradient, hessien) plus la minimisation sera efficace.

2.2 Quelques rappelles :

1
 Cours  : Optimisation.

Nous allons ici rappeler brièvement les définitions de quelques notions importantes
auxquelles nous ferons appel par la suite ainsi que quelques propriétés.
2.2.1 Dérivée partielle

2.2.2 Gradient

Exemple 1 :

Calculer le gradient de la fonction f :

2.2.3 Matrice Hessien

Exemple 2 :

Calculer la matrice Hessien de la fonction f :

2
 Cours  : Optimisation.

2.2.4 Ensembles et fonctions convexes

Propriétée :

2.2.5 Points critiques : maximums, minimums

Dans un ensemble ordonné, le plus grand élément (ou le plus petit) d’une partie de cet
ensemble est un extremum maximum (ou minimum) s’il est supérieur (ou inferieur) à tous les
autres éléments de la partie. Ce groupe d’éléments sont connus sous le nom de points critiques
ou points extremum définis sur un domaine d’étude D (espace topologique).

f(a) est un maximum global si ∀x ∈ D f (x) ≤ f (a)

f(a) est un minimum global si∀x ∈ D f (x) ≥ f (a)

f(a) est un maximum local (ou relatif) s’il existe un voisinage V de a tel que ∀x ∈V , f (x)
≤ f (a)

f(a) est un minimum local (ou relatif) s’il existe un voisinage V de a tel que ∀x ∈V , f (x)
≥ f (a)

3
 Cours  : Optimisation.

Figure1 : Points extrêmes (maximums et minimums locaux et globaux) sur une fonction

Pour trouver les maximums et les minimums d’une fonction, on utilise le calcul différentiel, et là
ou la dérivée de la fonction s’annule, on trouve soit un maximum ou un minimum. Un minimum
local est facile à trouver, mais il est difficile de trouver un minimum absolu.

Pour trouver le type de point critique, on utilise les deuxièmes dérivées évaluées dans le point
d’étude. Pour le cas d’une fonction à une variable f(x),
si f’’(a)>0, on trouve un minimum local en ce point,
si f’’(a)<0 on trouve un maximum local

2.3 Conditions nécessaires

Etant donné un vecteur x*,nous souhaiterions être capables de déterminer si ce vecteur est un
minimum local ou global de la fonction f. La propriété de différentiabilité continue de f fournit une
première manière de caractériser une solution optimale. Enonçons tout d’abord un théorème, sur
lequel s’appuiera le corollaire suivant pour établir une première condition nécessaire d’optimalité :

Théorème :

Le théorème

4
 Cours  : Optimisation.

2.4 Conditions suffisantes

Les conditions données précédemment sont nécessaire (si f n’est pas convexe), 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 continuellement différentiable.

Théorème ( condition suffisante du second ordre)

2.5 Méthodes itératives d’optimisation sans contraintes

Nous considérons ici les méthodes permettant de résoudre un problème d’optimisation sans
Contraintes (appelées aussi parfois méthodes d’optimisation directe),soit le problème

Il existe plusieurs méthodes :

1. Méthodes locales
2. Méthodes de recherche unidimensionnelle
3. Méthodes du gradient
4. Méthodes des directions conjuguées
5. Méthode de Newton
6. Méthodes quasi-Newton

Dans ce qui suit, nous allons présenter quelques méthodes par algorithmes permettant de
calculer (de manière approchée) la ou les solutions du problème (P) de départ. Bien entendu,
nous ne pouvons pas être exhaustifs ; nous présentons les méthodes “de base” les plus
classiques. Toutefois, la plupart de ces algorithmes exploitent les conditions d’optimalité dont
on a vu qu’elles permettaient (au mieux) de déterminer des minima locaux.

2.5.1 Définition d’un algorithme :

Un algorithme est défini par une application A de Rn dans Rn permettant la génération d’une suite
d’éléments de Rn par la formule :

2.5.2 Définition convergence d’un algorithme :

 On dit que l’algorithme A converge si la suite (xk)k ε N engendrée par l’algorithme converge vers une
limite x*.

5
 Cours  : Optimisation.

Il est bien entendu très important d’assurer la convergence d’un algorithme via les hypothèses ad-
hoc, mais la vitesse de convergence et la complexité sont aussi des facteurs à prendre en compte
lors de l’utilisation (ou de la génération) d’un algorithme ; on a en effet “intérêt » à ce que la
méthode soit la plus rapide possible tout en restant précise et stable. Un critère de mesure de la
vitesse (ou taux) de convergence est l’évolution de l’erreur commise

Méthodes de recherche unidirectionnelle

1. La méthode analytique :
Théorème 1:(Condition suffisante de minimalité locale)
Soit f :R → R une fonction C². Si x* ϵR vérifie les conditions :
f’(x*) = 0
f’’(x*) >0
Alors, f(x*) est un minimum local strict de f.

Théorème 2:(Condition suffisante de maximalité locale)

Soit f :R → R une fonction C². Si x* ϵR vérifie les conditions :
f’(x*) = 0
f’’(x*) <0
Alors, f(x*) est un maximum local strict de f.

Théorème 3:(Condition suffisante de maximalité locale)

Soit f :R → R une fonction C². Si x* ϵR vérifie les conditions :
f’(x*) = 0
f’’(x*) =0
Alors, x*est un point critique de f.

6
 Cours  : Optimisation.

Figure 1: Exemples de problème d’optimisation.

Exemple1  :
Soit la fonction
f(x) =x²
Trouver l’optimum de la fonction f.
f’(x)= 2x =0, x*=0
f’’(x)= 2 > 0
Donc f(0) est un minimum de la fonction f.

Exemple2  :
Soit la fonction
f(x) =x3
Trouver l’optimum de la fonction f.
f’(x)= 3x² =0, x*=0
f’’(x)= 6x et f’’(x*) = 0 . Le point x* n’est pas minimum local ni maximum local.
Dans ce cas f’’(x) <0 pour x<x* et f’’(x)>0 pour x>x*.

Exemple3  :
Soit la fonction
f(x) =x4
Trouver l’optimum de la fonction f.
f’(x)= 4x3 =0, x*=0
f’’(x)= 12x2 , f’’(x*) = 0
Dans ce cas, x* est un minimum local de la fonction f(x), f’(x) < 0 pour x < x* et f’(x) > 0 pour x >
x*

2. La méthode du second ordre (méthode de Newton) :

Il est possible d'utiliser la méthode de Newton pour rechercher un minimiseur. Le principe est de
calculer une approximation p de f autour d'un point x k par son développement de Taylor du second
ordre :

On calcule alors un nouveau point, xk+1,qui minimise p soit:

D’un point de vue pratique, cette méthode souffre de nombreux inconvénients :

 La méthode peut diverger si le point de départ est trop éloigné de la solution,

7
 Cours  : Optimisation.

 la méthode n’est pas définie si f’’(xk)=0,

 la méthode peut converger indifféremment vers un minimum, un maximum ou un poit selle.

Exemple  :
Soit la fonction
f(x) = 2sinx – x²/10 avec x0 =2.5

La première dérivée de la fonction f est :

La deuxième dérivée de la fonction f est :

Suivant la méthode de Newton le point xi+1 s’écrit comme suit :

La solution de la fonction f est x = 1.469.

3. La méthode du premier ordre (Dichotomie) :

On cherche à trouver un minimum local x* avec une précision donnée par la réduction itérative
de l’intervalle de recherche : dichotomie ( c’est une optimisation exacte). Le principe de dichotomie
repose sur la version suivante du théorème des valeurs intermédiaires :
Théorème 1.
Soit f : [a, b] → R une fonction continue sur un segment.
Si f (a)· f (b) ≤ 0, alors il existe l ∈ [a, b] tel que f (l) = 0
La condition f(a)·f(b) ≤ 0 signifie que f(a)et f(b) sont de signes opposés (ou que l’un des deux est
nul). L’hypothèse de continuité est essentielle.

On part d’une fonction f : [a, b] → R continue, avec a < b, et f (a)· f (b) ≤0.
Voici la première étape de la construction : on regarde le signe de la valeur de la fonction f
appliquée au point milieu a+b/ 2 .
• Si f (a)· f ( a+b 2 ) ≤0, alors il existe c ∈ [a, a+b 2 ] tel que f (c) = 0.
• Si f (a)· f ( a+b 2 ) > 0, cela implique que f ( a+b 2 )· f (b) ≤0, et alors il existe c ∈ [ a+b 2 , b]
tel que f (c) = 0

8
 Cours  : Optimisation.

Nous avons obtenu un intervalle de longueur moitié dans lequel l’équation (f (x) = 0) admet une
solution. On itère alors le procédé pour diviser de nouveau l’intervalle en deux. Voici le processus
complet :
• Au rang 0 :
On pose a0 = a, b0 = b. Il existe une solution x0 de l’équation (f (x) = 0) dans l’intervalle [a0 , b0 ].
• Au rang 1 :
 Si f (a0 )x f ( (a0+b0)/2 ) ≤ 0, alors on pose a1 = a0 et b1 = (a0+b0 )/2 ,
 sinon on pose a1 = (a0+b0)/2 et b1 = b.
 Dans les deux cas, il existe une solution x 1 de l’équation (f (x) = 0) dans l’intervalle [a 1 ,
b1 ].
• ..
• Au rang n :
supposons construit un intervalle [an , bn ], de longueur (b−a )/2n , et contenant une solution xn de
l’équation (f (x) = 0). Alors :
 Si f (an )· f ( (an+bn)/ 2 ) ≤0, alors on pose an+1 = an et bn+1 = (an+bn)/ 2 ,
 sinon on pose an+1 = (an+bn)/2 et bn+1 = bn .
 Dans les deux cas, il existe une solution xn+1 de l’équation (f (x) = 0) dans l’intervalle [an+1
, bn+1 ].
À chaque étape on a
an ≤xn ≤bn
On arrête le processus dès que bn − an = (b−a )/2n est inférieur à la précision souhaitée.

Exemple  :
Soit la fonction f définie par f (x) = x 2 − 10, c’est une fonction continue sur R qui s’annule en ±
√10. De plus √10 est l’unique solution positive de l’équation (f (x) = 0). Nous pouvons
restreindre la fonction f à l’intervalle [3,4].
En d’autre termes f (3) 60 et f (4) >0, donc l’équation (f (x) = 0) admet une solution dans
l’intervalle [3, 4] d’après le théorème des valeurs intermédiaires, et par unicité c’est √ 10, donc
√10 ∈ [3, 4].

9
 Cours  : Optimisation.

Voici les toutes premières étapes :

1. On pose a0 = 3 et b0 = 4, on a bien f (a0 ) 60 et f (b0 ) >0. On calcule a0+b0 2 = 3,5 puis f
( a0+b0 2 ) : f (3,5) = 3, 52 − 10 = 2, 25 >0. Donc p 10 est dans l’intervalle [3; 3, 5] et on pose a1
= a0 = 3 et b1 = a0+b0 2 = 3, 5.
2. On sait donc que f (a1 ) 60 et f (b1 ) >0.
On calcule
f ( a1+b1 2 ) = f (3,25) = 0,5625 >0,
on pose a2 = 3 et b2 = 3, 25. 3.
On calcule
f ( a2+b2 2 ) = f (3,125) = −0,23. . . 60.
Comme f (b2 ) >0 alors cette fois f s’annule sur le second intervalle [ a2+b2 2 , b2 ] et on pose
a3 = a2+b2 2 = 3, 125 et b3 = b2 = 3, 25.
À ce stade, on a prouvé : 3, 125 6 ≤ 10 63, 25.
Voici la suite des étapes : a0 = 3 b0 = 4
a1 = 3 b1 = 3, 5
a2 = 3 b2 = 3, 25
a3 = 3, 125 b3 = 3, 25
a4 = 3, 125 b4 = 3, 1875
a5 = 3, 15625 b5 = 3, 1875
a6 = 3, 15625 b6 = 3, 171875
a7 = 3, 15625 b7 = 3, 164062 .
a8 = 3, 16015 . . . b8 = 3, 164062 . . .

Donc en 8 étapes on obtient l’encadrement : 3, 160 6 p 10 63, 165 En particulier, on vient

d’obtenir les deux premières décimales : √ 10 = 3, 16 .

4. La méthode de la section d’or :

La méthode du nombre d’or est plus générale et plus simple à mettre en œuvre.

La Méthode du nombre d’or commence par le positionnement des points comme illustré sur cette
figure .

10
 Cours  : Optimisation.

Exemple  :
Minimisation de f(x) = - x cos( x ) avec 0 ≤ x ≤2/ π

Méthodes du gradient
La méthode (ou algorithme) du Gradient fait partie d’une classe plus grande de méthodes
numériques appelées méthodes de descente. Cette méthode est la plus simple à mettre en
œuvre pour trouver un minimum local sur une fonction. Comme son nom l'indique, on utilise
le gradient en un point donné de courbe pour donner la direction de la descente. La distance
entre le point xk et le point xk+1 est calculé en fonction de la valeur du gradient d k et d'un pas
déterminé à l'avance ρ.
xk+1 = xk + ρ gk

Elle consiste à minimiser une fonction J. Pour cela on se donne un point de départ arbitraire xo.
Pour construire l’itéré suivant x1 il faut penser qu’on veut se rapprocher du minimum de J; on veut
donc que J(x1) <J(xo).
On cherche alors x1 sous la forme :

x1 = xo + ρ1d1

Avec :
d1 est un vecteur non nul de Rn
ρ1 un réel strictement positif.

11
 Cours  : Optimisation.

En pratique donc, on cherche d1 et ρ1 pour que J(xo+ρ1d1) <J(xo). On ne peut pas toujours trouver
d1. Quand d1 existe on dit que c’est une direction de descente et ρ 1 est le pas de descente. La
direction et le pas de descente peuvent être fixé ou changer à chaque itération. Le schéma général
d’une méthode de descente est le suivant :

Une idée naturelle pour trouver une direction de descente est de faire un développement de Taylor
(formel) à l’ordre 2 de la fonction J entre deux itérés xk et xk+1 = xk + ρk dk :

- Le gradient de la fonction J Indique la direction avec le plus grand taux de décroissance de

f au point

12
 Cours  : Optimisation.

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. Nous donnons ci-dessous un critère de convergence.

On utilise le plus souvent la méthode du gradient à pas constant (ρ k = ρ= constant). Toutefois, on

peut faire varier le pas à chaque itération : on obtient alors la méthode du gradient à pas variable.
La méthode du gradient `a pas optimal propose un choix du pas qui rend la fonction cout minimale
le long de la direction de descente choisie. Plus précisément, l’´étape 2 devient :

Exemple 1( à pas constant)

Le problème est de trouver la valeur de x qui minimise E(x).
Dans cette exemple, on connaît l'expression analytique de la fonction E : E(x) = (x-1)(x-2)(x-3)
(x-5) = (x2 -3x +2)(x2 -8x +15)
= x4 -11x3 +41x² -61x +30

On connaît aussi sa dérivée:

E'(x) = 4x3 - 33x2 + 82x – 61

Pour trouver analytiquement le minimum de la fonction E, il faut trouver les racines de l'équation
E'(x) = 0, donc trouver les racines d'un polynôme de degré 3, ce qui est « difficile ». Donc on va
utiliser la DG.
La DG consiste à construire une suite de valeurs xi (avec x0 fixé au hasard) de manière itérative:

xi+1 = xi – η E'(xi)

si x0 = 4,5 et η = 0.01,

13
 Cours  : Optimisation.

x1= x0- η E'(x0)

Exemple 2( à pas variable)

Soit la fonction à deux variables suivante :
f(x,y) = 4x² -4xy +2y²
Déterminer la solution optimale en utilisant la méthode du gradient à pas variable si x0(2,3)

 La première itération :
On a :
∇f(x0,y0) = t (8x0 −4y0,−4x0 + 4y0)
∇f(x(0)) = t (4,4)
x(0) −ρ∇f(x(0))= t(2,3)−ρ t(4,4) = t(2−4ρ,3−4ρ)
Ainsi
f(x(0) −ρ∇f(x(0)))=4(2−4ρ)2 −4(2−4ρ)(3−4ρ) + 2(3−4ρ)2 =10−32ρ + 32ρ²
Cette dernière fonction est un trinôme du second degré, qui est minimale en ρ = 1/2.
On trouve ainsi
x(1) = t(0,1)

 La deuxième itération :

∇f(x(0)) = t (−4,4)
d’où x(1) −ρ∇f(x(1))= t(0,1)−ρ t(−4,4) = t(4ρ,1−4ρ)
Ainsi f(x(1) −ρ∇f(x(1)))=4(4ρ)2 −4(4ρ)(1−4ρ) + 2(1−4ρ)2 =2−32ρ + 160ρ2
Cette dernière fonction est un trinôme du second degré, qui est minimale en ρ = 1/10. On trouve
ainsi
x(2) = t(2/5,3/5)

 La troisième itération :
on a ∇f(x(2)) =
t(4/5,4/5)
d’où x(2) −ρ∇f(x(2))=
t(2/5,3/5)−ρ t(4/5,4/5)=t(2/5 −4ρ /5, 3 5 −4ρ/5)
Ainsi f(x(2) −ρ∇f(x(2)))=4(2/5 −
4ρ/5)2 −4(2/5 −4ρ/5)(3/5 −4ρ/5) + 2(3/5 −4ρ/5)2=2/5 −32/25ρ +32/25ρ²
Cette dernière fonction est un trinôme du second degré, qui est minimale en ρ = 1/2. On trouve
ainsi
x(3) =t(0, 1/5)

Valeurs de f(x(k)) L’algorithme minimise bien la fonctionnelle f ; on a en effet :

f(x(0))=10
f(x(1))=2
f(x(2))= 2/5
f(x(3))= 2/25

14