Université Moulay Ismail Année Universitaire : 2024-2025

ENSAM Meknès Master SDII

Série de TD & TP
Module : Méthodes d’optimisation

Exercice 1
Déterminer et établir la nature des points critiques des fonctions f : R2 → R définies par :

1. f (x, y) = x2 + xy + y 2 + y

2. f (x, y) = xy − 2x − 2y − x2 − y 2

3. f (x, y) = y 3 + 3x2 y − 6x2 − 6y 2 + 2

4. f (x, y) = x3 + y 3 − 3xy + 3

5. f (x, y) = (x − 1)2 + 2y 2

Exercice 2 (Fabrication optimale)

Votre société s’occupe de la fabrication d’une pièce mécanique. Celle-ci dépend de deux paramètres
réels x et y (à priori non-contraints) de la façon suivante : le coût unitaire de fabrication d’une
pièce est égal à
c(x, y) = x2 + 2y 2
tandis que le taux de pièces défectueuses (compris entre 0 et 1) est égal à
1
t(x, y) = .
1 + (xy)2

On cherche à maximiser la rentabilité totale du processus de fabrication. On prendra pour fonction

objectif le coût unitaire moyen d’une pièce non-défectueuse, qui est égal au coût de fabrication
d’une pièce divisé par le taux de pièces non-défectueuses, et on tentera de le simplifier autant que
possible.
Exercice 3 (Optimisation libre)
Si f est une fonction continue d’une seule variable réelle et si f admet deux maxima sur un
intervalle alors il existe un minimum compris entre les deux maxima. Le but de cet exercice est
de montrer que ce résultat ne s’étend pas en deux dimensions.
Considérons la fonction f : R2 → R définie par :

f (x, y) = 4x2 ey − 2x4 − e4y .

Montrer que cette fonction admet deux maxima mais aucun autre point critique.
Exercice 4 (Optimisation sous contrainte)

1. Tracer les courbes de niveau 2, 4, 6, et 8 de la fonction f : (R∗+ )2 → R définie par f (x, y) = xy.
Tracer sur la même figure la courbe d’équation x+y = 4. En déduire si f admet des extrema
sous la contrainte x + y = 4. En cas affirmatif, en établir la nature.

2. Utiliser la méthode des multiplicateurs de Lagrange pour justifier l’étude précédente.

1
Exercice 5 (Production d’une firme)
Une firme produit des appareils dans deux usines différentes. Les coûts totaux de production pour
les deux usines sont respectivement :

C1 (q) = 200 + 6q + 0.03q 2 ,

C2 (q) = 150 + 10q + 0.02q 2 ,
où q représente le nombre d’appareils produits dans l’usine. La firme s’est engagée à livrer 100
appareils à une entreprise. Les frais de transport par appareil sont de 50 Dhs pour les livraisons
à partir de la première usine et de 25 Dhs pour les livraisons à partir de la seconde usine. Les
frais de transport sont supportés par la firme productive. Calculer le nombre d’appareils que doit
produire la firme dans chaque usine afin de minimiser le coût total de production compris le coût
de transport.
Exercice 6 (Méthode du gradient à pas constant)
On veut minimiser la fonctionnelle
1
J(x) = (Ax, x) − (b, x),
2
où b ∈ Rn et A est une matrice réelle symétrique définie positive. Cela revient à résoudre le
système Ax = b. Pour cela, nous allons employer la méthode du gradient à pas constant.
Soit x∗ la solution de ce système. On propose l’algorithme suivant : on se donne un vecteur initial
x(0) , et on calcule la suite d’itérés par l’algorithme

r(k) = b − Ax(k)
x(k+1) = x(k) + αr(k)

où α est une constante réelle donnée.

1. Soit e(k) = x(k) − x∗ , pour k ≥ 0. Donner une relation entre e(k) et e(0) .

2. Montrer que l’algorithme converge si et seulement si

2
0<α<
λn
où λn est la plus grande valeur propre de A.

3. Donner le meilleur choix pour α en fonction des valeurs propres de A. Que concluez-vous?

Exercice 7 (Méthode du gradient à pas optimal)

Soit A ∈ Mn (R) symétrique définie positive et b un vecteur de Rn . On note λi , 1 ≤ i ≤ n, les
valeurs propres de A rangées par ordre croissant:

0 < λ1 ≤ . . . ≤ λn

On définit la fonctionnelle quadratique J par

1
J(x) = Ax · x − b · x
2
où · désigne le produit scalaire usuel de Rn .

2
On considère la méthode itérative suivante pour résoudre du système linéaire Ax = b : on se
donne un point initial x(0) de Rn , on définit le résidu initial r(0) = Ax(0) − b, et tant que le résidu
r(k) à l’ordre k est non nul, on pose

r(k) · r(k)
α(k) =
Ar(k) · r(k)
x(k+1) = x(k) + α(k) r(k)
r(k+1) = b − Ax(k+1)

Bien sûr, si r(k) = 0, alors x(k) est solution du système linéaire.

Dans tout l’exercice, nous ferons l’hypothèse que r(k) ̸= 0.

1. Montrer que J est différentiable et déterminer sa différentielle.

2. Montrer que α(k) est l’unique réel qui minimise sur R la fonction α → J x(k) + αr(k) .



3. Evaluer la différence : J x(k+1) − J x(k) .

4. Montrer que l’on a

(k) 2
(k)


r · r
A−1 r(k+1) · r(k+1) = A−1 r(k) · r(k) − .
Ar(k) · r(k)

5. En déduire que l’on a

A−1 r(k+1) · r(k+1) (λn − λ1 )2
≤ .
A−1 r(k) · r(k) (λn + λ1 )2

Exercice 8 (TP : Méthodes de gradient pour des fonctionnelles quadratiques)

Soit n ∈ N∗ . On considère la matrice A ∈ Mn (R) et le vecteur bn ∈ Rn définis par :
 
4 −2 0 . . . 0
.. 
 −2 4 −2 . 


An = 
 . . . . . . . . .

 et bn = (1, 1, . . . , 1).
 0 0 
 .
 ..

−2 4 −2 
0 . . . 0 −2 4

On cherche à minimiser dans Rn , par différentes méthodes, la fonctionnelle :

1
Jn (x) = (An x, x) − (bn , x) .
2
On appelle donc (Pn ) le problème :

min Jn (x)
(Pn )
x ∈ Rn

1. Programmer en Python la fonctionnelle Jn , et la représenter dans le cas n = 2 sur le pavé

[−10, 10]× [−10, 10].

2. Vérifier numériquement, pour certaines valeurs de n que An est définie positive.

Calculer la solution théorique du problème (Pn ) dans le cas n = 2.

3. Nous allons étudier 3 méthodes de minimisation. Pour chacune de ces études, on demande :
−→ pour le cas n = 2 :

3
 • pour un point de départ x0 , de stocker la liste des xn obtenu, avant que le critère de
convergence soit atteint.
• de tracer sur une courbe les lignes qui relient les xn .

−→ lorsque n prend les valeurs 10, 20, 50, 100 :

• de tester chacune des trois méthodes,

• Enfin, de comparer à l’aide d’un graphique ou d’un tableau, la rapidité de convergence
de chacune de ces méthodes, ainsi que le temps de calcul, suivant les différentes valeurs
prises par n.
(a) La méthode du gradient à pas fixe. Écrire une fonction Python prenant en argu-
ment ρ > 0, un pas fixe et x0 ∈ Rn , un vecteur d’initialisation, afin de mettre en
œuvre l’algorithme du gradient à pas fixe, puis la tester sur Jn dans chacun des
cas ci-dessus. Répondre aux questions initiales.
Expliquer brièvement pourquoi il est important de choisir le pas fixe, ni trop grand,
ni trop petit.

(b) La méthode du gradient à pas optimal.

i. Soient x ∈ Rn , un point, et d ∈ Rn , un vecteur.
Écrire une fonction Python permettant de minimiser, à l’aide de la méthode
de la section dorée, la fonction t 7−→ Jn (x + td) (partie annexe page 6).
ii. Voici l’algorithme du gradient à pas optimal pour la minimisation d’une fonc-
tion f donnée : 

 x0 est donné.
 xn+1 = xn + ρn dn

n n
 d = −∇f (x )
 ρn = min Jn (xn + αdn )


α∈R

Programmer cet algorithme et répondre aux questions initiales. On pourra

utiliser la méthode de la section dorée pour calculer ρn .
(c) La méthode du gradient conjugué dans le cas d’une fonctionnelle quadratique el-
liptique. Soit
f : Rn −→ R
x 7−→ 21 (Ax, x) − (b, x)
où A ∈ Mn (R) est une matrice symétrique définie positive et b est un vecteur de
Rn . Alors, dans ce cas, l’algorithme du gradient conjugué s’écrit:

0 0 0
 x est donné, r = Ax − b et
 d0 = −r0
(rn ,dn )
 xn+1 = xn + ρn dn , ρn = − (Adn ,dn )



 rn+1 = Axn+1 − b
n+1 2
 dn+1 = −rn+1 + βn dn , βn := ∥r 2∥



∥rn ∥

Programmer cet algorithme et répondre aux questions initiales.

Exercice 9 (Facultatif )
On cherche les extrema de la fonction f : R2 → R définie par f (x, y) = x + y sous la contrainte
x2 + y 2 = 1. Faire d’abord une étude des courbes de niveau de f et de leurs intersections avec le
graphe de la contrainte. En déduire les extrema ainsi que leur nature. Vérifier ensuite que cette
étude est correcte en étudiant la nature des points critiques du lagrangien.

4
Exercice 10 (Facultatif )
Une entreprise fabrique deux modèles de vélos de montagne : le modèle X est plus abordable et
se vend 5000 Dhs l’unité, tandis que le modèle Y se vend 10000 Dhs l’unité. Les coûts totaux de
fabrication (en Dhs) sont exprimés par la fonction c(x, y) = 5x2 + 5y 2 − 52 xy + 100000 où x est le
nombre de vélos du modèle X et y est le nombre de vélos du modèle Y , produits mensuellement.
On suppose que chaque vélo produit peut être vendu sur le marché.

1. Écrire (x, y) 7→ p la fonction des profits totaux mensuels.

2. La capacité de production de l’entreprise est de 150 vélos par mois. En supposant que
l’entreprise désire utiliser à pleine capacité son usine, trouver la répartition de la production
mensuelle permettant de maximiser les profits. Prouvez qu’il s’agit bien d’un maximum
absolu et donnez la valeur du profit mensuel.

3. Le patron de l’entreprise s’interroge sur la pertinence de vouloir produire à pleine capacité.

Il se demande si la solution qu’il obtiendrait sans cette contrainte serait plus intéressante.
Aidez-le à répondre à cette question en trouvant la solution qui maximise les profits sans
cette contrainte. Prouvez qu’il s’agit bien d’un maximum absolu et donnez la valeur du
profit mensuel. La solution obtenue est-elle réalisable pour l’entreprise?

Exercice 11 (Facultatif )
Utiliser la méthode des multiplicateurs de Lagrange pour calculer le maximum et le minimum
de la fonction f sous la (les) contrainte(s) indiquée(s) :

1. f (x, y) = x2 + y 2 sous la contrainte xy = 1

2. f (x, y) = 3x + y sous la contrainte x2 + y 2 = 10

3. f (x, y) = y 2 − x2 sous la contrainte 41 x2 + y 2 = 1

4. f (x, y) = exy sous la contrainte x3 + y 3 = 16

5. f (x, y, z) = 2x + 2y + z sous la contrainte x2 + y 2 + z 2 = 9

6. f (x, y, z) = x2 + y 2 + z 2 sous la contrainte x + y + z = 12

7. f (x, y, z, t) = x + y + z + t sous la contrainte x2 + y 2 + z 2 + t2 = 1

8. f (x1 , x2 , . . . , xn ) = ni=1 xi sous la contrainte ni=1 x2i = c

P P

9. f (x, y, z) = x + 2y sous les contraintes x + y + z = 1 et y 2 + z 2 = 4

10. f (x, y, z) = 3x − y − 3z sous les contraintes x + y − z = 0 et x2 + 2z 2 = 1

5
Annexe : Méthode de la section dorée pour la recherche du
pas ρ
Soit q(ρ) la fonction coût que l’on cherche à minimiser. On pourra prendre par exemple

q(ρ) = J(x(k) + ρd(k) )

afin d’appliquer les idées au cas de la méthode de descente. Supposons que l’on connaisse un
intervalle [a; b] contenant le minimum ρ∗ de q et tel que q soit décroissante sur [a; ρ∗ ] et croissante
sur ]ρ∗ ; b] (q est alors appelée une fonction unimodale).
On construit une suite décroissante d’intervalles [ai ; bi ] qui contiennent tous le minimum ρ∗ .
Pour passer de [ai ; bi ] à [ai+1 ; bi+1 ], on procède de la manière suivante. On introduit deux nombres
a′ et b′ de l’intervalle [ai ; bi ] et tels que a′ < b′ . Puis, on calcule les valeurs q(a′ ) et q(b′ ). Trois pos-
sibilités se présentent alors à nous. Si q(a′ ) < q(b′ ), alors, le minimum ρ∗ se trouve nécessairement
à gauche de b′ . Ceci définit alors le nouvel intervalle en posant ai+1 = a′ et bi+1 = b′ . Considérons
maintenant que l’inégalité : q(a′ ) > q(b′ ) est satisfaite. Dans ce second cas, il est évident que le
minimum se trouve cette fois à droite de a′ . On pose alors : ai+1 = a′ et bi+1 = bi . Enfin, le
dernier cas consiste à avoir q(a′ ) = q(b′ ). Alors, le minimum se trouve dans l’intervalle [a′ ; b′ ]. On
se restreint donc à ai+1 = a′ et bi+1 = b′ .
La question suivante se pose : comment choisir a′ et b′ en pratique? En général, on privilégie
deux aspects :

i) on souhaite que le facteur de réduction τ , qui représente le ratio du nouvel intervalle par
rapport au précédent, soit constant,

ii) on désire réutiliser le point qui n’a pas été choisi dans l’itération précédente afin de diminuer
les coûts de calculs.

On peut montrer que la vérification simultanée de ces deux contraintes conduit à un choix
unique des paramètres a′ et b′ . Plus précisément, supposons que q est unimodale. Alors, on obtient
l’algorithme 1 dit de la section dorée, la méthode tirant son nom de la valeur du paramètre τ .
Ici, N max est le nombre maximal d’itérations que l’on se fixe. À cette fin, on doit valider un
critère d’arrêt de la forme : |bi+1 − ai+1 | < ε, où ε est l’erreur (ou tolérance) que l’on se permet
sur la solution ρ∗ du problème.

Algorithm 1 Algorithme de la section dorée

√
1: poser τ = 1+2 5
2: poser a0 = a
3: poser b0 = b
4: for i = 0, . . . , N max do
5: poser a′ = ai + 21 (bi − ai )
6: poser b′ = ai + τ1 (bi − ai )
7: if q(a′ ) < q(b′ ) then
8: poser ai+1 = ai
9: poser bi+1 = b′
10: else if q(a′ ) > q(b′ ) then
11: poser ai+1 = a′
12: poser bi+1 = bi
13: else if q(a′ ) = q(b′ ) then
14: poser ai+1 = a′
15: poser bi+1 = b′