0% ont trouvé ce document utile (0 vote)

72 vues46 pages

Chapitre 2

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

72 vues46 pages

Chapitre 2

Transféré par

جلولي غوتي

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Chapitre2 Algorithmes d’optimisation

MASTER PHYSIQUE - Toutes options confondues

Samir Kenouche - Département des Sciences de la Matière - UMKB
Module : Méthodes Mathématiques et Algorithmes pour la Physique
Résumé
Un processus d’optimisation consiste à choisir entre plusieurs solutions possibles, celle qui est la meilleure.
Il s’agit ainsi de minimiser ou de maximiser un critère sur l’ensemble de toutes les solutions admissibles. Nous
aborderons les algorithmes d’optimisation usuels à savoir : Newton, quasi-Newton, la famille des méthodes
de descente de gradient et les algorithmes génétiques. La programmation des algorithmes abordés dans ce
chapitre sera conduite au moyen de scripts Matlabr . Pendant les séances de cours, nous traiterons uniquement
des problèmes d’optimisation non contraints. La résolution de problèmes contraints se fera lors des séances
de travaux pratiques. La dernière section de ce chapitre est donnée à cet effet.

Table des matières

I Introduction 11
I-A Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
I-B Critères d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

II Algorithme de Newton 13
II-A Algorithme de quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

III Algorithmes de descente de gradient 18

III-A Méthode de gradient à pas fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
III-B Méthode de gradient à pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

III-C Méthode de gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

IV Algorithmes génétiques 30

V Travaux pratiques avec des fonctions Matlab prédéfinies 34

V-A Optimisation sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
V-B Optimisation avec contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Annexe A : Dérivée directionnelle 52

Annexe B : Codage binaire 54

I. Introduction

L Es algorithmes d’optimisation sans ou sous contraintes (unconstrained and constrained problem en

anglais), de fonctions mathématiques uni et multidimensionnelles, ont pour objectif de chercher un
vecteur X̂ tel que f (X̂) soit un extremum (minimum ou maximum) de la fonction en question. L’optimisation
s’apparente systématiquement à une minimisation car trouver le maximum d’une fonction f revient à minimiser
la fonction −f . Dans cette topologie, la fonction à optimiser est appelée fonction-objectif ou encore critère
d’optimisation. Ainsi, l’opération d’optimisation est formalisée selon l’écriture :

X̂ ∈ argminf (X) (1)

X∈Rn

S. Kenouche est docteur en Physique de l’Université des Sciences et Techniques de Montpellier et docteur en Chimie de
l’Université A. Mira de Béjaia.
page web personnelle : http://www.sites.univ-biskra.dz/kenouche
Version corrigée, améliorée et actualisée le 10.10.2020.
M. Samir KENOUCHE

Avec X̂ = (x̂1 , x̂2 , ..., x̂n )T sont les coordonnées du point critique. On fait appel aux algorithmes d’optimisa-

MASTER PHYSIQUE - Toutes options confondues

tion afin de résoudre des problèmes de différentes natures, comme par exemple, trouver les zéros de fonctions
non-linéaires, ajustement de données expérimentales selon le critère des moindres carrés linéaire et non-linéaire,
résolution de systèmes d’équations de plusieurs variables ... etc. En général, la recherche des extremums est
atteinte en procédant au calcul des dérivées premières (gradient de la fonction) et des dérivées secondes
(Hessien de la fonction). Toutefois, trouver un minimum global n’est pas toujours chose facile et il n’y a pas
d’algorithme d’optimisation parfait. En effet, pour résoudre un problème d’optimisation convenablement : (1)
il faut bien poser le problème (2) choisir le bon algorithme (3) savoir interpréter les résultats qui en découlent.

A. Convergence
n o
L’étude de la convergence d’une méthode numérique est atteinte à travers la suite des itérés X (k)
k∈N
générés par l’algorithme. Ce dernier est dit convergent si pour tout X (0) ∈ Rn nous avons :

lim k X (k) − X ∗ k= 0 (2)

k→+∞

Avec X ∗ ∈ Rn est la solution approchée, de la valeur exacte, déterminée avec une tolérance fixée préalablement.
La condition (2) garantit, à partir d’une certaine itération, la satisfaction du critère d’arrêt pour la tolérance
exigée. Nous rappelons que le taux de convergence (ou ”vitesse” de convergence) et la complexité du problème
traité rentrent en ligne de compte lors de l’utilisation d’un algorithme d’optimisation. La convergence ne
signifie pas systématiquement l’existence d’un optimum même local. Le schéma numérique adopté doit être
à la fois rapide et robuste. Ces deux derniers critères sont contrôlés par l’étude du taux de convergence qui
quantifie l’erreur commise à chaque itération, soit :

e(k) =k X (k) − X ∗ k tel que ∇f (X ∗ ) = 0 (3)

L’estimation de l’erreur servira, entre autre, à comparer le taux de convergence des différentes méthodes
numériques. En pratique, l’erreur est représentée graphiquement en traçant la norme de l’erreur, soit k e(k+1) k
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

en fonction de k e(k) k avec une échelle logarithmique. Ainsi, l’ordre noté p, de la méthode numérique s’obtient
à partir de :

k e(k+1) k≈ A k e(k) kp =⇒ log k e(k+1) k≈ p log k e(k) k + cste (4)

L’ordre, p, est quantifié via la pente de l’équation ci-dessus. Il en ressort les conclusions suivantes :

1) Si p = 1 =⇒ X (k) converge linéairement vers la solution approchée. Dans ce cas on gagne la même
quantité de précision à chaque itération. Il en résulte :

k X (k+1) − X ∗ k
lim = =τ avec 0 < τ < 1 (5)
k→+∞ k X (k) − X ∗ k
Elle est dite superlinéaire si τ = 0.
2) Si p = 2 =⇒ X (k) converge quadratiquement vers la solution approchée. Dans ce cas on gagne le double
de précision à chaque itération.
3) Si p = 3 =⇒ X (k) converge cubiquement vers la solution approchée. Dans ce cas on gagne le triple de
précision à chaque itération. Il en résulte :

k X (k+1) − X ∗ k
lim = =τ avec τ ≥ 0 (6)
k→+∞ k X (k) − X ∗ kp

Chapitre2 Algorithmes d’optimisation 12

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

D’un point de vue pratique et pour un k suffisamment élevé, la vitesse de convergence d’une méthode
itérative est évaluée ”empiriquement” au moyen de la relation :

k X (k+2) − X (k+1) k
Kp (X, k) = (7)
k X (k+1) − X (k) kp

Bien évidemment, nous visons à ce que la convergence de l’algorithme soit la plus élevée possible afin de
tendre vers la solution en un minimum d’itérations pour la tolérance exigée. La convergence quadratique est
plus rapide que celle superlinéaire. A son tour cette dernière, est plus rapide que la convergence linéaire. Tenant
compte de l’équation (7), il vient que plus Kp (X, k) tend vers zéro plus le taux de convergence de la méthode
est élevé.

B. Critères d’arrêt
Les méthodes numériques, dites locales, procèdent de façon itérative. Typiquement, étant donné une valeur
initiale, un nouvel itéré est mis à jour afin de converger vers un point stationnaire. Ce processus est réitéré
jusqu’à la satisfaction d’un ou plusieurs critères d’arrêt de l’algorithme. D’un point de vue purement théorique,
le schéma itératif est infini. En pratique, la suite d’approximations successives est tronquée dés que l’on
considère avoir atteint la précision requise. Étant donné une tolérance , les critères d’arrêt pouvant êtres
envisagés sont :

k X (k+1) − X (k) k < (8)

k ∇f (X (k) ) k < (9)

k f (X (k+1) ) − f (X (k) ) k
< (10)
k f (X (k) ) k
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Il est possible d’envisager également un quatrième critère, celui du nombre d’itérations dépassant un seuil
fixé préalablement. Il se peut que le critère (23) ne soit pas satisfait même si l’algorithme converge. Les erreurs
d’arrondis dues à l’accumulation des opérations arithmétiques peuvent êtres du même ordre de grandeur que le
gain de précision obtenu à l’itération en cours. Le critère (8) est recommandé, le schéma itératif est interrompu
lorsqu’il ne produit plus de gain significatif en terme de précision. En outre, dans certaines situations la
divergence d’un algorithme ne signifie pas forcément l’inexistence de la solution, il faudra juste adapter le
nombre d’itérations et/ou la tolérance considérés. D’un point de vue purement pratique, une combinaison de
ces critères est prise en compte.

II. Algorithme de Newton

Comme il a été signalé au début de ce chapitre, l’opération d’optimisation s’apparente systématiquement
à une minimisation, car trouver le maximum d’une fonction f revient à minimiser la fonction −f selon
l’équivalence :

Arg maxf (x) ⇔ Arg min(−f (x)) (11)

x x

Les deux opérations d’optimisation sont pleinement équivalentes. La méthode de Newton est efficiente,
notamment parce qu’elle prend en compte la courbure de la fonction-objectif à travers le calcul de sa seconde
dérivée. Cette méthode est praticable si à chaque itération, la dérivée seconde est définie ou la matrice hessienne
est définie positive pour le cas X (k) ∈ Rn . Soit f : Rn −→ R une fonction de classe C 2 . Le développement en
série de Taylor d’ordre deux (modèle quadratique) est une fonction PX (k) (X) : Rn −→ R, avec :
1
PX (k) (X) = f (X (k) ) + (X − X (k) )T ∇f (X (k) ) + (X − X (k) )T ∇2 f (X (k) ) (X − X (k) ) (12)
2!
Chapitre2 Algorithmes d’optimisation 13
M. Samir KENOUCHE

Avec, ∇2 f (X (k) ) est la matrice Hessienne de f en X = X (k) soit Hf (X (k) ) = ∇2 f (X (k) ). Posons U =

MASTER PHYSIQUE - Toutes options confondues

X − X (k) , il vient :
1 T 2
PX (k) (X + U ) = f (X (k) ) + U T ∇f (X (k) ) + U ∇ f (X (k) ) U (13)
2!

min{PX (k) (X + U )} ⇐⇒ ∇PX (k) (X + U ) = 0 (14)

Une condition suffisante d’optimalité :

∇PX (k) (X + U ) = ∇f (X (k) ) + ∇2 f (X (k) ) U = 0 (15)

∇f (X (k) )
∇f (X (k) ) = −U ∇2 f (X (k) ) ⇒ U = − (16)
∇2 f (X (k) )

∇f (X (k) )
X = X (k) − avec U = X − X (k) (17)
∇2 f (X (k) )

On calcule alors un nouveau point, X (k+1) , qui minimise PX (k) soit :

∇f (X (k) )
X (k+1) = X (k) − (18)
∇2 f (X (k) )
Ou bien avec une écriture équivalente :

X (k+1) = X (k) − Hf (X (k) )−1 f (X (k) ) (19)

Ci-dessous l’écriture algorithmique de la méthode de Newton
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Algorithm 1 Algorithme de Newton

Input : f (X) ∈ C 2 , X (0) ∈ Rn
k ←− 0

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Calcul du gradient Gk ←− −∇f (X (k) )

−1
3. Calcul de Hf Hk ←− [Hf (X (k) )]−1
4. Nouvelle itération X (k+1) ←− X (k) + Gk Hk
5. Mise à jour : k ←− k + 1
6. Fin

Appliquons le schéma numérique (19) à la fonction-objectif ci-dessous.

Chapitre2 Algorithmes d’optimisation 14

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Exercice ¶ + r
Soit la fonction-objectif de trois variables, f (X) tel que X ∈ R3 , suivante :

1 4 1
f (X) = x + x32 − x33 + 6 x21 + 3 x22 + 6 x1 x2 (20)
4 3 3
La tolérance vaut = 10−5 et pour l’évaluation numérique prendre X (0) = (−0.6637, 0.1758, 1.5778)T .

1) Trouver analytiquement l’optimum de la fonction-objectif.

2) Évaluer numériquement la fonction-objectif en utilisant l’algorithme de Newton.
3) Écrire un script Matlabr de l’algorithme de Newton permettant sa minimisation.

Les résolutions analytique et numérique seront menées pendant la séance de cours. Le script Matlabr est
donné ci-dessous

clear␣all␣;␣clc␣;␣close␣all␣;

%␣Samir␣KENOUCHE␣-␣LE␣08/08/2019
%␣ALGORITHME␣DE␣NEWTON

fx␣=␣@(x)␣(1/4)*x(3)ˆ4␣+␣x(2)ˆ3␣-␣(1/3)*x(3)ˆ3␣+␣6*x(1)ˆ2␣+␣...
␣␣␣␣3*x(2)ˆ2␣+␣6*x(1)*x(2)␣;

rng(1110,’twister’)␣␣;␣%␣INITIALISATION␣DU␣GENERATEUR␣DES␣NOMBRES␣ALEATOIRES
xinit␣=␣randn(1,3)’␣;␣␣%␣INITIALISATION␣ALEATOIRE

it␣=␣0␣;␣itmax␣=␣20␣;␣␣%␣NOMBRE␣D’ITERATIONS
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

err␣=␣10.ˆ(-5)␣;␣␣␣␣␣␣␣%␣TOLERANCE

while␣it␣<␣itmax

␣␣␣␣Hx(1,1)␣=␣12␣;␣Hx(1,2)␣=␣6␣;␣Hx(1,3)␣=␣0␣;
␣␣␣␣Hx(2,1)␣=␣6␣;␣Hx(2,2)␣=␣6*xinit(2)␣+␣6␣;␣Hx(2,3)␣=␣0␣;
␣␣␣␣Hx(3,1)␣=␣0␣;␣Hx(3,2)␣=␣0␣;␣Hx(3,3)␣=␣3*xinit(3)ˆ2␣-␣2*xinit(3)␣;

␣␣␣␣dfx␣=␣[12*xinit(1)␣+␣6*xinit(2)␣;␣...
␣␣␣␣␣␣␣␣␣3*xinit(2)ˆ2+␣6*xinit(1)␣+␣6*xinit(2)␣;␣xinit(3)ˆ3␣-␣xinit(3)ˆ2]␣;

␣␣␣␣xk␣=␣xinit␣-␣inv(Hx)*dfx␣␣;

␣␣␣␣␣␣␣␣␣if␣␣norm(inv(Hx)*dfx)␣<=␣err␣␣␣%␣TEST␣D’ARRET
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣solution␣=␣xk␣;␣␣␣␣␣␣␣␣␣␣%␣OPTIMUM␣OBTENU
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣f_min␣=␣fx(solution)␣;␣␣␣%␣MINIMUM␣DE␣LA␣FONCTION-OBJECTIF
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣iteration_max␣=␣it␣;␣␣␣␣␣%␣NOMBRE␣D’ITERATIONS␣PERMETTANT␣LA␣CV
␣␣␣␣␣␣␣␣␣␣break
␣␣␣␣␣␣␣␣␣end

␣␣␣␣xinit␣=␣xk␣;␣it␣=␣it␣+␣1␣;␣␣␣␣␣␣␣␣␣␣%␣MISE␣A␣JOUR
end

%%␣SOLUTION␣:␣X*␣=(0,␣0,␣1)␣EN␣04␣ITERATIONS

Chapitre2 Algorithmes d’optimisation 15

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Il est possible de voir la méthode de Newton comme un algorithme de descente de gradient à pas fixe valant
l’unité. La famille des algorithmes de descente de gradient fera l’objet des sections suivantes. Nonobstant, la
simplicité et la convergence quadratique de l’algorithme de Newton, ce dernier souffre d’un certain nombres
d’inconvénients : il peut diverger si le point initial est trop éloigné de la solution recherchée. En outre,
l’algorithme ne peut être utilisé si la fonction-objectif n’est pas deux fois dérivables. Dans certaines situations,
même si la dérivée seconde ou le Hessien pour la cas multidimensionnel existe, son calcul peut se révéler
fastidieux ou très laborieux ou encore impossible à atteindre.

Nota Bene: Toutes les méthodes numériques ont une structure d’une suite numérique. Ce qui les dis-
tinguent, c’est la formule du schéma numérique de la méthode en question. Toute suite de nombres réels (ou
de nombre complexe C) est convergente si et seulement si elle vérifie le critère de Cauchy.
n o
Définition d’une suite de Cauchy: Une suite X (k) est de Cauchy (ou vérifie le critère de
k∈N
Cauchy) si pour un rang k ∈ N suffisamment grand nous avons :

lim k X (k) − X ∗ k = 0 (21)

k−→+∞

Ce critère s’énonce aussi,

∀ > 0, ∃ η tel que k>η (ou η()) ⇒ k X (k) − X ∗ k ≤

n o
Une façon de démontrer le théorème consiste à démontrer que X (k) est une suite de Cauchy 1 . Soit
k∈N
q ∈ [0 ; 1[ et ∀k ∈ N, nous avons :

k f (X (k) ) − f (X (k−1) ) k ≤ q k X (k) − X (k−1) k

⇒ k X (k+1) − X (k) k ≤ q k X (k) − X (k−1) k (22)

Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

D’un autre côté, nous pouvons écrire

k X (k) − X (k−1) k ≤ q k X (k−1) − X (k−2) k (23)

En substituant (23) dans (24) nous obtenons :

⇒ k X (k+1) − X (k) k ≤ q 2 k X (k−1) − X (k−2) k (24)

En procédant par récurrence nous démontrons 2 :

⇒ k X (k+1) − X (k) k ≤ q k k X (1) − X (0) k (25)

n o
Avec q ∈ [0 , 1[, la distance k X (k+1) − X (k) k tend vers zéro pour k assez grand alors X (k) est une
k∈N
suite de Cauchy donc elle est convergente.

1. Rappelons que toute suite convergente dans R est une suite de Cauchy.
qk
2. Pour les puristes, nous opterons plutôt pour k X (k+1) − X (k) k ≤ k X (1) − X (0) k
1−q

Chapitre2 Algorithmes d’optimisation 16

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

A. Algorithme de quasi-Newton
L’intérêt d’utiliser l’algorithme de quasi-Newton par rapport à celui de Newton tient aux éléments suivants :
(1) le Hessien n’est pas calculé explicitement, ce dernier exige un temps de calcul souvent très élevé (2) la
détermination de la direction de descente dk ne nécessite qu’une multiplication matrice-vecteur, sans se soucier
du calcul de gradient (3) les approximations du Hessien H (k+1) sont définies positives, garantissant ainsi que
les directions de recherche sont systématiquement descendantes. Le schéma numérique de Broyden-Fletcher-
Goldforb-Shanno, communément appelé BFGS est :

!
y T H (k) yk dk dTk H (k) yk dTk + dk ykT H (k)
H (k+1) = H (k) + 1 + k T − (26)
y dk ykT dk ykT dk
Avec,

yk = ∇f (X (k+1 ) − ∇f (X (k )
D’autres versions de cet algorithme existent aussi, nous citerons notamment la formule de Davidon-Fletcher-
Powell, communément appelée DFP. L’inconvénient des méthodes de quai-Newton est que l’on exploite pas
toute l’information portant sur la forme de la fonction-objectif. Par ailleurs, l’initialisation de H0 ∈ Rn×n
se fait très souvent avec la matrice identité I ∈ Rn×n . La pratique montre que ce choix semble donner des
résultats très probants. Ci-dessous, l’écriture algorithmique de la méthode de Quasi-Newton

Algorithm 2 Algorithme de Quasi-Newton

Input : f (X) ∈ C 1 , X (0) ∈ Rn , H0 = In×n
k ←− 0

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Calcul du gradient Gk ←− −∇f (X (k) )

3. Pas optimal λk ←− argmin(X (k) + λ Gk )
4. La descente dk ←− λk Gk H0
5. Nouvelle itération X (k+1) ←− X (k) + dk
6. Calcul intermédiaire yk ←− ∇f (X (k+1) ) − ∇f (X (k) )
!
y T H (k) yk dk dTk H (k) yk dTk + dk ykT H (k)
7. Approx. de la Hess. H (k+1)
←− H (k)
+ 1+ k T T
−
y dk y k dk ykT dk
8. Mise à jour : k ←− k + 1
9. Fin

Exercice · + r

Nous appliquerons cette méthode pour chercher le minimum de la fonction-objectif à deux dimensions
suivante :

1 2 7 2

 f (X) = x + y


2 2 (27)

(0)

Avec X = (7.5, 2.2)


La tolérance considérée est = 10−5 . Ci-dessous, le script Matlabr

Chapitre2 Algorithmes d’optimisation 17

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

close␣all␣;␣clc␣;␣clear␣all␣;

%␣Le␣12.08.2019␣-␣Samir␣KENOUCHE
%␣Algorithme␣de␣BFGS␣-␣quasi-Newton

n␣=␣2␣;␣Hinit␣=␣eye(n,n)␣;
fxy␣=␣@(x,y)␣x.ˆ2*(1/2)␣+␣y.ˆ2*(7/2)␣;␣dfx␣=␣@(x)␣x␣;␣dfy␣=␣@(y)␣7.*y␣;
it␣=␣0␣;␣itmax␣=␣10␣;␣tol␣=␣␣1e-5␣;␣xinit␣=␣[7␣;␣2]␣;

while␣it␣<␣itmax

␣␣␣d␣=␣-␣Hinit*[dfx(xinit(1))␣;␣dfy(xinit(2))]␣;
␣␣␣lambdak␣=␣-(xinit(1)*d(1)␣+␣7*xinit(2)*d(2))/(d(1).ˆ2␣+␣7*d(2).ˆ2)␣;

␣␣␣dk␣=␣lambdak*d␣;␣xk␣=␣xinit␣+␣dk␣;

␣␣␣if␣norm(dk)␣<␣tol
␣␣␣␣␣solution␣=␣xk␣␣␣;␣%␣VECTEUR␣SOLUTION
␣␣␣␣␣nbr_it␣=␣it␣;␣␣␣␣␣%␣NOMBRE␣D’ITERATION␣PERMETTANT␣LA␣CV
␣␣␣␣␣␣␣break
␣␣␣end

␣␣␣yk␣=␣[dfx(xk(1))␣;␣dfy(xk(2))]␣-␣[dfx(xinit(1))␣;␣dfy(xinit(2))]␣;
␣␣␣Hk␣=␣Hinit␣+␣(1␣+␣(yk’*Hinit*yk)/(yk’*dk))*(dk*dk’)/(yk’*dk)␣-␣...
␣␣␣␣␣␣␣(Hinit*yk*dk’␣+␣dk*yk’*Hinit)/(yk’*dk)␣;

␣␣␣Hinit␣=␣Hk␣;␣xinit␣=␣xk␣;␣␣it␣=␣it␣+␣1␣;␣%␣MISE␣A␣JOUR
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

end

solution

Les méthodes de Newton et de quasi-Newton peuvent rencontrer des problèmes tels que le calcul du Hessien
soit trop complexe ou qu’il n’existe pas. La nécessité d’appliquer une inversion matricielle à chaque itération,
ceci peut se révéler rédhibitoire pour des problèmes d’optimisation mobilisant beaucoup de variables. Ces
méthodes peuvent donc devenir impraticables. Une alternative consiste à utiliser la famille des algorithmes de
descente de gradient. Ces méthodes ne requièrent pas le calcul explicite ou l’approximation du Hessien. Elles
n’exigent pas de facto le stockage du Hessien (Rn×n ), mais seulement un ou quelques vecteurs (∈ Rn ).

III. Algorithmes de descente de gradient

Un algorithme de descente de gradient est mis en œuvre suivant les modes de choix des directions de descente
successives, ensuite par l’amplitude du pas effectué dans la direction choisie. La famille des algorithmes de
descente de gradient est à la base des processus d’optimisation de problèmes plus au moins complexes. Le
terme descente vient du fait que cet algorithme cherche l’extremum suivant une direction opposée à celle du
gradient de la fonction-objectif. Le pas de descente λk est soit constant (méthode de gradient à pas fixe) ou
bien incrémenté selon les méthodes de Wolfe, de gradient à pas optimal et de gradient conjugué. Typiquement,
le pas de descente est obtenu au moyen d’une recherche linéaire vérifiant : f (x(k) + λk ∇f (x(k) )) < f (x(k) ).
Dans cette section, nous rappellerons succinctement la notion de la dérivée directionnelle. Cette étape est
importante afin de rendre compte du principe de fonctionnement des algorithmes de descente de gradient.
Plus de détails sur cette notion sont disponibles en annexe (A).

Chapitre2 Algorithmes d’optimisation 18

M. Samir KENOUCHE

→
−
Par définition, la dérivée directionnelle de f (x, y) dans la direction du vecteur unitaire d = a~i + b ~j au

MASTER PHYSIQUE - Toutes options confondues

point f (x0 , y0 ) est :

f (x0 + λ a, y0 + λ b) − f (x0 , y0 ) →
−
→ (x0 , y0 ) = lim
f−
d
= ∇f (x0 , y0 ) d (28)
λ→0 λ

→
−
Théorème : La dérivée directionnelle est maximale lorsque d a la même direction que ∇f (x0 , y0 ) de plus
le taux de variation maximal de f (x, y) en (x0 , y0 ) est ||∇f (x0 , y0 )||.
→
− →
−
Ce théorème peut être prouvé en considérant que f− → (x0 , y0 ) = ∇f (x0 , y0 ) d = ||∇f (x0 , y0 )|| || d || cos(θ) =
d
→
−
||∇f (x0 , y0 )|| cos(θ). Ainsi f−
→ (x0 , y0 ) est maximale si cos(θ) = ±1 autrement dit si la condition ∇f (x0 , y0 )// d
d
→
−
est satisfaite. Dans le cas où θ = π/2 ⇒ ∇f (x0 , y0 ) ⊥ d . Ce résultat indique que si je me déplace dans une
direction perpendiculaire au ∇f , le taux de variation de la fonction f (x, y) est nul.
→
− →
−
– Si les deux vecteurs ∇f et d ont la même direction et le même sens, dans ce cas le vecteur unitaire d
désigne une direction de croissance maximale de f (x, y).
→
− →
−
– Si les deux vecteurs ∇f et d ont la même direction et de sens opposé, dans ce cas le vecteur unitaire d
désigne une direction de décroissance maximale de f (x, y). Cette condition est prouvée selon :

→
−
∇f (x0 , y0 ) × d = ∇f (x0 , y0 ) × (−∇f (x0 , y0 ))
= −∇f (x0 , y0 ) × ∇f (x0 , y0 )
= − ||∇(x0 , y0 )||2 >0
| {z }
| {z }
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

<0
→
−
⇒ d = −∇f est une direction de descente
Théorème: Soit f une fonction C 1 sur un ouvert D de R2 et P0 un point d eD tel que f (P0 ) = k. Nous
supposons que le ∇f est non nul au point P0 = (x0 , y0 ). La tangente en P0 à la courbe d’équation f (x, y) = c
a comme équation :

∇f (x0 , y0 ) · P~0 P = 0 (29)

Ou de façon équivalente :
∂f (x0 , y0 ) ∂f (x0 , y0 )
(x − x0 ) + (y − y0 ) = 0 (30)
∂x ∂y
Démonstration: Nous travaillerons sur la courbe de niveau f (x, y) = 0. Le point P0 (x0 , y0 ) peut se
déplacer sur la courbe de niveau de sorte que des coordonnées changent en fonction du temps. Cela nous permet
d’écrire P0 (x0 + a t, y0 + b t). Ainsi nous obtenons l’équation paramétrique (de paramètre t) :

f (x0 + a t, y0 + b t) = f (x(t), y(t)) = 0 (31)

En dérivant (31) nous obtenons :
df ∂f dx(t) ∂f dy(t)
= + =0 (32)
dt ∂x dt ∂y dt
Au point P0 (x0 , y0 ) correspondant à t = 0, il vient :
df (x0 , y0 ) ∂f (x0 , y0 ) dx(t) ∂f (x0 , y0 ) dy(t)
= + =0 (33)
dt ∂x dt ∂y dt
Chapitre2 Algorithmes d’optimisation 19
M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

df (x0 , y0 ) ∂f (x0 , y0 ) ∂f (x0 , y0 )
⇒ = a+ b=0 (34)
dt ∂x ∂y
df (x0 , y0 )
⇒ = ∇f (x0 , y0 ) · (a, b) (35)
dt
Avec a et b sont les coordonnées de la pente de l’équation tangente au point (x0 , y0 ). Nous concluons ainsi
que le gradient de f est toujours orthogonal (produit scalaire (35) est nul) aux courbes de niveau.

A. Méthode de gradient à pas fixe

L’idée de base de cette approche consiste à chercher une suite {xk }k∈N ∈ Rn dont le successeur de xk doit
satisfaire la condition :

f (xk+1 ) < f (xk ) (36)

Afin d’établir cette suite, on exploitera la dérivée directionnelle définie précédemment. Considérons la figure
ci-dessous :

x
o xk

o xk+1

y
0
dk
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Figure 1: Dérivée directionnelle dans la direction d~k .

Compte tenu de l’Eq. (92) (voir l’annexe), à une dimension on obtient :

f (xk+1 ) − f (xk ) f (xk + λ a) − f (xk )
→ (xk ) = lim
f−
d
⇒ f−
→ (xk ) = lim
d
(37)
λ→0 λ λ→0 λ

Comme précédemment, nous avons

−
x− −−→ → − −−−−→ →
−
avec λ ∈ R∗+
k xk+1 //dk ⇒ xk xk+1 = λ dk

D’un autre côté,

−
x− −−→ −−−−→ −−→ −−−−→ −−→ −−−−→
k xk+1 = Oxk+1 − Oxk ⇒ Oxk+1 = Oxk + xk xk+1

−−−−→ −−→ →
−
⇒ Oxk+1 = Oxk + λ dk (38)

D’où le schéma numérique de l’algorithme de descente de gradient :

x(k+1) = x(k) + λ dk = x(k) − λ∇f (x(k) ), λ>0 (39)

Chapitre2 Algorithmes d’optimisation 20

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Ainsi,

f (xk+1 ) < f (xk ) ⇔ f (x(k) − λ∇f (x(k) ) < f (xk ) (40)

Avec, dk = −∇f (x(k) ) est la direction de plus forte descente de f au point xk . Le paramètre λ est le
pas de descente qui est constant dans cette version de l’algorithme. Notons que la vitesse de convergence
de cet algorithme est proportionnelle à la valeur de λ. Une valeur initiale pour incrémenter l’algorithme est
λ = 0.01. Cette méthode est itérative, elle a donc besoin bien évidemment d’une valeur initiale pour démarrer
l’incrémentation de l’algorithme. Ci-dessous, l’écriture algorithmique de la méthode de gradient à pas fixe.

Algorithm 3 Algorithme de descente de gradient à pas fixe

Input : f (X) ∈ C 1 , X (0) ∈ Rn , λ ∈ R∗+
k ←− 0

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Direction de descente dk ←− −∇f (X (k) )

3. Nouvelle itération X (k+1) ←− X (k) + λk dk
4. Mise à jour : k ←− k + 1
5. Fin

Afin d’illustrer le principe de fonctionnement de cet algorithme, nous chercherons à optimiser une fonction-
objectif d’une seule variable.

Exercice ¸ + r
Cherchons la minimisation de la fonction-objectif :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

f (x) = 4 x2 + ex avec ∇f (x) = 8 x + ex

Cette fonction est au moins de classe C 1 sur R. Exécutons le schéma numérique de l’algorithme de descente
de gradient à pas fixe pour x0 = 1.50000, λ = 0.02 et = 10−3 , soit :
h (k)
i
x(k+1) = x(k) + λ dk = x(k) − λ∇f (x(k) ) = x(k) − λ 8 x(k) + ex
Commençons par appliquer le schéma numérique ci-dessus,

x(1) = 1.500000 − 0.02 ∇f (1.500000) = 1.170366

x(2) = 1.170366 − 0.02 ∇f (1.170366) = 0.918644
x(3) = 0.918644 − 0.02 ∇f (0.918644) = 0.721543
x(4) = 0.721543 − 0.02 ∇f (0.721543) = 0.564944
x(5) = 0.564944 − 0.02 ∇f (0.564944) = 0.439366
.. .. .. ..
. . . .
.. .. .. ..
. . . .
x(30) = −0.10695 − 0.02 ∇f (−0.10695) = −0.10781
Le test d’arrêt |x(k+1) − x(k) | < est positif au bout de la 30ème itération, soit :

|x(30) − x(29) | = 8.5000 × 10−4 <

Chapitre2 Algorithmes d’optimisation 21

M. Samir KENOUCHE

L’algorithme converge vers la solution x∗ = −0.10781 correspondant au minimum de la fonction-objectif

MASTER PHYSIQUE - Toutes options confondues

considérée.

Exercice ¹ + r
Soit la fonction-objectif ci-dessous :

( √
f (x) = cos(2 x) x2 + 1
(41)
Avec x0 = −2, x ∈ [−4, 0]
1) Écrire un script Matlabr de l’algorithme de descente de gradient permettant la minimisation de la
fonction-objectif.

Script Matlabr

clear␣all␣;␣close␣all␣;␣clc␣;
%␣Le␣05.08.2019␣-␣Samir␣KENOUCHE
%%%%%%%%%%%%%%%%%%%%%%%␣DSCENTE␣DE␣GRADIENT␣A␣PAS␣FIXE␣%%%%%%%%%%%%%%%%%%%%%%
syms␣x
fun␣=␣cos(2*x)␣+␣sqrt(xˆ2␣+␣1)␣;␣dfun␣=␣diff(fun,x)␣;
xi␣=␣-4:0.004:␣0␣;␣fx␣=␣subs(fun,␣x,␣xi)␣;␣dfx␣=␣subs(dfun,␣x,␣xi)␣;

xinit␣=␣-3␣;␣lambda␣=␣0.1/2␣;␣itmax␣=␣100␣;␣it␣=␣0␣;␣echelle␣=␣0.5␣;
tol␣=␣␣1e-3␣;␣plot(xi,fx,’LineWidth’,1)␣;␣hold␣on␣;

␣while␣it␣<␣itmax

␣␣␣␣J␣=␣subs(dfun,␣x,␣xinit)␣;
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

␣␣␣␣xn␣=␣xinit␣-␣lambda*J␣;␣xinit␣=␣xn␣;

␣␣␣␣it␣=␣it␣+␣1;

␣␣␣␣fxn␣=␣subs(fun,␣x,␣xn)␣;␣dfxn␣=␣subs(dfun␣,␣x,␣xn)␣;

␣␣␣␣if␣abs(lambda*J)␣<␣tol
␣␣␣␣␣␣␣␣␣sol␣=␣xn
␣␣␣␣␣␣␣␣␣break
␣␣␣␣end

␣␣␣␣dk␣=␣-␣dfxn␣;␣%␣DIRECTION␣DE␣DESCENTE
␣␣␣␣plot(xn,␣fxn,’xr’,’MarkerSize’,7)␣;␣hold␣on␣;
␣␣␣␣plot(xn,␣fxn,’or’,’MarkerSize’,7)␣;␣hold␣on␣;
␣␣␣quiver(xn,fxn,dk,0,␣echelle,’Color’,␣’k’,’LineWidth’,1)␣;␣hold␣on;
␣end
h␣=␣gca␣;
str(1)␣=␣{’Plot␣of␣the␣function␣:’};
str(2)␣=␣{’$$y␣=␣\cos(2\,x)␣+␣\sqrt{xˆ2␣+␣1}$$’};
str(3)␣=␣{’With␣the␣minimum:’};
str(4)␣=␣{[’$$x_{min}␣=␣$$’,␣num2str(sol)]};
set(gcf,’CurrentAxes’,h)␣;

text(’Interpreter’,’latex’,␣’String’,str,’Position’,[-3.9␣1.5],’FontSize’,12)

Chapitre2 Algorithmes d’optimisation 22

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Figure 2: Minimisation avec la descente de gradient à pas fixe

Le minimum renvoyé par ce script est : sol = -1.3668. L’inconvénient de cette méthode est qu’elle réclame
une valeur initiale très proche de la solution approchée. Dans le cas contraire, l’algorithme ne convergera pas
vers le véritable minimum de la fonction. Nous faisons remarquer que le critère d’arrêt k X (k+1) − X (k) k est
totalement équivalent à celui de k λk ∇f X (k) k.

B. Méthode de gradient à pas optimal

L’inconvénient d’utiliser un pas de descente constant (λ = cst) est que l’algorithme converge très lentement
si le pas est trop petit. De plus, l’algorithme peut devenir instable dans le cas où le pas est trop grand. On
comprend donc que le choix optimal de la valeur de λ devient délicat dans ce cas de figure. Il faudra par
conséquent ajuster la valeur de λ à chaque itération. Cette procédure est appelée recherche en ligne (line
search) 3 . Nous appliquerons à cet effet la méthode de gradient à pas optimal. L’idée de base de cette méthode
est de chercher λk diminuant d’avantage f (x(k) ) dans la direction dk = −∇f (x(k) ), selon :

0
ϕ(λk ) = argmin f (x(k) − λ ∇f (x(k) )) ⇔ ϕ (λk ) = 0 ⇔ ϕ(λopt ) ≤ ϕ(λk ) (42)
λ>0

Il convient de noter, qu’en toute rigueur le pas de descente n’est pas λ mais λ dk . L’opération d’optimisation
du pas de descente permet de répondre à la question : quelle distance doit-on parcourir ? Cherchons la valeur
du pas λk minimisant une fonction-objectif f (X (k+1) ), avec X ∈ Rn , dans la direction de descente dk . Nous
avons :

f (X (k+1) ) = f (X (k) + λk dk ) (43)

Dans ce chapitre, il est question que de fonctions quadratiques. Ainsi la fonction f (X) peut se mettre sous
la forme :
1 T
f (X) = X A X − bT X ⇒ ∇f (X) = A X − b = g (44)
2
3. Notons qu’il existe d’autres méthodes de recherche linéaire moins restrictives. Nous citerons les méthodes de Armijo, de
Goldstein et de Wolf. Ces méthodes autorisent n’ont pas un choix unique du pas optimal, mais un intervalle de valeurs.

Chapitre2 Algorithmes d’optimisation 23

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Avec A une matrice symétrique définie positive. Le schéma numérique de l’algorithme de descente de gradient
impose :

X (k+1) = X (k) − λk ∇f (X (k) ) (45)

Nous cherchons un pas optimal tel que :

λk = argmin f (X (k) − λ ∇f (X (k) )) (46)

λ≥0

Ainsi,

∂f (X (k+1) )
(λ = λk ) = 0 ⇔ ∇f (X (k+1) ) ∇f (X (k) ) = 0 (47)
∂λ
Tenant compte de (44) il vient

h iT
∇f (X (k+1) ) ∇f (X (k) ) = A X (k+1) − b ∇f (X (k) ) = 0
h h i iT
= A X (k) − λk ∇f (X (k) ) − b ∇f (X (k) ) = 0
h iT
= A X (k) − b − A λk ∇f (X (k) ) ∇f (X (k) ) = 0
= (A X (k) − b)T ∇f (X (k) ) − λk ∇f (X (k) )T A ∇f (X (k) ) = 0

(A X (k) − b)T ∇f (X (k) ) ∇f (X (k) )T ∇f (X (k) )

⇒ λk = T
= (48)
(k)
∇f (X ) A ∇f (X ) (k) ∇f (X (k) )T A ∇f (X (k) )
La formule générale de la méthode de descente de gradient à pas optimal dans la direction dk est :

dTk gk
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

X (k+1) = X (k) + dk avec gk = ∇f (X (k) ) et dTk = ∇f (X (k) )T (49)

dTk A dk

Algorithm 4 Algorithme de descente de gradient à pas optimal

Input : f (X) ∈ C 1 , X (0) ∈ Rn
k ←− 0

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Direction de descente dk ←− −∇f (X (k) )

3. Trouver un pas tel que λk ←− min f (X (k) − λ ∇f (X (k) ))
λk ≥0
4. Nouvelle itération X (k+1) ←− X (k) + λk dk
5. Mise à jour : k ←− k + 1
6. Fin

Exercice º + r
Illustrons la méthode de gradient à pas optimal pour la fonction-objectif de deux variables suivante :

f (X) = 4 (x2 + y 2 ) − 2 x y − 6 (x + y) avec X = (x, y)T (50)

Le gradient s’écrit :
!
8x − 2y − 6
∇f (X) = (51)
−2 x + 8 y − 6

Chapitre2 Algorithmes d’optimisation 24

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Et le Hessien,
!
2 8 −2
H(f ) = ∇ f (X) = (52)
−2 8
La Matrice Hessienne est symétrique définie positive. La fonction f (X) est strictement convexe et unimodale.
Désormais notons dk = (d1 , d2 )T la direction de gradient, soit :
! !
d1 8x − 2y − 6
∇f (X) = = (53)
d2 −2 x + 8 y − 6
Nous avons aussi :

ϕ(X + λk ∇f (X)) = 4 (x + λk d1 )2 + 4 (y + λk d2 )2 − 2 (x + λk d1 ) (y + λk d2 ) − 6 (x + λk d1 + y + λk d2 )
calculons la dérivée :

0
ϕ (λk ) = 0
0
ϕ (λk ) = 8 (x + λk d1 ) d1 + 8 (y + λk d2 ) d2 − 2 (x + λk d1 ) d2 − 2 (y + λk d2 ) d1 − 6 (d1 + d2 ) = 0
6 (d1 + d2 ) + 2 (x d2 + y d1 ) − 8 (x d1 + y d2 )
=⇒ λk =
8 (d21 + d22 ) − 4 d1 d2
Il en résulte le schéma numérique de l’algorithme de descente de gradient à pas optimal :

6 (d1 + d2 ) + 2 (x d2 + y d1 ) − 8 (x d1 + y d2 )
(x(k+1) , y (k+1) ) = (x(k) , y (k) )− (8 x(k) − 2 y (k) − 6, −2 x(k) + 8 y (k) − 6)
8 (d21 + d22 ) − 4 d1 d2 | {z } | {z }
d1 d2
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Script Matlabr :

clc␣;␣clear␣all␣;␣close␣all␣;

%␣Le␣08/08/2019␣-␣Samir␣KENOUCHE
%␣METHODE␣DE␣GRADIENT␣A␣PAS␣OPTIMAL

␣fxy␣=␣@(x,y)␣4*(x.ˆ2␣+␣y.ˆ2)␣-␣2*x*y␣-␣6*(x+y)␣;␣␣itmax␣=␣5␣;␣it␣=␣0␣;
␣dfx␣=␣@(x,y)␣8*x␣-␣2*y␣-␣6␣;␣dfy␣=␣@(x,y)␣-2*x␣+␣8*y␣-␣6␣;

while␣it␣<␣itmax

␣␣␣xinit␣=␣[.3␣.4]␣;
␣␣␣df␣=␣-␣[dfx(xinit(1),xinit(2))␣dfy(xinit(1),xinit(2))]␣;

␣␣␣lambdak␣=␣(6*(df(1)␣+␣df(2))␣+␣2*(xinit(1)*df(2)␣+␣xinit(2)*df(1))␣-␣...
␣␣␣␣␣␣␣␣␣8*(xinit(1)*df(1)+␣xinit(2)*df(2)))/(8*(df(1).ˆ2␣+␣df(2).ˆ2)␣-␣...
␣␣␣␣␣␣␣␣␣4*df(1)*df(2))␣;␣␣␣␣␣␣%␣PAS␣OPTIMAL␣EXACTE

␣␣␣xk␣=␣xinit␣+␣lambdak*df␣␣␣␣␣%␣NOUVEL␣ITERE

␣␣␣xinit␣=␣xk␣;␣it␣=␣it␣+␣1␣;␣␣%␣MISE␣A␣JOUR

end

Chapitre2 Algorithmes d’optimisation 25

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

f_min␣=␣fxy(xk(1),xk(2))␣;␣%␣MIN␣DE␣LA␣FONCTION-OBJECTIF

%%%%%%%%%%%%%%%%%%%%%%%%%%%%␣AFFICHAGE␣GRAPHIQUE␣%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x␣=␣-10:0.3:␣8␣;␣y␣=␣-10:0.3:8␣;␣[xgrid,␣ygrid]␣=␣meshgrid(x,y)␣;
zgrid␣=␣fxy(xgrid,ygrid)␣;␣figure(’color’,[1␣1␣1])␣;
contourf(xgrid,ygrid,zgrid)␣;␣xlabel(’x’)␣;␣ylabel(’y’)␣;␣hold␣on␣;
plot(xk(1),xk(2),’rx’)␣;␣plot(xk(1),xk(2),’ro’)␣;

Exercice » + r
Nous appliquerons cette méthode pour chercher le minimum de la fonction :

1 2 7 2

f (x, y) =
x + y

2 2 (54)
 Avec x = (7.5, 2.2)
0

Avec un raisonnement analogue que précédemment, nous obtenons l’expression analytique du pas optimal

−(x(k) d1 + 7 y (k) d2 )
λk = (55)
d21 + 7 d22

Il en résulte le schéma numérique :

(x(k) d1 + 7 y (k) d2 ) (k)

(x(k+1) , y (k+1) ) = (x(k) , y (k) ) − 2 2 (x , 7 y (k) ) (56)
d1 + 7 d2 |{z} | {z }
d1 d2
r
Script Matlab :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

clear␣all␣;␣close␣all␣;␣clc␣;

%␣Le␣09/08/2019␣-␣Samir␣KENOUCHE
%␣GRADIENT␣A␣PAS␣OPTIMAL

fxy␣=␣@(x,y)␣x.ˆ2*(1/2)␣+␣y.ˆ2*(7/2)␣;␣dfx␣=␣@(x)␣x␣;␣dfy␣=␣@(y)␣7.*y␣;
it␣=␣0␣;␣itmax␣=␣40␣;␣echelle␣=␣0.6␣;␣␣tol␣=␣␣1e-6␣;␣xinit␣=␣[7.5␣2.2]␣;

x␣=␣-2:0.2:␣8␣;␣y␣=␣-6:0.2:6␣;␣[xgrid,␣ygrid]␣=␣meshgrid(x,y)␣;
zgrid␣=␣␣fxy(xgrid,␣ygrid)␣;␣figure(’color’,[1␣1␣1])␣;
contourf(xgrid,ygrid,zgrid)␣;␣hold␣on␣;␣xlabel(’x’)␣;␣ylabel(’y’)␣;

␣while␣it␣<␣itmax

␣␣␣dk␣=␣␣-␣[dfx(xinit(1))␣dfy(xinit(2))]␣;
␣␣␣lambdak␣=␣-(xinit(1)*dk(1)␣+␣7*xinit(2)*dk(2))/(dk(1).ˆ2␣+␣7*dk(2).ˆ2)␣;

␣␣␣xk␣=␣xinit␣+␣lambdak*dk␣;

␣␣%%%%%%%%%%%%%%%%%%%%%%%%%%%%%␣TEST␣D’ARRET␣%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
␣␣␣␣␣␣if␣norm(lambdak*dk)␣<=␣tol
␣␣␣␣␣␣␣␣␣solution␣=␣xk␣;␣␣␣␣␣␣␣␣␣␣␣%␣SOLUTION␣OBTENUE
␣␣␣␣␣␣␣␣␣nbre_it␣=␣it␣;␣␣␣␣␣␣␣␣␣␣␣␣%␣NOMBRE␣D’ITERATION␣PERMETTANT␣LA␣CV

Chapitre2 Algorithmes d’optimisation 26

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣␣␣␣break
␣␣␣␣␣␣end
␣␣%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

␣␣plot(xk(1),␣xk(2),’xw’,’MarkerSize’,7)␣;␣hold␣on␣;
␣␣plot(xk(1),␣xk(2),’ow’,’MarkerSize’,7)␣;␣hold␣on␣;
␣␣quiver(xk(1),␣xk(2),␣-dfx(xk(1)),-␣dfy(xk(2)),...
␣␣␣␣␣␣echelle,’Color’,␣’r’,␣’LineWidth’,1)␣;

␣␣xinit␣=␣xk␣;␣␣it␣=␣it␣+␣1␣;␣␣␣␣␣␣%␣MISE␣A␣JOUR
␣end

␣f_min␣=␣fxy(solution(1),solution(2))␣;␣%␣MIN␣DE␣LA␣FONCTION-OBJECTIF

L’affichage graphique généré par ce script est :

0
y
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

−2

−4

−6
−2 −1 0 1 2 3 4 5 6 7 8
x

Figure 3: Minimisation par la méthode de la descente de gradient à pas optimal

→
−
Dans le direction dk , à l’itération x(k+1) l’algorithme calcule le minimum de ∇f (x(k+1) ), soit

ϕ(λ) = dk ∇f (x(k+1) ) (57)

La recherche du minimum impose de calculer la dérivée :
0
ϕ (λ) = 0 ⇔ < dk |∇f (x(k+1) ) >= 0 ⇔ − < ∇f (x(k) )|∇f (x(k+1) ) >= 0 (58)
Ainsi, le produit scalaire des deux gradients est nul, par conséquent les directions de descente successives
calculées par l’algorithme sont orthogonales. Ceci explique pourquoi la convergence suit une trajectoire en
zigzag à angles droits. L’avantage d’optimiser le pas de descente de gradient rend l’algorithme moins sensible,
par rapport au pas fixe, au choix de la valeur initiale. La vitesse de convergence est améliorée également.
Néanmoins, cette méthode peut se révéler moins efficace dans le cas où la fonction est caractérisée par des
pentes peu marquées. L’autre inconvénient tient au fait qu’il est difficile, voir impossible, de trouver une
expression analytique λk = f (xk ) pour des fonctions plus complexes. Chaque méthode est adaptée à un
problème spécifique.

Chapitre2 Algorithmes d’optimisation 27

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

C. Méthode de gradient conjugué
Cette méthode procède par la détermination successive de directions de recherche et de longueurs de descente.
Contrairement aux autres méthodes de descente qui rendent compte uniquement du comportement local de la
fonction-objectif qui se matérialise par une structure en zigzag. La méthodes du gradient conjugué permet de
s’affranchir de cette structure en déterminant des directions de recherche différentes des directions précédentes.

Définition: Soit une matrice A ∈ Rn×n définie positive. Deux directions dk+1 et dk de Rn sont conjuguées
par rapport à la matrice A si

dTk+1 A dk = 0 ∀k (59)
En outre, si A = I (matrice identité), les directions conjuguées dk+1 et dk sont orthogonales. Nous cherchons
ainsi dk+1 dans le plan formé par les directions orthogonales dk et gk+1 soit :

dk+1 = −gk+1 + βk dk βk ∈ R et gk+1 , dk ∈ Rn (60)

Cherchons l’expression de βk en combinant les relations (59) et (60), soit :

(−gk+1 + βk dk )T A dk = 0 ⇒ −gk+1
T
A dk + βk dTk A dk = 0

T
gk+1 A dk
⇒ βk = T
(61)
dk A dk
L’expression du pas optimal a déjà été déterminée précédemment (48) :

∇f (X (k) )T ∇f (X (k) )
λk = (62)
∇f (X (k) )T A ∇f (X (k) )
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Algorithm 5 Algorithme de descente de gradient conjugué

Input : f (X) ∈ C 1 , X (0) ∈ Rn , ∇f (X (0) ) ∈ Rn , A tel que ∀M ∈ Rn , M 6= 0 : M T A M > 0
k ←− 0

1. Tant que critère d’arrêt n’est pas vérifié faire :

dTk dk
2. Pas optimal λk =
dTk A dk
3. Nouvelle itération X (k+1) ←− X (k) + λk dk
g T A dk
4. Calcul du scalaire βk = k+1
dTk A dk
5. Direction conjuguée dk+1 = −gk+1 + βk dk
6. Mise à jour : k ←− k + 1
7. Fin
Soulignons qu’il existe plusieurs méthodes pour calculer le paramètre βk . Dans l’équation (61), nous avons
utilisé la méthode de Fletcher-Reeves. Nous citerons également les méthodes de Polack-Ribière et de Hestenes-
Stiefel.

Exercice ¼ + r
Illustrons la méthode de gradient conjugué pour la fonction-objectif de deux variables suivante :

y2
f (X) = 5 x2 + − 3 (x + y) avec X = (x, y)T (63)
2
Chapitre2 Algorithmes d’optimisation 28
M. Samir KENOUCHE

Prendre comme vecteur initial X (0) = [−2, 1]T et une tolérance = 10−4 . Le critère d’arrêt est :

MASTER PHYSIQUE - Toutes options confondues

f (X (k+1) ) − f (X (k) )
k k<
f (X (k) )
Script Matlabr :

clc␣;␣clear␣all␣;␣close␣all␣;

%␣Le␣10/08/2019␣-␣Samir␣KENOUCHE
%␣METHODE␣DU␣GRADIENT␣CONJUGUE

␣fxy␣=␣@(x,y)␣5*x.ˆ2␣+␣y.ˆ2*(1/2)␣-␣3*(x+y)␣;␣␣itmax␣=␣15␣;␣it␣=␣0;
␣dfx␣=␣@(x)␣10*x␣-␣3␣;␣dfy␣=␣@(y)␣y␣-␣3␣;␣tol␣=␣1e-04␣;

␣A␣=␣[10␣0␣;␣0␣1]␣;␣␣b␣=␣[3␣;␣3]␣;␣xinit␣=␣[-2␣;␣1]␣;
␣␣␣dkinit␣=␣␣-␣[dfx(xinit(1))␣;␣dfy(xinit(2))]␣;␣xtest␣=␣zeros(2,itmax);

while␣it␣<␣itmax

␣␣␣lambdak␣=␣(dkinit’*dkinit)/(dkinit’*A*dkinit)␣;

␣␣␣xmin␣=␣xinit␣+␣lambdak*dkinit␣;

␣␣␣if␣abs((fxy(xmin(1),␣xmin(2))␣-␣fxy(xinit(1),...
␣␣␣␣␣␣␣␣␣␣␣xinit(2)))/fxy(xinit(1),␣xinit(2)))␣<␣tol␣;

␣␣␣␣␣␣␣␣␣solution␣=␣xmin␣␣␣;␣%␣VECTEUR␣SOLUTION
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

␣␣␣␣␣␣␣␣␣nbr_it␣=␣it␣;␣␣␣␣␣␣␣%␣NOMBRE␣D’ITERATION␣PERMETTANT␣LA␣CV
␣␣␣␣␣␣␣break
␣␣␣end

␣␣␣betak␣=␣([dfx(xmin(1))␣;␣dfy(xmin(2))]’*A*dkinit)/(dkinit’*A*dkinit)␣␣;
␣␣␣dk␣=␣␣-␣[dfx(xmin(1))␣;␣dfy(xmin(2))]␣+␣betak*dkinit
␣␣␣xinit␣=␣xmin␣;␣dkinit␣=␣dk␣;␣it␣=␣it␣+␣1␣;␣%␣MISE␣A␣JOUR
end

f_min␣=␣fxy(solution(1),solution(2))␣;␣%␣MIN␣DE␣LA␣FONCTION-OBJECTIF

%%%%%%%%%%%%%%%%%%%%%%%%%%␣AFFICHAGE␣GRAPHIQUE␣%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x␣=␣-20:0.3:␣18␣;␣y␣=␣-20:0.3:18␣;␣[xgrid,␣ygrid]␣=␣meshgrid(x,y)␣;
zgrid␣=␣fxy(xgrid,ygrid)␣;␣figure(’color’,[1␣1␣1])␣;
contourf(xgrid,ygrid,zgrid)␣;␣␣xlabel(’x’)␣;␣ylabel(’y’)␣;␣hold␣on␣;
plot(solution(1),solution(2),’rx’)␣;␣plot(solution(1),solution(2),’ro’)␣;

%␣VERIFICATION␣:␣A␣*␣solution␣-␣b␣=␣0␣Avec␣XMIN␣=␣(0.30␣;␣3.0)
%␣ATTENTION␣AUX␣ERREURS␣D’ARRONDI

La méthode de gradient conjugué appliquée à une fonction-objectif d’ordre n converge au plus en n itérations.
Notons toutefois que les erreurs d’arrondi dans le calcul des directions conjuguées font que nous n’obtenons
pas toujours la solution exacte en n itérations. Cette méthode réclame un nombre d’itérations proportionnel

Chapitre2 Algorithmes d’optimisation 29

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

à cond(A). Contrairement aux autres méthodes de gradient, exigeant un nombre d’itérations proportionnel
à cond(A).

IV. Algorithmes génétiques

4
Cette classe d’algorithmes est dite évolutionniste, car fondée sur les mécanismes Darwiniens de la sélection
naturelle. Le fonctionnement de ces algorithmes est comme suit : partant d’une population initiale d’individus,
choisis aléatoirement, la performance relative de chaque individu est mesurée au moyen d’une fonction fitness.
Les valeurs de cette fonction sont classées selon un ordre décroissant. Nous créons ainsi une nouvelle population
qui a hérité du bagage génétique des meilleurs individus de la population initiale. Cette nouvelle population
est crée en se servant des opérations : sélection, croisement et mutation. Ce processus est réitéré jusqu’à la
sélection du meilleur individu, constituant la solution du problème d’optimisation.

Avant de décrire les différents mécanismes du fonctionnement de ces algorithmes, nous donnerons, chemin
faisant, quelques définitions élémentaires. Un individu I (ou chromosome) est codé sous forme d’une chaine
binaire constituée de m gènes, I = {g1 , g2 , g3 , · · · , gm } tel que ∀i ∈ [1, m], gi ∈ V = {0, 1}. Important ! il existe
également le codage réel tel que gi ∈ R. Toutefois, dans cette section nous nous focaliserons exclusivement sur
le codage binaire. Pour une population constituée de n individus P = {I1 , I2 , I3 , · · · , In } et chaque individu
est codé en m gènes, nous obtenons :



 I1 = g11 , g21 , g31 , · · · , gm
1
2 2 2 2
 I2 = g1 , g2 , g3 , · · · , gm




P= I3 = g13 , g23 , g33 , · · · , gm
3
(64)
 ..
.




In = (g1n , g2n , g3n , · · · , gm
n


}

Chaque individu Ii (appelé aussi chromosome ou encore génome) de la population P est formé de m gènes,
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

choisis de manière totalement aléatoire. Dans le cas du codage binaire, la fonction fitness (ou efficacité) f ∈ Rn+ .
Cette fonction sert à classer les individus en fonction de leur performance. Elle peut être vue également comme
une mesure d’adaptation des individus à leur environnement. En pratique, on utilise une fonction de décodage
δ permettant le passage du système binaire au système décimal, soit :

δ : {0, 1}m 7−→ R

f : δ {0, 1}m 7−→ R∗+
Dans sa formulation la plus simple, la fonction δ est définie selon :
m
tel que δ(Ii ) ∈ R∗+
X
δ(Ii ) = gj 2m−j (65)
j=1

Plus de détails sur la conversion des systèmes de numération sont donnés en annexe (B). Dans ce qui suit,
nous décrirons succinctement les trois mécanismes de base de la sélection naturelle. Ensuite, nous prendrons
un exemple d’application numérique afin de faciliter la compréhension des différentes notions inhérentes aux
algorithmes génétiques.

4. Les algorithmes génétiques font partie des méthodes dites de recherche globale : cela signifie la possibilité d’atteindre un
optimum, ou du moins un meilleur point, même si ce dernier n’est pas dans le voisinage immédiat de l’itéré précédent. Toutes les
autres méthodes d’optimisation vues précédemment sont dites de recherche locale : Le nouvel itéré est recherché dans le voisinage
immédiat (d’où la notion de localité) de l’itéré précédent.

Chapitre2 Algorithmes d’optimisation 30

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

a) Sélection: Le processus de sélection naturelle permet aux gènes les mieux adaptés de se reproduire
plus souvent et de contribuer davantage aux générations futures. Dans une population P = {I1 , I2 , I3 , · · · , In },
i
chaque individu est évalué par la fonction fitness Rw = f (δ(Ii )). En pratique, nous associons à chaque individu,
i
une probabilité Ps , d’être sélectionné.

Ri
Psi = X w i (66)
Rw
i∈P

Il existe une panoplie de processus de sélection. Nous avons pris la méthode la plus intuitive. Autrement
dit, la probabilité de reproduction d’un individu dépend de sa valeur au regard de l’ensemble des valeurs de
la population.

b) Croisement: Nous vérifions d’abord s’il y a croisement (ou reproduction) selon une probabilité
de croisement typiquement Pc ∈ V (0.85, 1). Il existe plusieurs types de croisement, nous considérons ici
le croisement dit arithmétique. Soient une population de deux individus {I1 , I2 } et un nombre aléatoire
α ∈ V (0, 1). S’il y a croisement les rejetons ri = {r1 , r2 , r3 } (enfants) de la nouvelle génération s’obtiennent
selon :


 r1 = α I1 + α I2

ri = r = (1 − α) I + α I
2 1 2 (67)
 r = α I + (1 − α) I

3 1 2

L’opération de croisement atteint chaque gène de chaque individu, selon le processus ci-dessous.

α g11 + α g12
 
 α g1 + α g2 
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

 2 2 
1 2 
α g + α g

r1 = 
 3 3  (68)
.. 
.
 
 
1 2
α gm + α gm

(1 − α) g11 + α g12
 
 (1 − α) g 1 + α g 2 
 2 2 
1 2 
(1 − α) g + α g

r2 = 
 3 3  (69)
.. 
.
 
 
1 2
(1 − α) gm + α gm

α g11 + (1 − α) g12
 
 α g 1 + (1 − α) g 2 
 2 2 
1 2 
α g + (1 − α) g

r3 = 
 3 3  (70)
.. 
.
 
 
1 2
α gm + (1 − α) gm

Les individus de la nouvelle génération {r1 , r2 , r3 } ont hérité en théorie les meilleurs gènes des individus de
la génération précédente.

Chapitre2 Algorithmes d’optimisation 31

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

c) Mutation: Nous vérifions d’abord s’il y a mutation selon une probabilité de mutation typiquement
Pm ∈ V (10−4 , 10−1 ). Pour un gène ayant une probabilité de mutation Pm , nous obtenons de façon totalement
aléatoire :

0
 gi + ψ[max(gi ) − gi ]
 1ère possibilité
gi = (71)
 g − ψ[max(g ) − g ]

2ème possibilité
i i i

La fonction ψ est définie selon l’expression :

b
gT − gt

ψ(x) = x β (72)
gT

Avec β est un nombre aléatoire ∈ V (0, 1), gt est la génération courante, gT est la génération maximale et
b est le degré d’extinction.

Exercice ½ + r
En guise d’application numérique, soit à maximiser la fonction-objectif à une seule variable :

x∗ ∈ argmax 17 (x − x2 ) (73)
x∈Rn

Si l’on souhaite la minimiser on prendra tout simplement :

x∗ ∈ argmin − 17 (x − x2 ) (74)
x∈Rn

Prendre une probabilité de croisement Pc = 0.75 et une probabilité de mutation Pm = 0.001. La population
initiale est formée de six individus. Ces derniers sont constitués de quatre gènes. Cet exemple simple vise à
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

illustrer concrètement le fonctionnement des opérations de sélection, de croisement, de mutation et l’utilisation

des différents paramètres des algorithmes génétiques permettant d’atteindre l’optimum. Cet exercice sera
intégralement résolu lors de la séance de cours.

Exercice ¾ + r
Pour des problèmes d’optimisation plus complexes, nous utiliserons la fonction Matlabr prédéfinie ga. En
guise d’application de cette fonction, nous souhaitons optimiser la fonction-objectif précédente (63) dont nous
rappelons la formule :

y2
f (X) = 5 x2 + − 3 (x + y) avec X = (x, y)T
2
La syntaxe de la fonction Matlabr prédéfinie ga est donnée dans le script Matlabr ci-dessous :

clc␣;␣clear␣all␣;

%␣Samir␣KENOUCHE␣-␣Unconstrained␣optomization␣using␣algorithm␣genetic
%␣Le␣14/09/2019

addpath(’C:\Users\kenouche’)␣;

myfitness␣=␣@(x)␣5*x(1).ˆ2␣+␣x(2).ˆ2*(1/2)␣-␣3*(x(1)+x(2))␣;

cineq␣=␣[]␣;␣ceq␣=␣[]␣;␣␣␣%␣unconstrained␣problem

Chapitre2 Algorithmes d’optimisation 32

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

rng(1037,’twister’)␣;␣␣␣␣␣%␣Control␣random␣number␣generation
xinit␣=␣randn([1␣2])␣;␣␣␣␣%␣Initialisation
nbrevars␣=␣2␣;␣␣␣␣␣␣␣␣␣␣␣␣%␣Number␣of␣variables
LB␣=␣[-inf␣-inf]␣;␣␣␣␣␣␣␣␣%␣Lower␣bound
UB␣=␣[+inf␣+inf]␣;␣␣␣␣␣␣␣␣%␣Upper␣bound

options␣=␣gaoptimset(’CreationFcn’,␣@gacreationlinearfeasible,␣...
␣␣␣␣’PlotFcns’,␣@gaplotbestf,␣’CrossoverFraction’,␣0.75,␣...
␣␣␣␣’InitialPopulation’,xinit,’MutationFcn’,@mutationadaptfeasible,␣...
␣␣␣␣’EliteCount’,␣2,’PopulationSize’,50,␣’TolFun’,␣1e-03,’Display’,’iter’)␣;

[xoptimal,fval,exitflag,output,population,scores]␣=␣ga(myfitness,␣...
␣␣␣␣nbrevars,[],[],[],[],LB,UB,␣cineq,␣ceq,␣options)␣;

disp(output.message)␣;
str␣=␣[’LES␣POINTS␣STATIONNAIRES␣OBTENUS␣:␣’␣num2str(xoptimal)]
%␣LES␣POINTS␣STATIONNAIRES␣OBTENUS␣:␣0.3␣␣3

En conclusion, nous soulignons que les trois processus d’un algorithme génétique sont régit par un certain
nombre de paramètres fixés préalablement. Ces derniers conditionnent la réussite de l’optimisation du problème
étudié. Parmi ces paramètres, nous citerons (1) La taille de la population P, et la taille de la chaine de codage
des individus. Si cette population est trop grande, le temps de calcul de l’algorithme peut se révéler très
contraignant. En revanche, si la taille de la population est petite, l’algorithme convergera vraisemblablement
vers un mauvais individu. (2) Le choix de la valeur de la probabilité de croisement Pc , celle-ci dépend de la
forme de la fonction fitness. En pratique, le choix de cette probabilité se fait de façon heuristique. Plus Pc est
élevée, plus la population subit des transformations profondes. (3) Le choix de la valeur de la probabilité de
mutation Pm . Elle est généralement faible puisqu’une valeur élevée risque de conduire à une solution divergente.
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

Une dernière notion inhérente aux algorithmes génétiques est celle de l’élitisme. Cette opération consiste
à conserver le meilleur individu dans la génération ultérieure. Après le croisement, on compare le meilleur
individu de la génération courante avec le meilleur individu de la génération antérieure. A l’issue de cette
comparaison, le meilleur individu est conservé au détriment de l’autre qui est éliminé.

Exercice ¿ + r
1) Minimiser en utilisant l’algorithme génétique la fonction-objectif définie par :

f (X) = 100 (x21 − x2 )2 + (1 − x1 )2


 x1 x2 + x1 − x2 + 1.5 ≤ 0

X̂ ∈ argmin f (X)tel que 10 − x x ≤ 0
1 2
X∈Rn  0 ≤ x ≤ 1, 0 ≤ x ≤ 13

1 2

D’abord nous commençons par écrire les contraintes dans un fichier M-file, qu’on appellera ensuite depuis
le script principal.

␣function␣[cineq,␣ceq]␣=␣myconstraint(x)
␣␣␣cineq␣=␣[1.5␣+␣x(1)*x(2)␣+␣x(1)␣-␣x(2)␣;
␣␣␣-x(1)*x(2)␣+␣10]␣;
␣␣␣ceq␣=␣[]␣;
␣return

Chapitre2 Algorithmes d’optimisation 33

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Ce fichier est sauvegardé obligatoirement sous le nom myconstraint.m et doit être dans le même répertoire
que le script principal ci-dessous :

clc␣;␣clear␣all␣;

%␣Samir␣KENOUCHE␣-␣Constrained␣optomization␣using␣algorithm␣genetic
%␣Le␣15/09/2019
addpath(’C:\Users\kenouche’)␣;

myfitness␣=␣@(x)␣100*(x(1)ˆ2␣-␣x(2))ˆ2␣+␣(1␣-␣x(1))ˆ2␣;

rng(1403,’twister’)␣;␣␣␣%␣Control␣random␣number␣generation
xinit␣=␣randn([1␣2])␣;␣␣%␣initialisation
nbrevars␣=␣2␣;␣␣␣␣␣␣␣␣␣␣%␣Number␣of␣variables
LB␣=␣[0␣0]␣;␣␣␣␣␣␣␣␣␣␣␣␣%␣Lower␣bound
UB␣=␣[1␣13]␣;␣␣␣␣␣␣␣␣␣␣␣%␣Upper␣bound

options␣=␣gaoptimset(’CreationFcn’,␣@gacreationlinearfeasible,␣...
␣␣␣␣’PlotFcns’,␣@gaplotbestf,␣’CrossoverFraction’,␣0.75,␣...
␣␣␣␣’InitialPopulation’,xinit,’MutationFcn’,@mutationadaptfeasible,␣...
␣␣␣␣’EliteCount’,␣1,’PopulationSize’,50,␣’TolFun’,␣1e-03,␣...
␣␣␣␣’Display’,’iter’)␣;

[xopti,fval,exitflag,output,population,scores]␣=␣ga(myfitness,␣nbrevars,␣...
␣␣␣␣[],[],[],[],LB,UB,␣@myconstraint,␣options)␣;
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

disp(output.message)
str␣=␣[’Les␣points␣statonnaires␣obtenus␣:␣’␣num2str(xopti)]
%%␣Les␣points␣stationnaires␣obtenus␣:␣0.812202␣␣12.3122

V. Travaux pratiques avec des fonctions Matlab prédéfinies

A. Optimisation sans contraintes
La formulation mathématique générale d’un problème d’optimisation sans contraintes s’écrit selon :

X̂ = argmin f (X) (75)

X∈D

Avec, D est un sous-ensemble de Rn . Les variables X = (x1 , x2 , ..., xn )T sont appelées variables d’optimisation
ou variables de décision. La fonction f , à valeurs réelles, définie par f : D ⊂ Rn → R est la fonction-objectif
ou fonction de coût. Dans cette section, on abordera les fonctions Matlabr prédéfinies, dédiées à la résolution
de problèmes d’optimisation sans contraintes. Toutes ces fonctions sont disponibles dans la boite à outil
Optimization Toolbox du logiciel. Les fonctions Matlabr prédéfinies destinées à la minimisation de fonctions
d’une seule variable sont fminbnd et fminunc. Notons que cette dernière peut également être utilisée pour les
fonctions de plusieurs variables. Ces commandes présentent une syntaxe très similaires.

options␣=␣optimset(’param␣1’,␣value␣1,␣’param␣2’,␣value␣2,␣...)
[x,␣fval,␣exitflag,␣output,␣grad,␣hessian]=␣fminunc(fun,␣x0,␣options)␣%␣pour␣fminunc
[x,␣fval,␣exitflag,␣output]␣=␣fminbnd(fun␣,lB,␣uB,␣options)␣␣␣␣␣␣␣␣␣␣␣%␣pour␣fminbnd

Chapitre2 Algorithmes d’optimisation 34

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

La fonction fminunc accepte comme arguments en entrée, la fonction à minimiser fun, les valeurs initiales x0
pour initialiser la recherche des minimums et en dernier lieu l’argument options spécifiant les différents champs
d’optimisation. Ces derniers sont modifiés en appelant la fonction optimset, dont ses différents paramètres
seront décrits dans l’exercice ci-dessous. L’argument fun peut être définie en tant que objet inline, fonction
anonyme ou bien une fonction M-file. Les sorties renvoyées sont : x représentant le minimum trouvé après
convergence et fval est le nombre d’évaluation de la fonction fun. Une valeur de la sortie exitflag = 1
signifie que l’algorithme a bel et bien convergé vers la solution approchée. Plus généralement, une valeur de
exitflag > 1 signifie que l’algorithme a convergé vers la solution. Une valeur de exitflag < 1 signifie que
l’algorithme n’a pas convergé. Dans le cas où exitflag = 0, cela veut dire que le nombre d’itérations ou le
nombre d’évaluation de la fonction est atteint. La sortie output renvoie des champs relatifs au type d’algorithme
utilisé, le nombre d’itérations conduisant à la solution approchée, un message sur l’état de l’optimisation ...
etc. Les sorties grad et hessian renvoient respectivement le Jacobien (première dérivée) et le Hessien (second
dérivée) de la fonction à minimiser.

La différence entre les fonctions fminunc et fminbnd se situe au niveau de l’initialisation de la recherche de
la solution. En effet, fminunc démarre la recherche à partir d’une valeur initiale apportée par x0. En revanche,
fminbnd effectue sa recherche à partir d’un intervalle dont les bornes inférieure et supérieure sont indiquées
respectivement par les entrées lB et uB.

Exercice ¶ + r
1) Minimiser la fonction-objectif définie par :

2
 f (x) = (x − 1) × exp(−x + 2 x + 1)

(76)
 x ∈ [−4, 4]


en utilisant les fonctions prédéfinies fminbnd et fminunc

Script Matlabr

clear␣all;␣clc␣;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
lB␣=␣-4␣;␣uB␣=␣4␣;␣xinit␣=␣1␣;
fx␣=␣@(x)␣(x-1).*exp(-x.ˆ2␣+␣2.*x␣+␣1)␣;

opts␣=␣optimset(’Display’,’iter’,’FunValCheck’,’on’,’TolX’,1e-8)␣;
%␣parametres␣d’optimisation
[xMin1,␣funEval1,␣exitTest1,␣output1,␣grad1,␣hessian1]␣=␣fminunc(fx,␣xinit,␣opts)␣;
%␣premiere␣possibilite
[xMin2,␣funEval2,␣exitTest2,␣output2]␣=␣fminbnd(fx,␣lB,␣uB,␣opts)␣;
%␣Deuxieme␣posibilite

Les arguments de sortie renvoyés par fminunc sont :

%%%%%%%%%%%%%%%%%%%␣AFFICHAGE␣PAR␣DEFAUT␣1ER␣CAS␣%%%%%%%%%%%%%%%%%%%
␣Iteration␣␣Func-count␣␣␣␣␣␣␣f(x)
␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣2␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0
␣␣␣␣␣1␣␣␣␣␣␣␣␣␣␣␣4␣␣␣␣␣␣␣␣␣-2.71828
␣␣␣␣␣2␣␣␣␣␣␣␣␣␣␣␣6␣␣␣␣␣␣␣␣␣-3.16544
␣␣␣␣␣3␣␣␣␣␣␣␣␣␣␣␣8␣␣␣␣␣␣␣␣␣-3.16849

Chapitre2 Algorithmes d’optimisation 35

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣4␣␣␣␣␣␣␣␣␣␣10␣␣␣␣␣␣␣␣␣-3.16903
␣␣␣␣␣5␣␣␣␣␣␣␣␣␣␣12␣␣␣␣␣␣␣␣␣-3.16903
␣␣␣␣␣6␣␣␣␣␣␣␣␣␣␣14␣␣␣␣␣␣␣␣␣-3.16903
Optimization␣terminated:␣relative␣infinity-norm␣of␣gradient␣less␣than␣options.TolFun.
%%%%%%%%%%%%%%%%%%%␣AFFICHAGE␣PAR␣DEFAUT␣2EME␣CAS␣%%%%%%%%%%%%%%%%%%
␣Func-count␣␣␣␣␣x␣␣␣␣␣␣␣␣␣␣f(x)
␣␣␣␣1␣␣␣␣␣␣-0.944272␣␣␣␣-0.327815
␣␣␣␣2␣␣␣␣␣␣␣0.944272␣␣␣␣-0.410501
␣␣␣␣3␣␣␣␣␣␣␣␣2.11146␣␣␣␣␣␣2.38771
␣␣␣␣4␣␣␣␣␣␣0.0274024␣␣␣␣␣-2.79063
␣␣␣␣5␣␣␣␣␣0.00805821␣␣␣␣␣-2.74001
␣␣␣␣6␣␣␣␣␣␣␣0.252738␣␣␣␣␣-3.15901
␣␣␣␣7␣␣␣␣␣␣␣␣0.51688␣␣␣␣␣-2.82668
␣␣␣␣8␣␣␣␣␣␣␣0.278372␣␣␣␣␣-3.16771
␣␣␣␣9␣␣␣␣␣␣␣␣0.29087␣␣␣␣␣-3.16901
␣␣␣10␣␣␣␣␣␣␣0.293071␣␣␣␣␣-3.16903
␣␣␣11␣␣␣␣␣␣␣␣␣0.2929␣␣␣␣␣-3.16903
␣␣␣12␣␣␣␣␣␣␣0.292893␣␣␣␣␣-3.16903
␣␣␣13␣␣␣␣␣␣␣0.292893␣␣␣␣␣-3.16903
␣␣␣14␣␣␣␣␣␣␣0.292893␣␣␣␣␣-3.16903
␣␣␣15␣␣␣␣␣␣␣0.292893␣␣␣␣␣-3.16903

Optimization␣terminated:
␣the␣current␣x␣satisfies␣the␣termination␣criteria␣using␣OPTIONS.TolX␣of␣1.000000e-08

Les autres sorties sont affichées comme suit :

>>␣xMin1␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣0.2929
␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣MINIMUM␣OBTENU

>>␣funEval1␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣-3.1690
␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣VALEUR␣DE␣LA␣FONCTION␣A␣LA␣DERNIERE␣ITERATION

>>␣exitTest1␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣1
␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣TEST␣DE␣CONVERGENCE␣POSITIF

>>␣grad1␣=

␣␣␣␣␣␣␣␣␣␣-5.9605e-08
␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣VALEUR␣DU␣GRADIENT␣DE␣LA␣FONCTION-OBJECTIF

>>␣hessian1␣=

␣␣␣␣␣␣␣␣␣␣␣␣␣␣12.6783
␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣VALEUR␣DU␣HESSIEN␣DE␣LA␣FONCTION-OBJECTIF

>>␣xMin2␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.2929

Chapitre2 Algorithmes d’optimisation 36

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣MINIMUM␣OBTENU␣AVEC␣fminbnd

>>␣funEval2␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣-3.1690

>>␣exitTest2␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣1

L’argument opts, de type srtucture, compte les options d’optimisation spécifiées dans optimset. Le champ
de la structure opts indiqué par optimset(’Display’,’iter’, ...) affiche des détails pour chaque itération.
Si l’on désire afficher uniquement les détails de la dernière itération, on remplacera ’iter’ par ’final’. Dans
le cas où on ne veut afficher aucun détails, on mettra la valeur ’off’. Le champ indiqué par optimset(....,
’FunValCheck’,’on’,...) contrôle si les valeurs de la fonction sont réelles et affiche dans le cas contraire un
avertissement quand la fonction en question renvoie une valeur complexe ou NaN. On peut suspendre cette
vérification, en remplaçant la valeur ’on’ par ’off’. Le champ d’optimisation optimset(...., ’TolX’,
1e-08) correspond à la tolérance admise pour la solution approchée. D’autres champs d’optimisation existent
comme MaxFunEvals qui fixe le nombre maximum d’évaluation de la fonction à optimiser et MaxIter fixant
également le nombre maximum d’itération. Voir aussi GradObj, OutputFcn, PlotFcns, ... etc dont la description
est disponible dans le help de Matlabr .

La sortie xMin1 = 0.2929 est le minimum trouvé. Ce dernier est cherché autour de la valeur initiale xinit.
La sortie funEval1 = -3.1690 exprime l’évaluation de la fonction à la dernière itération, c’est-à-dire pour
fx(x = xMin1). L’argument exitTest = 1 signifie que l’algorithme a convergé vers la solution, une valeur
négative indiquerai le contraire. L’argument de sortie output1, de type structure, renvoie les champs suivants :

>>␣output1␣=␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣pour␣la␣commande␣fminunc
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

␣␣␣␣␣␣␣␣␣␣␣␣iterations:␣6
␣␣␣␣␣␣␣␣␣␣␣␣␣funcCount:␣14
␣␣␣␣␣␣␣␣␣␣␣␣␣␣stepsize:␣1
␣␣␣␣␣␣␣␣␣firstorderopt:␣5.9605e-08
␣␣␣␣␣␣␣␣␣␣␣␣␣algorithm:␣[1x38␣char]␣␣%␣’Quasi-Newton␣line␣search’
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣message:␣[1x85␣char]␣␣%␣␣Optimization␣terminated␣...

>>␣output2␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣␣pour␣la␣commande␣fminbnd
␣␣␣␣␣␣␣␣␣␣␣␣iterations:␣14
␣␣␣␣␣␣␣␣␣␣␣␣␣funcCount:␣15
␣␣␣␣␣␣␣␣␣␣␣␣␣algorithm:␣[1x46␣char]␣␣%␣’golden␣section␣search’
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣message:␣[1x111␣char]␣%␣Optimization␣terminated␣...

La fonction a été évaluée 14 fois et l’algorithme converge vers la solution approchée au bout de la 6ième
itération. La sortie stepsize: 1 indique le pas final de l’algorithme moyenne dimension de Quasi-Newton. Le
mot Optimization affiché comme message, fait référence au faite que l’algorithme de minimisation fonctionne
selon le critère des moindres carrés. fminbnd présente les mêmes propriétés que celles de fminunc, à la différence
que fminbnd cherche le minimum dans un intervalle, donné en argument d’entrée avec la borne inférieure lB
(lower Bound) et la borne supérieure uB (upper Bound).

Nous allons désormais tester la fonction fminsearch qui s’utilise pour la minimisation de fonctions multi-
dimensionnelles. Sa syntaxe usuelle est analogue à celle de fminunc, à la différence près que fminsearch ne
renvoie ni le Jacobien ni le Hessien de la fonction à optimiser. Ceci provient du fait que cette fonction est

Chapitre2 Algorithmes d’optimisation 37

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

basée sur l’algorithme Simplex. Nous allons procéder à son implémentation dans l’exercice ci-dessous.

Exercice · + r
1) Minimiser la fonction-objectif de deux variables définie par :

f (x1 , x2 ) = x21 + (x2 − 2)2 (77)

analytiquement puis en utilisant la fonction prédéfinie fminsearch

Commençons par déterminer, analytiquement, les extremums de la fonction f (x1 , x2 ). Le gradient de la

fonction s’écrit :

∂f
= 2 x1 = 0



∂x1 (78)
∂f
= 2 (x2 − 2) = 0



∂x2
Le vecteur du point critique est donné donc par X̂ = (x̂1 = 0 ; x̂2 = 2). Cherchons désormais la nature de
ce point, s’agit-il d’un minimum ou d’un maximum ?. Calculons le déterminant du Hessien de f .

∂ 2 f (X̂) ∂ 2 f (X̂)
∂x21 ∂x1 ∂x2 2 0
2 2 =⇒ =4>0 (79)
∂ f (X̂) ∂ f (X̂) 0 2
∂x2 ∂x1 ∂x22

À partir de ces résultats, il en découle que le point X̂ = (x̂1 = 0 ; x̂2 = 2) est le minimum recherché. Nous
résoudrons le même système de façon algorithmique en se servant de la fonction fminsearch. Voici le script
Matlabr
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

clear␣all;␣clc␣;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
xinit␣=␣[1␣1]␣;␣fun␣=␣@(x)␣x(1).ˆ2␣+␣(x(2)␣-␣2).ˆ2;
opts␣=␣optimset(’Display’,’iter’,’FunValCheck’,’on’,’TolX’,1e-8)␣;

[xMin,␣funEval,␣exitTest,␣output]␣=␣fminsearch(fun,␣␣xinit,␣opts)␣;

Ci-dessous les différentes sorties renvoyées par le script.

%%%%%%%%%%%%%%%%%%%%%%%%%%%␣SORTIE␣PAR␣DEFAUT␣%%%%%%%%%%%%%%%%%%%%%%%%
␣Iteration␣␣␣Func-count␣␣␣␣␣Min␣f(x)
␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣␣1␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣2
␣␣␣␣␣1␣␣␣␣␣␣␣␣␣␣␣␣3␣␣␣␣␣␣␣␣␣␣␣1.9025
␣␣␣␣␣2␣␣␣␣␣␣␣␣␣␣␣␣5␣␣␣␣␣␣␣␣␣␣1.66563
␣␣␣␣␣3␣␣␣␣␣␣␣␣␣␣␣␣7␣␣␣␣␣␣␣␣␣␣1.38266
␣␣␣␣␣4␣␣␣␣␣␣␣␣␣␣␣␣9␣␣␣␣␣␣␣␣␣0.889414
␣␣␣␣␣5␣␣␣␣␣␣␣␣␣␣␣11␣␣␣␣␣␣␣␣␣0.353447
␣␣␣␣␣6␣␣␣␣␣␣␣␣␣␣␣13␣␣␣␣␣␣␣␣0.0265259
␣␣␣␣␣7␣␣␣␣␣␣␣␣␣␣␣14␣␣␣␣␣␣␣␣0.0265259
␣␣␣␣␣8␣␣␣␣␣␣␣␣␣␣␣16␣␣␣␣␣␣␣␣0.0265259
␣␣␣␣␣9␣␣␣␣␣␣␣␣␣␣␣18␣␣␣␣␣␣␣␣0.0265259

Chapitre2 Algorithmes d’optimisation 38

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣...␣␣␣␣␣␣␣␣␣␣...␣␣␣␣␣␣␣.........

␣␣␣␣␣63␣␣␣␣␣␣␣␣␣␣125␣␣␣␣␣␣2.15781e-17
␣␣␣␣␣64␣␣␣␣␣␣␣␣␣␣127␣␣␣␣␣␣2.15781e-17

Optimization␣terminated:
␣the␣current␣x␣satisfies␣the␣termination␣criteria␣using␣OPTIONS.TolX␣of␣1.000000e-08␣and␣F(
X)␣satisfies␣the␣convergence␣criteria␣using␣OPTIONS.TolFun␣of␣1.000000e-04

>>␣xMin␣=

␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.0000␣␣␣␣2.0000

>>␣funEval␣=

␣␣␣␣␣␣␣␣␣␣␣␣␣␣2.1578e-17

>>␣exitTest␣=

␣␣␣␣␣␣␣␣␣␣␣␣␣␣1

>>␣output

␣␣␣␣␣␣␣␣iterations:␣64
␣␣␣␣␣␣␣␣␣funcCount:␣127
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

␣␣␣␣␣␣␣␣␣algorithm:␣[1x33␣char]␣%␣’Nelder-Mead␣simplex␣direct␣search’
␣␣␣␣␣␣␣␣␣␣␣message:␣[1x194␣char]␣%␣Optimization␣terminated:␣the␣current␣x␣satisfies␣the␣
termination

L’algorithme converge vers la solution approchée Xmin au bout de 64 itérations. Notons que cette convergence
est atteinte car les conditions d’arrêt de l’algorithme sont satisfaites, soit une tolérance TolX = 1e-8. En
choisissant par exemple une tolérance de TolX = 1e-3, l’algorithme converge vers la solution approchée (xMin
= [-0.0002 ; 2.0004]) au bout de 28 itérations seulement. Dans le cas où cette dernière n’est pas spécifiée,
la valeur par défaut est TolX = 1e-6. On comprend alors que le choix de la tolérance est conditionné par la
précision recherchée. Il est important de rappeler aussi que tous ces algorithmes d’optimisation sont basés sur
des processus itératifs, donc fortement dépendant du choix de la valeur initiale. Autrement dit, plus la valeur
initiale est proche de la solution approchée plus l’algorithme converge rapidement.

Comme il a été mentionné dans la section précédente, la fonction fminunc s’utilise aussi pour l’optimisation
de fonctions à plusieurs variables. Nous allons l’utiliser pour optimiser la fonction f (x1 , x2 ) = 2 x21 + x1 x2 +
2 x22 − 6 x1 − 5 x2 + 3

Script Matlabr

clear␣all;␣clc␣;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
xinit␣=␣[-1␣1]␣;
fx␣=␣@(x)␣2*x(1).ˆ2␣+␣x(1)*x(2)␣+␣2*x(2).ˆ2␣-␣6*x(1)␣-␣5*x(2)␣+␣3␣;

Chapitre2 Algorithmes d’optimisation 39

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

opts␣=␣optimset(’LargeScale’,’off’,’Display’,’iter’,’FunValCheck’,...
␣␣␣␣’on’,’MaxIter’,␣20,’TolX’,␣1e-5)␣;
[x,␣funEval,␣exitTest,␣output,␣grad,␣hessian]␣=␣fminunc(fx,␣xinit,␣opts)␣;

Il est possible de définir explicitement le gradient et le Hessien de la fonction-objectif. Le premier intérêt de

cette procédure est de fournir les expressions analytiques, sans approximation, des dérivées. Si ces dernières ne
sont pas explicitées, Matlabr calcule une approximation selon la méthode des différences finies. L’autre intérêt
tient à l’accroissement, notamment pour des systèmes plus complexes, de la vitesse de convergence. Ainsi, le
gradient et le Hessien sont indiqués via la syntaxe options = optimset(’GradObj’,’on’,’Hessian’,’on’).
On commence d’abord par définir la fonction M-file suivante.

function␣[fun,␣Jacobien,␣Hessien]␣=␣myfun(x)

fun␣=␣2*x(1).ˆ2␣+␣x(1)*x(2)␣+␣2*x(2).ˆ2␣-␣6*x(1)␣-␣5*x(2)␣+␣3␣;

%␣Compute␣the␣objective␣function␣value␣at␣x
if␣nargout␣>␣1
%␣fun␣called␣with␣two␣output␣arguments
grad(1)␣=␣4*x(1)␣+␣x(2)␣-␣6␣;␣%␣Gradient␣of␣the␣function␣evaluated␣at␣x
grad(2)␣=␣x(1)␣+␣4*x(2)␣-␣5␣;

Jacobien␣=␣grad␣;
end

if␣nargout␣>␣2
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

hessian(1,1)␣=␣4␣;␣␣hessian(2,1)␣=␣1␣;␣%␣Hessian␣evaluated␣at␣x
hessian(2,1)␣=␣1␣;␣␣hessian(2,2)␣=␣4␣;
Hessien␣=␣hessian␣;

end
return

Cette fonction est sauvegardée sous le nom myfun.m. L’appel de cette dernière se fait avec le script suivant :

clear␣all;␣clc␣;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
xinit␣=␣[1␣1]␣;
opts␣=␣optimset(’GradObj’,’on’,’Hessian’,’on’,’Display’,’iter’)␣;
[x,␣fval,␣exitflag,␣output]␣=␣fminunc(@myfun,␣xinit,␣opts)

En écrivant opts = optimset(’GradObj’,’off’,’Hessian’,’off’), Matlabr évalue le gradient et le

Hessien de la fonction-objectif par la méthode des différences finies (DF). Le champ d’optimisation opts
= optimset(’DerivativeCheck’,’on’) compare le gradient fourni par l’utilisateur à celui évalué par DF. Le
champ d’optimisation opts = optimset(’FinDiffType’, ’forward’) (par défaut) stipule que le gradient
sera estimé par différences finies progressives. En indiquant la valeur ’central’, dans ce cas, le gradient sera
estimé par différences finies centrées. Le paramètre d’optimisation FinDiffType (type de différences finies)
n’est valable que si le paramètre DerivativeCheck est activé. D’autres paramètres d’optimisation existent, à

Chapitre2 Algorithmes d’optimisation 40

M. Samir KENOUCHE

l’instar de DiffMaxChange, DiffMinChange, FinDiffRelStep, ... etc. Consulter le help de Matlabr pour de

MASTER PHYSIQUE - Toutes options confondues

amples informations.

Exercice ¸ + s
– Justifier de l’existence d’un extremum des fonctions-objectif suivantes :

f1 (x1 , x2 ) = (1 − x1 )2 + 100 (x2 − x21 )2



f2 (x1 , x2 ) = 20 + x21 + x22 − 10 (cos(2πx1 ) + cos(2πx2 ))





 f3 (x1 , x2 ) = (x21 + x2 − 11)2 + (x1 + x22 − 7)2


1 (80)
 f4 (x1 , x2 ) = − sin(x21 + x22 )
2



f5 (x1 , x2 ) = x31 + x32 − 3 x1 x2




2 2
f6 (x1 , x2 ) = x1 − x1 x2 + x2 + 3 x1 − 2 x2 + 1


– Trouver les extremums des fonctions ci-dessus, analytiquement, ensuite en se servant de la fonction
prédéfinie fminsearch

B. Optimisation avec contraintes

De nombreux problèmes en physique, en chimie, en ingénierie et en économie nécessitent de minimiser une
fonction-objectif soumise à plusieurs contraintes. Dans ce qui suit, nous nous intéresserons à la résolution de
problèmes d’optimisation sous contraintes dont la formulation mathématique générale est donnée par :

X̂ = argmin f (X) (81)

X∈Rn
(
hi (x) = 0, {i = 1, 2, ..., n}
tel que
gj (x) ≤ 0, {j = 1, 2, ..., m}
Avec, P est un sous-ensemble non vide de Rn défini par des contraintes d’égalité et/ou d’inégalité de fonctions :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

P = {x ∈ Rn : hi (x) = 0, gj (x) ≤ 0} (82)

Ainsi, l’ensemble P est appelé domaine des contraintes, g = (g1 , g2 , ..., gm ) sont les contraintes d’inégalité
et h = (h1 , h2 , ..., hn ) sont les contraintes d’égalité. Dans cette section, il sera question de présenter l’ensemble
des fonctions Matlabr prédéfinies, dédiées à la résolution de problèmes d’optimisation avec contraintes. Toutes
ces fonctions sont disponibles dans la boite à outil Optimization Toolbox de Matlabr .

La fonction linprog (Linear programming) solutionne un processus d’optimisation, écrit sous une formu-
lation linéaire minimisant la quantité :


 A×x≤B

min f T x tel que Aeq × x = Beq (83)
X∈Rn  lB ≤ x ≤ uB


linprog s’utilise avec deux types d’algorithmes Large-échelle (Large-Scale Optimization) et Moyenne-échelle
(Medium-Scale Optimization). Le premier type est utilisé pour des systèmes complexes en terme de taille et
sous certaines conditions qu’on ne va pas détailler ici. On se contentera d’utiliser le deuxième type et plus
précisément la méthode Simplex. La syntaxe usuelle de linprog est :

[x,␣fval,␣exitflag,␣output,␣lambda]␣=␣linprog(f,␣A,␣B,␣Aeq,␣Beq,␣lB␣,␣uB,␣x0,␣options)

Chapitre2 Algorithmes d’optimisation 41

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Les quantités x, f, B, Beq, lB et uB sont des vecteurs. Les arguments A et Aeq sont des matrices.
L’argument f désigne le vecteur des coefficients des variables, tel que f T x = f (1) x(1) + f (2) x(2) ... f (n) x(n).
Les contraintes linéaires de type équation et inéquation sont écrites respectivement selon Aeq × x = Beq
et A × x ≤ B. L’argument de sortie lambda désigne le multiplicateur de Lagrange. Les arguments lB et uB
délimitent l’intervalle de définition des variables en question. Pour les variables non bornées, on mettra lB =
-inf et uB = inf.

Exercice ¹ + r
1) Minimiser la fonction-objectif définie par :

f (x) = −5 x1 − 4 x2 − 6 x3




x1 − x2 + x3 ≤ 20
 3 x + 2 x + 4 x ≤ 42
1 2 3
X̂ = argmin f (X) tel que
X∈R3 
 3 x1 + 2 x 2 ≤ 30
 0≤x ,0≤x ,0≤x

1 2 3

2) Maximiser la fonction-objectif définie par :

f (x) = 14 x1 + 6 x2




x1 + x2 ≤ 7.50
 11 x + 3 x ≤ 0.40
1 2
X̂ = argmin f (X) tel que
X∈R2 
 12 x1 + 21 x2 ≤ 1.50
 x ≥ 0, x ≥ 0

1 2

Script Matlabr , concernant la minimisation

clear␣all␣;␣clc␣;

opts␣=␣optimset(’LargeScale’,␣’off’,’Simplex’,␣’on’)␣;
options␣=␣optimset(opts,␣’Display’,␣’iter’,␣’TolFun’,␣1e-5)␣;

f␣=␣[-5␣;␣-4␣;␣-6]␣;␣A␣=␣[1␣-1␣1␣;␣3␣2␣4␣;␣3␣2␣0]␣;
B␣=␣[20;␣42;␣30]␣;␣lB␣=␣[0␣;␣0␣;␣0]␣;␣uB␣=␣[inf␣;␣inf␣;␣inf]␣;

[x,␣fval,␣exitflag,␣output,lambda]␣=␣linprog(f,␣A,␣B,␣[],␣...
[],lB,␣uB,␣[],␣options)␣;

point_critique␣=␣sprintf(’%6.4f␣\n’,␣x)

Le champ d’optimisation opts = optimset(’LargeScale’, ’off’ ...) signifie qu’on utilisera l’algorithme
Moyenne-échelle pour résoudre ce problème. Le critère d’arrêt est considéré pour la fonction à travers options
= optimset(... ’TolFun’, 1e-5), autrement dit l’algorithme s’arrête une fois que la condition |f (xk+1 ) −
f (xk )| ≤ 1e − 5 est satisfaite. Ci-dessous, l’affichage généré par le script.

The␣default␣starting␣point␣is␣feasible,␣skipping␣Phase␣1.

Phase␣2:␣Minimize␣using␣simplex.
␣␣␣␣␣␣Iter␣␣␣␣␣␣␣␣␣␣␣␣Objective␣␣␣␣␣␣␣␣␣␣␣␣␣␣Dual␣Infeasibility

Chapitre2 Algorithmes d’optimisation 42

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣f’*x␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣A’*y+z-w-f
␣␣␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣8.77496
␣␣␣␣␣␣␣1␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣-63␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣1.11803
␣␣␣␣␣␣␣2␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣-78␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0
Optimization␣terminated.

>>␣point_critique␣=␣␣␣␣␣␣␣%␣solution
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.0000
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣15.0000
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣3.0000
>>␣fval␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣-78
>>␣exitflag␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣1

On constate que l’algorithme Simplex converge vers la solution approchée au bout de trois itérations. Ci-
dessous, le script Matlabr relatif à la maximisation.

clear␣all␣;␣clc␣;

opts␣=␣optimset(’LargeScale’,␣’off’,’Simplex’,␣’on’)␣;
options␣=␣optimset(opts,␣’Display’,␣’iter’,␣’TolFun’,␣1e-5)␣;

f␣=␣[-14␣;␣-6]␣;␣A␣=␣[1␣1␣;␣11␣3␣;␣12␣21]␣;
B␣=␣[7.50␣;␣0.40␣;␣1.50]␣;␣lB␣=␣[0␣;␣0]␣;␣uB␣=␣[inf␣;␣inf]␣;
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

[x,␣fval,␣exitflag,␣output,lambda]␣=␣linprog(f,␣A,␣B,␣[],␣...
[],lB,␣uB,␣[],␣options)␣;

point_critique␣=␣sprintf(’%6.4f␣\n’,␣x)

Maximiser la fonction 14 x1 + 6 x2 revient à minimiser −14 x1 − 6 x2 . Ci-dessous, l’affichage généré par ce

script.

The␣default␣starting␣point␣is␣feasible,␣skipping␣Phase␣1.

Phase␣2:␣Minimize␣using␣simplex.
␣␣␣␣␣␣Iter␣␣␣␣␣␣␣␣␣␣␣␣Objective␣␣␣␣␣␣␣␣␣␣␣␣␣␣Dual␣Infeasibility
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣f’*x␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣A’*y+z-w-f
␣␣␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣15.2315
␣␣␣␣␣␣␣1␣␣␣␣␣␣␣␣␣␣␣␣-0.509091␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣2.18182
␣␣␣␣␣␣␣2␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣-0.64␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0
Optimization␣terminated.

>>␣point_critique␣=␣␣␣␣␣␣␣%␣point␣critique␣du␣maximum
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.0200
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.0600
>>␣fval␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣-0.6400

Chapitre2 Algorithmes d’optimisation 43

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

>>␣exitflag␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣1

Désormais on se servira de la fonction fmincon. La topologie générale d’un processus d’optimisation avec
contraintes sur les variables, peut s’écrire suivant la notation compacte suivante :



 A×x≤B
× x = Beq



 Aeq
X̂ ∈ argminf (X) tel que C(x) ≤ x (84)
X∈Rn
Ceq(x) = x






lB ≤ x ≤ uB

Les quantités x, B, Beq, lB, et uB sont des vecteurs. A et Aeq sont des matrices, f (x), C(x) et Ceq(x)
sont des fonctions pouvant êtres également des fonctions non-linéaires. Afin de résoudre des problèmes d’opti-
misation sous contraintes, on se servira de fmincon. Cette fonction sert à optimiser des fonctions-objectifs
multidimensionnelles non-linéaires. Par défaut, l’algorithme d’optimisation est basé sur la méthode SQP
(Sequential Quadratic Programming). La syntaxe usuelle de fmincon s’écrit selon :

[x,␣fval,␣exitflag,␣output,␣lambda,␣grad,␣hessian]␣=␣fmincon(fun,␣x0,␣A,␣B,␣Aeq,␣Beq,␣lB,␣
uB,␣@nonlcon,␣options)

Les contraintes linéaires de type équation et inéquation sont écrites respectivement selon Aeq × x = Beq
et A × x ≤ B. Les contraintes non-linéaires de type équation et inéquation sont données respectivement par
Ceq(x) = x et C(x) ≤ x. La fonction M-file @nonlcon contient les contraintes non-linéaires de type équation et
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

inéquation. Les autres arguments en entrée et en sortie ont la même signification que ceux des fonctions vues
précédemment. Il est très important de souligner que si un ou plusieurs arguments ci-dessus sont manquants,
on doit les remplacer par un ensemble vide []. L’ordre d’apparition des arguments en entrée est important,
on doit toujours commencer par les contraintes de type inégalité même si ce type de contrainte est vide. Nous
commencerons dans un premier temps par résoudre un problème d’optimisation sous contraintes linéaires.

Exercice º + r
– On se propose de minimiser la fonction-objectif définie par :

f (x1 , x2 ) = 2 x21 + x1 x2 + 2 x22 − 6 x1 − 6 x2 + 15





x1 + 2 x2 ≤ 5
 4x ≤ 7
1
X̂ = argmin f (X) tel que
X∈R2 
 x 2 ≤2
 −2 x + 2 x = −1

1 2

Script Matlabr

clc␣;␣clear␣all␣;
%%%%%%%%%%%%%%%%%%%␣Optimisation␣sous␣contraintes␣%%%%%%%%%%%%%%%%%%%
fun␣=␣@(x)␣2*x(1).ˆ2␣+␣x(1)*x(2)␣+␣2*x(2).ˆ2␣-␣6*x(1)␣-␣6*x(2)␣+␣15␣;

A␣=␣[1␣2␣;␣4␣0␣;␣0␣1]␣;␣B␣=␣[5␣7␣2]␣;
Aeq␣=␣[-2␣2]␣;␣Beq␣=␣-1␣;␣xinit␣=␣[-1␣1/2]␣;

Chapitre2 Algorithmes d’optimisation 44

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

options␣=␣optimset(’LevenbergMarquardt’,’on’,’Display’,’iter’,␣...
␣␣␣␣’TolX’,␣1e-4)␣;
[x,␣fval,␣exitflag,␣output,␣lambda,␣grad,␣hessian]␣=␣fmincon(fun,␣...
␣␣␣␣xinit,␣A,␣B,␣Aeq,␣Beq,␣[],␣[],␣[],␣options)

Le champ d’optimisation optimset(’LevenbergMarquardt’,’on’, ...) indique que l’opération d’opti-

misation sera menée par le biais de l’algorithme de Levenberg-Marquardt. Le choix de cet algorithme peut
se faire également avec la syntaxe optimset(’NonlEqnAlgorithm’,’lm’, ...). On peut aussi faire appel
à l’algorithme de Gauss-Newton, en utilisant la syntaxe optimset(’NonlEqnAlgorithm’,’gn’, ...). Les
différentes sorties renvoyées par ce script sont énumérées ci-dessous.

%%%%%%%%%%%%%%%%%%%%%%%␣affichage␣par␣defaut␣%%%%%%%%%%%%%%%%%%%%%%%%
Iter␣F-count␣␣␣␣␣␣␣␣f(x)␣␣␣constraint
␣␣␣␣0␣␣␣␣␣␣3␣␣␣␣␣␣␣␣␣␣␣20␣␣␣␣␣␣␣␣␣␣␣␣4
␣␣␣␣1␣␣␣␣␣␣6␣␣␣␣␣␣␣8.4375␣␣␣␣1.332e-15
␣␣␣␣2␣␣␣␣␣␣9␣␣␣␣␣␣8.05206␣␣␣␣␣␣␣␣␣␣␣␣0
␣␣␣␣3␣␣␣␣␣12␣␣␣␣␣␣␣7.9875␣␣␣␣␣2.22e-16

Optimization␣terminated:␣first-order␣optimality␣measure␣less
␣than␣options.TolFun␣and␣maximum␣constraint␣violation␣is␣less
␣than␣options.TolCon.
No␣active␣inequalities.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>␣x␣=␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣%␣coordonnees␣du␣point␣critique

␣␣␣␣␣␣1.4500␣␣␣␣0.9500
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

>>␣fval␣=

␣␣␣␣␣␣7.9875

>>␣exitflag␣=

␣␣␣␣␣␣1

>>␣output␣=

␣␣␣␣␣␣␣␣␣iterations:␣3
␣␣␣␣␣␣␣␣␣␣funcCount:␣12
␣␣␣␣␣␣␣lssteplength:␣1
␣␣␣␣␣␣␣␣␣␣␣stepsize:␣0.1607
␣␣␣␣␣␣␣␣␣␣algorithm:␣[1x44␣char]
␣␣␣␣␣␣firstorderopt:␣[1x1␣double]
␣␣␣␣constrviolation:␣[1x1␣double]
␣␣␣␣␣␣␣␣␣␣␣␣message:␣[1x144␣char]

>>␣lambda␣=

␣␣␣␣␣␣␣␣␣lower:␣[2x1␣double]
␣␣␣␣␣␣␣␣␣upper:␣[2x1␣double]
␣␣␣␣␣␣␣␣␣eqlin:␣0.3750

Chapitre2 Algorithmes d’optimisation 45

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣␣eqnonlin:␣[0x1␣double]
␣␣␣␣␣␣␣ineqlin:␣[3x1␣double]
␣␣␣␣ineqnonlin:␣[0x1␣double]

>>␣grad␣=

␣␣␣␣␣␣0.7500
␣␣␣␣␣-0.7500

>>␣hessian␣=

␣␣␣␣␣␣2.6500␣␣␣␣2.3500
␣␣␣␣␣␣2.3500␣␣␣␣2.6500

Nous résolvons dans l’exercice ci-dessous, un problème d’optimisation avec contraintes non-linéaires.

Exercice » + r
– On se propose de minimiser le fonction-objectif définie par :

f (x1 , x2 ) = exp(x1 ) (4 x21 + 2 x22 + 4 x1 x2 + 2 x2 + 1)

(
2 + x1 x2 − x1 − x2 ≤ 0
X̂ = argmin f (X) tel que
X∈R2 −x1 x2 ≤ 10

On commence d’abord par écrire le fichier M-file correspondant aux contraintes non-linéaires. Ce fichier
bien entendu est sauvegardé sous le nom mycontr.m. Voici le script :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

function␣[C,␣Ceq]␣=␣mycontr(x)
%␣fonction␣definissant␣les␣contraintes␣non␣lineaires

C␣=␣[2␣+␣x(1)*x(2)␣-␣x(1)␣-␣x(2)␣;␣-x(1)*x(2)␣-␣10]␣;␣%␣inequation
Ceq␣=␣[]␣;␣%␣pas␣de␣contraintes␣non␣lineaires␣en␣equation
return

Ci-dessous le script Matlabr du programme appelant.

clc␣;␣clear␣all␣;

fun␣=␣@(x)␣exp(x(1))*(4*x(1)ˆ2␣+␣2*x(2)ˆ2␣+␣4*x(1)*x(2)␣+␣2*x(2)␣+␣1)

xinit␣=␣[-1␣1]␣;

options␣=␣optimset(’LevenbergMarquardt’,’on’,’Display’,’iter’,␣...
␣␣␣␣’TolX’,␣1e-4)␣;

[x,␣fval,␣exitflag,␣output,␣lambda,␣grad,␣hessian]␣=␣fmincon(fun,␣...
␣␣␣␣xinit,␣[],␣[],␣[],␣[],␣[],␣[],␣@mycontr,␣options)

Chapitre2 Algorithmes d’optimisation 46

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Les arguments de sorties renvoyés sont :

%%%%%%%%%%%%%%%%%%%%%%%␣affichage␣par␣defaut␣%%%%%%%%%%%%%%%%%%%%%%%%
Iter␣F-count␣␣␣␣␣␣␣␣f(x)␣␣␣constraint
␣␣␣␣0␣␣␣␣␣␣3␣␣␣␣␣␣␣1.8394␣␣␣␣␣␣␣␣␣␣␣␣1
␣␣␣␣1␣␣␣␣␣␣6␣␣␣␣␣␣1.98041␣␣␣␣␣␣-0.1839
␣␣␣␣2␣␣␣␣␣␣9␣␣␣␣␣␣1.63636␣␣␣␣␣␣␣0.2596
␣␣␣␣3␣␣␣␣␣12␣␣␣␣␣␣0.34132␣␣␣␣␣␣␣␣4.524
␣␣␣␣4␣␣␣␣␣15␣␣␣␣␣0.530719␣␣␣␣␣␣␣0.3344
␣␣␣␣5␣␣␣␣␣18␣␣␣␣␣0.447582␣␣␣␣␣-0.08164
␣␣␣␣6␣␣␣␣␣21␣␣␣␣␣0.123147␣␣␣␣␣␣␣␣2.352
␣␣␣␣7␣␣␣␣␣24␣␣␣␣0.0575464␣␣␣␣␣␣␣0.3957
␣␣␣␣8␣␣␣␣␣27␣␣␣␣0.0335016␣␣␣␣␣␣␣0.1153
␣␣␣␣9␣␣␣␣␣30␣␣␣␣0.0331726␣␣␣␣0.0001285
␣␣␣10␣␣␣␣␣33␣␣␣␣␣0.033173␣␣␣␣1.589e-10

Optimization␣terminated:␣first-order␣optimality␣measure␣less
␣than␣options.TolFun␣and␣maximum␣constraint␣violation␣is␣less
␣than␣options.TolCon.
Active␣inequalities␣(to␣within␣options.TolCon␣=␣1e-06):
␣␣lower␣␣␣␣␣␣upper␣␣␣␣␣ineqlin␣␣␣ineqnonlin
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣1
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>>␣x␣=

␣␣␣␣␣-9.0990␣␣␣␣1.0990
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

>>␣fval␣=

␣␣␣␣␣␣0.0332

>>␣exitflag␣=

␣␣␣␣␣␣␣1

>>␣output␣=

␣␣␣␣␣␣␣␣␣iterations:␣10
␣␣␣␣␣␣␣␣␣␣funcCount:␣33
␣␣␣␣␣␣␣lssteplength:␣1
␣␣␣␣␣␣␣␣␣␣␣stepsize:␣[1x1␣double]
␣␣␣␣␣␣␣␣␣␣algorithm:␣[1x44␣char]
␣␣␣␣␣␣firstorderopt:␣[1x1␣double]
␣␣␣␣constrviolation:␣[1x1␣double]
␣␣␣␣␣␣␣␣␣␣␣␣message:␣[1x144␣char]

>>␣lambda␣=

␣␣␣␣␣␣␣␣␣lower:␣[2x1␣double]
␣␣␣␣␣␣␣␣␣upper:␣[2x1␣double]

Chapitre2 Algorithmes d’optimisation 47

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣␣␣␣␣␣␣␣␣eqlin:␣[0x1␣double]
␣␣␣␣␣␣eqnonlin:␣[0x1␣double]
␣␣␣␣␣␣␣ineqlin:␣[0x1␣double]
␣␣␣␣ineqnonlin:␣[2x1␣double]

>>␣grad␣=

␣␣␣␣0.0255
␣␣␣-0.0034

>>␣hessian␣=

␣␣␣␣0.0280␣␣␣␣0.0035
␣␣␣␣0.0035␣␣␣␣0.0096

Exercice ¼ + s
– On se propose de minimiser les fonctions-objectif définies par :
1 1
f (x1 , x2 ) = (x1 − 3)2 + (x2 − 1)2
2 
2



x1 + x2 − 1 ≤ 0
 x −x −1≤0
1 2
X̂ = argmin f (X) tel que
X∈R2 
 −x1 + x2 − 1 ≤ 0
 −x − x − 1 ≤ 0

1 2

La fonction quadprog (Quadratic programming) solutionne un processus d’optimisation, écrit sous une
formulation quadratique qui minimise la quantité :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/


1 T  A×x≤B

minn f (X) = x H x + f T x tel que Aeq × x = Beq (85)
X∈R 2  lB ≤ x ≤ uB


La syntaxe usuelle de cette fonction est :

[x,␣fval,␣exitflag,␣output,␣lambda]␣=␣quadprog(H,␣f,␣A,␣B,␣Aeq,␣Beq,␣lb,␣ub,␣x0,␣options)

L’argument H est le Hessien de la fonction-objectif et f représente le vecteur des coefficients de la partie

linéaire de la fonction-objectif. Ces deux arguments sont obligatoires tandis que les autres sont optionnels.
Ces derniers ont la même signification que ceux de la fonction fmincon, pareil également pour les arguments
de sortie. L’ordre d’apparition des arguments doit être respecté, si un argument optionnel n’est pas utilisé, il
faudra le remplacer par l’ensemble vide [].

Exercice ½ + r
– On se propose de minimiser les fonctions-objectif définies par :

f (x1 , x2 ) = x21 + 4 x1 + 5 x2




2 x1 + x2 ≥ 10
 3 x + 6x ≤ 80
1 2
X̂ = argmin f (X) tel que
X∈R2 
 5 x 1 + 7 x 2 ≤ 50
 x ,x ≥ 0

1 2

Chapitre2 Algorithmes d’optimisation 48

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

f (x1 , x2 , x3 ) = x21 + x1 x2 + 2 x22 + 2 x23 + 2 x2 x3 + 4 x1 + 6 x2 + 12 x3

 x1 + x2 + x3 ≥ 6

X̂ = argmin f (X) tel que −x − x + 2 x ≥ 2
1 2 3
X∈R3  0 ≤ x , x , x ≤ 100

1 2 3

– Réécrire la fonction-objectif selon la notation générale décrite par l’Eq. (85).

– Trouver les coordonnées du point critique en utilisant quadprog.

Réécrivons d’abord ce système selon la notation générale décrite par l’Eq. (85).
 T     T  
1 x1 2 0 x1 4 x1
min2      +   
X∈R 2 x 0 0 x2 5 x2
2

−2 −1 " # 10
   
  x1  
 3 6 ≤
80

x2
 
5 7 50

D’après la définition sur les contraintes d’inégalités, elles doivent être écrites, inférieure ou égale à une
constante. La contrainte 2 x1 + x2 ≥ 10 est réécrite sous la forme −2 x1 − x2 ≤ 10. Voici le script Matlabr ,
pour la fonction à deux variables

clc␣;␣clear␣all␣;

H␣=␣[2␣0␣;␣0␣0]␣;␣f␣=␣[4␣;␣5]␣;
A␣=␣[-2␣-1␣;␣3␣6␣;␣5␣7]␣;␣B␣=␣[10␣;␣80␣;␣50]␣;␣lB␣=␣[0␣;␣0]␣;
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

uB␣=␣[inf␣;␣inf]␣;

options␣=␣optimset(’LargeScale’,’off’,’TolX’,␣1e-7)␣;
[x,␣fval,␣exitflag,␣output,␣lambda]␣=␣quadprog(H,␣f,␣A,␣B,␣[],[],␣...
␣␣␣␣lB,␣uB,␣[],␣options)␣;

if␣exitflag␣>␣0

␣␣␣disp(’L’’algorithme␣a␣converge␣vers␣la␣solution␣:’)
␣␣␣point_critique␣=␣x
else
␣␣␣␣disp(’L’’algorithme␣n’’a␣pas␣converge␣!’)
end

Ci-dessous les sorties correspondantes :

Optimization␣terminated.
L’algorithme␣a␣converge␣vers␣la␣solution␣:

point_critique␣=

␣␣␣␣␣0
␣␣␣␣␣0

Chapitre2 Algorithmes d’optimisation 49

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Notons qu’on peut réécrire ce script en considérant l’inégalité x1 , x2 ≥ 0 comme deux contraintes séparées
selon −x1 ≤ 0 et −x2 ≤ 0 ce qui revient à écrire deux nouvelles lignes [-1 0 ; 0 -1] dans la matrice A et
[0 ; 0] dans le vecteur B. Dans ce cas lB = [] et uB = []. Ci-dessous le script.

clc␣;␣clear␣all␣;

H␣=␣[2␣0␣;␣0␣0]␣;␣f␣=␣[4␣;␣5]␣;
A␣=␣[-2␣-1␣;␣3␣6␣;␣5␣7␣;␣-1␣0␣;␣0␣-1]␣;␣B␣=␣[10␣;␣80␣;␣50␣;␣0␣;␣0]␣;

options␣=␣optimset(’LargeScale’,’off’,’TolX’,␣1e-7)␣;
[x,␣fval,␣exitflag,␣output,␣lambda]␣=␣quadprog(H,␣f,␣A,␣B,␣[],[],␣...
␣␣␣␣[],␣[],␣[],␣options)␣;

if␣exitflag␣>␣0

␣␣␣disp(’L’’algorithme␣a␣converge␣vers␣la␣solution␣:’)
␣␣␣point_critique␣=␣x
else

␣␣␣␣disp(’L’’algorithme␣n’’a␣pas␣converge␣!’)

end

Script Matlabr pour la fonction de trois variables

clc␣;␣clear␣all␣;
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

H␣=␣[2␣1␣0␣;␣1␣4␣2␣;␣0␣2␣4]␣;␣f␣=␣[4␣;␣6␣;␣12]␣;
A␣=␣[-1␣-1␣-1␣;␣1␣1␣-2]␣;␣B␣=␣[-6␣;␣-2]␣;␣lB␣=␣[0␣;␣0␣;␣0]␣;
uB␣=␣[100␣;␣100␣;␣100]␣;␣xinit␣=␣[1␣;␣1␣;␣1]␣;

options␣=␣optimset(’Diagnostics’,’on’,’TolX’,␣1e-7)␣;
[x,␣fval,␣exitflag,␣output,␣lambda]␣=␣quadprog(H,␣f,␣A,␣B,␣[],[],␣...
␣␣␣␣lB,␣uB,␣xinit,options)␣;

if␣exitflag␣>␣0

␣␣␣disp(’L’’algorithme␣a␣converge␣vers␣la␣solution␣:’)
␣␣␣point_critique␣=␣x
else

␣␣␣␣disp(’L’’algorithme␣n’’a␣pas␣converge␣!’)

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Diagnostic␣Information
Number␣of␣variables:␣3
␣Number␣of␣linear␣inequality␣constraints:␣␣␣␣2

Chapitre2 Algorithmes d’optimisation 50

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

␣Number␣of␣linear␣equality␣constraints:␣␣␣␣␣␣0
␣Number␣of␣lower␣bound␣constraints:␣␣␣␣␣␣␣␣␣␣3
␣Number␣of␣upper␣bound␣constraints:␣␣␣␣␣␣␣␣␣␣3

Algorithm␣selected
␣␣␣medium-scale:␣active-set
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
End␣diagnostic␣information

Comme on peut le constater, le champ optimset(’Diagnostics’,’on’, ...) renvoie des informations sur
la fonction-objectif, comme le nombre de variables, le nombre d’équation et d’inéquation ... etc.

Optimization␣terminated.
L’algorithme␣a␣converge␣vers␣la␣solution␣:

>>␣point_critique␣=
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣3.3333
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣0.0000
␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣2.6667

Afin de maximiser la fonction-objectif au moyen de la fonction quadprog, on prendra -H et -f.

Exercice ¾ + s
– Minimiser les fonctions-objectif définies par :

f (x1 , x2 ) = (x1 − 2)2 + (x2 − 2)2





x1 + 2 x2 ≤ 3
 3 x + 2x ≥ 3
1 2
X̂ = argmin f (X) tel que
X∈R2 
 x1 − 2 x2 ≤ 2
 x ,x ≥ 0

1 2

f (x1 , x2 , x3 ) = x31 + x32 + x33



 x31 + x32 + x33 = 1
 2 x3 − x2 ≤ 0

3 2
X̂ = argmin f (X) tel que
X∈R3  x1 ≥ 0

 x ≤0

3

– Réécrire la fonction-objectif selon la notation générale décrite par l’Eq. (85).

– Trouver les coordonnées du point critique en utilisant quadprog. Pour la fonction à trois variables, prenez
le vecteur des valeurs initiales (1, 0, −1).

Pour conclure cette section, il recommandé également dans le même sillage de consulter les fonctions
d’optimisation prédéfinies fseminf, fminimax et fgoalattain.

Chapitre2 Algorithmes d’optimisation 51

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Annexe A
Dérivée directionnelle
Nous souhaitons quantifier le taux de variation de la fonction f : R2 7−→ R lorsqu’elle passe d’un point
f (x0 , y0 ) au point f (x, y). Nous travaillerons sur le plan de projection xoy, ce taux de variation est évalué par
→
− −−→
le segment de droite P0 P . Soit d = a~i + b ~j un vecteur unitaire ayant la même direction que P0 P .

f(x0,y0) f(x,y)

P0(x0,y0)
P(x,y)
d

~
Figure 4: Dérivée directionnelle au point P0 dans la direction d.

Sur la figure ci-dessus :

−−→ → − −−→ →
−
P0 P // d ⇒ P0 P = λ d avec λ ∈ R∗+
−−→ (86)
⇒ P0 P = λ (a~i + b ~j) = λ a~i + λ b ~j
−−→
D’un autre côté on peut définir le vecteur P0 P par rapport à l’origine O selon :

−−→ −→ −−→
P0 P = OP − OP0 (87)
= (x~i + y ~j) − (x0 ~i + y0 ~j) (88)
= x~i + y ~j − x0 ~i − y0 ~j (89)
= (x − x0 )~i + (y − y0 ) ~j (90)
Par identification des équations (86) et (90), il vient :
( (
x − x0 = λ a x = x0 + λ a
⇒ (91)
y − y0 = λ b y = y0 + λ b
→
−
Par voie de conséquence, la dérivée directionnelle de f (x, y) dans la direction du vecteur unitaire d = a~i+b ~j
au point f (x0 , y0 ) est :

f (x0 + λ a, y0 + λ b) − f (x0 , y0 )
→ (x0 , y0 ) = lim
f− (92)
d λ→0 λ

Chapitre2 Algorithmes d’optimisation 52

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

→
−
∇f (x0 , y0 ) × d = ∇f (x0 , y0 ) × (−∇f (x0 , y0 ))
= −∇f (x0 , y0 ) × ∇f (x0 , y0 )
= − ||∇(x0 , y0 )||2 >0
| {z }
| {z }
<0
→
−
⇒ d = −∇f est une direction de descente

2
Comme exemple d’application, calculons la dérivée directionnelle de la fonction f (x, y) = 2 e(x y) au point
(2, 3) dans la direction formant un angle de 75◦ avec l’axe des x positif. La solution est donnée ci-dessous :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

→
−
→ (2, 3) = ∇f (2, 3) d
f−
d
∂f ∂f
= (2, 3) × cos(75◦ ) + (2, 3) × sin(75◦ )
∂x ∂y
2 2
= 4 x y e(x y) × cos(75◦ ) + 2 x2 e(x y) × sin(75◦ )
= 24 e(4×3) × 0.25 + 8 e(4×3) × 0.96
= 6 e(12) + 7.70 e(12)
= 13.70 e(12)

Chapitre2 Algorithmes d’optimisation 53

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

Annexe B
Codage binaire
Dans ce système de numération binaire, on utilise la base 2. En prenant par exemple le nombre 55, celui-ci
se décompose en : 55 = 32 + 16 + 4 + 2 + 1.

55 = 1 × 32 + 1 × 16 + 1 × 4 + 1 × 2 + 1 × 1
55 = 1 × 25 + 1 × 24 + 1 × 22 + 1 × 21 + 1 × 20
55 = 1 × 25 + 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20
55 = 110111

On utilise également la notation 55(10) = 110111(2) . Il est possible d’arriver au même résultat, en procédant
par des divisions successives du nombre 55 suivant la base 2. La condition d’arrêt correspond à un quotient
nul, ensuite on remonte les restes des divisions, selon :
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

On obtient 55(10) = 110111(2) (de la droite vers la gauche). On peut proposer l’algorithme ci-dessous pour
transformer un nombre de la base décimale, par exemple le nombre 125, vers la base binaire.

%%%%%%%%%%%%%%%%%␣CONVERSION␣DECIMAL␣VERS␣LE␣BINAIRE␣%%%%%%%%%%%%%%%%
clc␣;␣clear␣all␣;
%␣Samir␣KENOUCHE␣-␣le␣09/08/2019

decNumber␣=␣125␣;␣base␣=␣2␣;␣binNumber␣=␣[];
quot␣=␣1␣;

while␣quot␣˜=␣0

␣␣␣␣quot␣=␣floor(decNumber/base)␣;␣reste␣=␣decNumber␣-␣quot*base␣␣;
␣␣␣␣decNumber␣=␣floor(decNumber/base);
␣␣␣␣binNumber␣=␣[reste␣binNumber]␣;

end

binNumber

Ce script renvoie le résultat suivant binNumber = 1111101.

Chapitre2 Algorithmes d’optimisation 54

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

On retrouve ainsi le même résultat 1255(10) = 1111101(2) . À l’inverse, la conversion du système binaire vers
le système décimal se fera, suivant :

110111(2) = 1 × 2(6−1) + 1 × 2(6−2) + 0 × 2(6−3) + 1 × 2(6−4) + 1 × 2(6−5) + 1 × 2(6−6) .

110111(2) = 1 × 25 + 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20 .
110111(2) = 32 + 16 + 0 + 4 + 2 + 1 = 55(10)

Cette conversion est implémentée dans le script Matlabs ci-dessous :

%%%%%%%%%%%%%%%%%␣CONVERSION␣BINAIRE␣VERS␣LE␣DECIMAL␣%%%%%%%%%%%%%%%%
clc␣;␣clear␣all␣;
%␣Samir␣KENOUCHE␣-␣le␣09/08/2019
Cours complet est disponible sur mon site web : http://sites.univ-biskra.dz/kenouche/

binNumber␣=␣[1␣1␣0␣1␣1␣1]␣;␣base␣=␣2␣;␣decNumber␣=␣0␣;

for␣i␣=␣1␣:␣numel(binNumber)

␣␣␣decNumber␣=␣decNumber␣+␣binNumber(i)*baseˆ(numel(binNumber)␣-␣i)␣;
end

decNumber

Pour la conversion de nombres fractionnaires on écrira :

01101.010(2) = 0 × 24 + 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 + 0 × 2−1 + 1 × 2−2 + 0 × 2−3

01101, 010(2) = 0 × 16 + 1 × 8 + 1 × 4 + 0 × 2 + 1 × 1 + 0 × 0.5 + 1 × 0.25 + 0 × 0.12
01101.010(2) = 13.25(10)

Pour la conversion d’un nombre fractionnaire d’un système décimal vers le binaire, on procèdera comme suit :
?
55.8625(10) = xxxxxx(2)

On commence d’abord par écrire la partie entière en binaire : 55(10) = 110111(2) . Ensuite on multiplie par
2 la partie fractionnaire :

0.8625 × 2 = 1.725 = 1 + 0.725

0.7250 × 2 = 1.450 = 1 + 0.450

Chapitre2 Algorithmes d’optimisation 55

M. Samir KENOUCHE

MASTER PHYSIQUE - Toutes options confondues

0.4500 × 2 = 0.900 = 0 + 0.900
0.9000 × 2 = 1.800 = 1 + 0.800
0.8000 × 2 = 1.600 = 1 + 0.600 ...

À partir de cet exemple, on note que la partie entière est codée, par des divisions successives par 2, sur
un nombre donné de bits. La partie fractionnaire est codée sur un nombre donné de bits en multipliant
successivement par 2 jusqu’à ce que la partie fractionnaire soit nulle ou le nombre de bits considéré est atteint.
Cette conversion donne :

55.8625(10) = 110111.11011(2) = 11011.111011(2) 21

Chapitre2 Algorithmes d’optimisation 56

Vous aimerez peut-être aussi

Algorithmes d'optimisation en physique
Pas encore d'évaluation
Algorithmes d'optimisation en physique
43 pages
Problèmes d'optimisation mathématique
Pas encore d'évaluation
Problèmes d'optimisation mathématique
4 pages
Introduction à l'optimisation
Pas encore d'évaluation
Introduction à l'optimisation
39 pages
Résolution d'équations non-linéaires
Pas encore d'évaluation
Résolution d'équations non-linéaires
25 pages
Algorithmes d'Optimisation Sans Contraintes
Pas encore d'évaluation
Algorithmes d'Optimisation Sans Contraintes
11 pages
Optimisation Numérique L3 Paris-Dauphine
Pas encore d'évaluation
Optimisation Numérique L3 Paris-Dauphine
78 pages
Polyao 101
Pas encore d'évaluation
Polyao 101
109 pages
Cours Optimisation Lafitte
Pas encore d'évaluation
Cours Optimisation Lafitte
129 pages
Optimisation Non Linéaire Sans Contraintes
Pas encore d'évaluation
Optimisation Non Linéaire Sans Contraintes
14 pages
Optimisation Numerique
Pas encore d'évaluation
Optimisation Numerique
29 pages
Techniques d'optimisation mathématique
Pas encore d'évaluation
Techniques d'optimisation mathématique
16 pages
Algorithmes d'Optimisation Différentiable
Pas encore d'évaluation
Algorithmes d'Optimisation Différentiable
44 pages
Cours Optimisation
Pas encore d'évaluation
Cours Optimisation
79 pages
Slides Méthodes Numériques Pour L'optimisation Différentiable
Pas encore d'évaluation
Slides Méthodes Numériques Pour L'optimisation Différentiable
44 pages
Professeur Benzine Rachid Cours Optimisation Sans Contraintes Tome1 PDF
Pas encore d'évaluation
Professeur Benzine Rachid Cours Optimisation Sans Contraintes Tome1 PDF
153 pages
Algorithme de Region de Confiance
Pas encore d'évaluation
Algorithme de Region de Confiance
16 pages
Optimisation Numérique Version Temporaire
Pas encore d'évaluation
Optimisation Numérique Version Temporaire
52 pages
Algorithmes d'optimisation non-linéaire
Pas encore d'évaluation
Algorithmes d'optimisation non-linéaire
18 pages
Cours Optimisation MEN MIET
Pas encore d'évaluation
Cours Optimisation MEN MIET
54 pages
Poly GMM4
Pas encore d'évaluation
Poly GMM4
106 pages
Optimisation Mathématique: Avec Applications en Imagerie
Pas encore d'évaluation
Optimisation Mathématique: Avec Applications en Imagerie
399 pages
Opt PDF
100% (1)
Opt PDF
395 pages
Chapitres 1-2-3 Cours Optimisation Sans Contraintes
100% (1)
Chapitres 1-2-3 Cours Optimisation Sans Contraintes
43 pages
Convexité et convergence de BFGS
Pas encore d'évaluation
Convexité et convergence de BFGS
45 pages
Optimisation Cours
Pas encore d'évaluation
Optimisation Cours
55 pages
Programmation Non Linéaire
100% (1)
Programmation Non Linéaire
251 pages
Optimisation Convexe de Fonctions Non Linéaires
Pas encore d'évaluation
Optimisation Convexe de Fonctions Non Linéaires
27 pages
Cours sur l'Optimisation sans Contrainte
Pas encore d'évaluation
Cours sur l'Optimisation sans Contrainte
55 pages
Optimisation sans contraintes en mathématiques
Pas encore d'évaluation
Optimisation sans contraintes en mathématiques
26 pages
Introduction À L'optimisation Numérique
100% (1)
Introduction À L'optimisation Numérique
43 pages
Chapitre II
Pas encore d'évaluation
Chapitre II
11 pages
Cours Optim NL
Pas encore d'évaluation
Cours Optim NL
69 pages
Optimisation Déterministe avec Contraintes
Pas encore d'évaluation
Optimisation Déterministe avec Contraintes
19 pages
Polycopi Cours Optimisation Version 2021
Pas encore d'évaluation
Polycopi Cours Optimisation Version 2021
171 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
45 pages
Techniques D'optimisation Cours Complet
Pas encore d'évaluation
Techniques D'optimisation Cours Complet
28 pages
Initiation à l'optimisation mathématique
Pas encore d'évaluation
Initiation à l'optimisation mathématique
8 pages
Introduction à l'Optimisation Numérique
Pas encore d'évaluation
Introduction à l'Optimisation Numérique
60 pages
Introduction à l'optimisation numérique
Pas encore d'évaluation
Introduction à l'optimisation numérique
52 pages
2 Optimisation Non Linéaire Sans Contraintes 2021
100% (1)
2 Optimisation Non Linéaire Sans Contraintes 2021
55 pages
CoursOptimisation CH2 (1371)
Pas encore d'évaluation
CoursOptimisation CH2 (1371)
19 pages
Partie Optimisation 2024-2025
Pas encore d'évaluation
Partie Optimisation 2024-2025
27 pages
Analyse Numérique Et Optimisation
Pas encore d'évaluation
Analyse Numérique Et Optimisation
57 pages
Opti Algo
Pas encore d'évaluation
Opti Algo
50 pages
Optimisation en apprentissage automatique
Pas encore d'évaluation
Optimisation en apprentissage automatique
64 pages
Optimisation Différentiable Convexe : Concepts et Méthodes
Pas encore d'évaluation
Optimisation Différentiable Convexe : Concepts et Méthodes
42 pages
Optimisation: Algorithmes et Méthodes
Pas encore d'évaluation
Optimisation: Algorithmes et Méthodes
27 pages
Optimisation Différentiable : Méthodes et Conditions
Pas encore d'évaluation
Optimisation Différentiable : Méthodes et Conditions
42 pages
Cours et exercices d'optimisation
Pas encore d'évaluation
Cours et exercices d'optimisation
124 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
12 pages
Méthodes de descente en optimisation
Pas encore d'évaluation
Méthodes de descente en optimisation
8 pages
Transp Optim 2018
Pas encore d'évaluation
Transp Optim 2018
38 pages
Optimisation Non-Linéaire L3
Pas encore d'évaluation
Optimisation Non-Linéaire L3
53 pages
Optimisation non linéaire : Méthodes et Algorithmes
Pas encore d'évaluation
Optimisation non linéaire : Méthodes et Algorithmes
78 pages
Méthodes d'Optimisation des Algorithmes
Pas encore d'évaluation
Méthodes d'Optimisation des Algorithmes
17 pages
Universite Montpellier 2 - Cours DOptimisation Numerique
Pas encore d'évaluation
Universite Montpellier 2 - Cours DOptimisation Numerique
71 pages
MNO2017
Pas encore d'évaluation
MNO2017
38 pages
Polycopié Analyse Des Données
Pas encore d'évaluation
Polycopié Analyse Des Données
141 pages
Rayon spectral et opérateurs auto-adjoints
Pas encore d'évaluation
Rayon spectral et opérateurs auto-adjoints
5 pages
TD2 Correction
Pas encore d'évaluation
TD2 Correction
10 pages
Théorèmes d'Intégration et Continuité
Pas encore d'évaluation
Théorèmes d'Intégration et Continuité
4 pages
Demande Autorisation Soutenance Thèse
Pas encore d'évaluation
Demande Autorisation Soutenance Thèse
1 page
Espaces de Banach, Hilbert et Sobolev
Pas encore d'évaluation
Espaces de Banach, Hilbert et Sobolev
39 pages
Coercivité et inégalités de Poincaré en H1
Pas encore d'évaluation
Coercivité et inégalités de Poincaré en H1
11 pages
Le béton: clé du développement ivoirien
Pas encore d'évaluation
Le béton: clé du développement ivoirien
10 pages
Équations et Contrôle du Système Électrique
Pas encore d'évaluation
Équations et Contrôle du Système Électrique
4 pages
Université Catholique Au Congo: Sujet
Pas encore d'évaluation
Université Catholique Au Congo: Sujet
72 pages
TD COMPRESSEUR e
Pas encore d'évaluation
TD COMPRESSEUR e
8 pages
Statistiques à Deux Variables
Pas encore d'évaluation
Statistiques à Deux Variables
5 pages
Regles Realisation Branchement Collectif
Pas encore d'évaluation
Regles Realisation Branchement Collectif
15 pages
Cours 4
Pas encore d'évaluation
Cours 4
75 pages
Utilisation Extincteurs
Pas encore d'évaluation
Utilisation Extincteurs
11 pages
LBY Système D'information TTI Eval 2+corrigé
Pas encore d'évaluation
LBY Système D'information TTI Eval 2+corrigé
4 pages
28 Messages Pour FLIRTER Avec Un Homme (CHAPITRE GRATUIT)
100% (1)
28 Messages Pour FLIRTER Avec Un Homme (CHAPITRE GRATUIT)
18 pages
Vaccination Proof
Pas encore d'évaluation
Vaccination Proof
2 pages
CV 1 Page
Pas encore d'évaluation
CV 1 Page
1 page
FR J01.300.1 Edel 150 Air Manuel
Pas encore d'évaluation
FR J01.300.1 Edel 150 Air Manuel
36 pages
Aqa Classic
Pas encore d'évaluation
Aqa Classic
4 pages
Initiation Covadis-Mise A Jour
Pas encore d'évaluation
Initiation Covadis-Mise A Jour
28 pages
Cps Merja
Pas encore d'évaluation
Cps Merja
98 pages
Gestion D'un Parking de Stationnement de Véhicules: Nbplibres
Pas encore d'évaluation
Gestion D'un Parking de Stationnement de Véhicules: Nbplibres
6 pages
Les Ascenseurs: Et Les Escaliers Mécaniques
Pas encore d'évaluation
Les Ascenseurs: Et Les Escaliers Mécaniques
9 pages
King Oil Tools Product Catalog
Pas encore d'évaluation
King Oil Tools Product Catalog
48 pages
Plan d'électricité et de masse R+2
Pas encore d'évaluation
Plan d'électricité et de masse R+2
1 page
Interfacage 0858809001316177433
Pas encore d'évaluation
Interfacage 0858809001316177433
7 pages
3-Cours VPN IPSEC
100% (1)
3-Cours VPN IPSEC
94 pages
Chapitre 1 Temporaire PDF
Pas encore d'évaluation
Chapitre 1 Temporaire PDF
5 pages
Simulation Électrique avec VoltaSim
Pas encore d'évaluation
Simulation Électrique avec VoltaSim
19 pages
CV ST
Pas encore d'évaluation
CV ST
2 pages
Optimisation Durable des Livraisons
Pas encore d'évaluation
Optimisation Durable des Livraisons
3 pages
Vases D Expansion Flexcon
Pas encore d'évaluation
Vases D Expansion Flexcon
24 pages
Fonctionnement et avantages de la pompe triplex
Pas encore d'évaluation
Fonctionnement et avantages de la pompe triplex
14 pages
Facteurs influençant l'usage du charbon à Madagascar
Pas encore d'évaluation
Facteurs influençant l'usage du charbon à Madagascar
21 pages
Redresseurs : Convertisseurs AC-DC en GE
Pas encore d'évaluation
Redresseurs : Convertisseurs AC-DC en GE
13 pages

Chapitre 2

Transféré par

Chapitre 2

Transféré par

Chapitre2 Algorithmes d’optimisation

MASTER PHYSIQUE - Toutes options confondues

Table des matières

III Algorithmes de descente de gradient 18

III-C Méthode de gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

V Travaux pratiques avec des fonctions Matlab prédéfinies 34

Annexe A : Dérivée directionnelle 52

Annexe B : Codage binaire 54

L Es algorithmes d’optimisation sans ou sous contraintes (unconstrained and constrained problem en

X̂ ∈ argminf (X) (1)

MASTER PHYSIQUE - Toutes options confondues

lim k X (k) − X ∗ k= 0 (2)

e(k) =k X (k) − X ∗ k tel que ∇f (X ∗ ) = 0 (3)

k e(k+1) k≈ A k e(k) kp =⇒ log k e(k+1) k≈ p log k e(k) k + cste (4)

Chapitre2 Algorithmes d’optimisation 12

MASTER PHYSIQUE - Toutes options confondues

k X (k+1) − X (k) k <  (8)

k ∇f (X (k) ) k <  (9)

II. Algorithme de Newton

Arg maxf (x) ⇔ Arg min(−f (x)) (11)

MASTER PHYSIQUE - Toutes options confondues

min{PX (k) (X + U )} ⇐⇒ ∇PX (k) (X + U ) = 0 (14)

∇PX (k) (X + U ) = ∇f (X (k) ) + ∇2 f (X (k) ) U = 0 (15)

On calcule alors un nouveau point, X (k+1) , qui minimise PX (k) soit :

X (k+1) = X (k) − Hf (X (k) )−1 f (X (k) ) (19)

Algorithm 1 Algorithme de Newton

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Calcul du gradient Gk ←− −∇f (X (k) )

Appliquons le schéma numérique (19) à la fonction-objectif ci-dessous.

Chapitre2 Algorithmes d’optimisation 14

MASTER PHYSIQUE - Toutes options confondues

1) Trouver analytiquement l’optimum de la fonction-objectif.

Chapitre2 Algorithmes d’optimisation 15

MASTER PHYSIQUE - Toutes options confondues

lim k X (k) − X ∗ k = 0 (21)

Ce critère s’énonce aussi,

∀ > 0, ∃ η tel que k>η (ou η()) ⇒ k X (k) − X ∗ k ≤ 

k f (X (k) ) − f (X (k−1) ) k ≤ q k X (k) − X (k−1) k

⇒ k X (k+1) − X (k) k ≤ q k X (k) − X (k−1) k (22)

D’un autre côté, nous pouvons écrire

k X (k) − X (k−1) k ≤ q k X (k−1) − X (k−2) k (23)

⇒ k X (k+1) − X (k) k ≤ q 2 k X (k−1) − X (k−2) k (24)

⇒ k X (k+1) − X (k) k ≤ q k k X (1) − X (0) k (25)

Chapitre2 Algorithmes d’optimisation 16

MASTER PHYSIQUE - Toutes options confondues

Algorithm 2 Algorithme de Quasi-Newton

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Calcul du gradient Gk ←− −∇f (X (k) )

La tolérance considérée est  = 10−5 . Ci-dessous, le script Matlabr

Chapitre2 Algorithmes d’optimisation 17

MASTER PHYSIQUE - Toutes options confondues

III. Algorithmes de descente de gradient

Chapitre2 Algorithmes d’optimisation 18

MASTER PHYSIQUE - Toutes options confondues

∇f (x0 , y0 ) · P~0 P = 0 (29)

f (x0 + a t, y0 + b t) = f (x(t), y(t)) = 0 (31)

MASTER PHYSIQUE - Toutes options confondues

A. Méthode de gradient à pas fixe

f (xk+1 ) < f (xk ) (36)

Figure 1: Dérivée directionnelle dans la direction d~k .

Compte tenu de l’Eq. (92) (voir l’annexe), à une dimension on obtient :

Comme précédemment, nous avons

D’un autre côté,

D’où le schéma numérique de l’algorithme de descente de gradient :

x(k+1) = x(k) + λ dk = x(k) − λ∇f (x(k) ), λ>0 (39)

Chapitre2 Algorithmes d’optimisation 20

MASTER PHYSIQUE - Toutes options confondues

f (xk+1 ) < f (xk ) ⇔ f (x(k) − λ∇f (x(k) ) < f (xk ) (40)

Algorithm 3 Algorithme de descente de gradient à pas fixe

1. Tant que critère d’arrêt n’est pas vérifié faire :

2. Direction de descente dk ←− −∇f (X (k) )

f (x) = 4 x2 + ex avec ∇f (x) = 8 x + ex

x(1) = 1.500000 − 0.02 ∇f (1.500000) = 1.170366

|x(30) − x(29) | = 8.5000 × 10−4 < 

Chapitre2 Algorithmes d’optimisation 21

L’algorithme converge vers la solution x∗ = −0.10781 correspondant au minimum de la fonction-objectif

k X (k+1) − X (k) k < (8)

k ∇f (X (k) ) k < (9)

∀ > 0, ∃ η tel que k>η (ou η()) ⇒ k X (k) − X ∗ k ≤

La tolérance considérée est = 10−5 . Ci-dessous, le script Matlabr

|x(30) − x(29) | = 8.5000 × 10−4 <