TD - Optimisation
TD - Optimisation
TD - Optimisation
Exercice 4. Soit f : Rn → R une fonction convexe. Soit x ∈ Rn une combinaison convexe des points
x1 , . . . , xm de dom(f ). Montrer que
f (x) ≤ max f (xk )
1≤k≤m
Exercice 5. Montrer qu’une fonction f : Rn → R est convexe si et seulement si pour tout (x, y) ∈
Rn × Rn et β ≥ 0 on a
f (y + β(y − x)) ≥ f (y) + β(f (y) − f (x)).
1
Exercice 6. 1) Étudier la convexité/concavité de la fonction x 7→ 1+ex
sur R.
2) En déduire que pour tous x1 . . . xn ≥ 1, on a
n
X 1 n
≥ √ (on pourra appliquer Jensen aux points yk = ln(xk )).
k=1 1 + xk 1 + x1 · · · xn
n
4) On suppose que f est deux fois différentiable. Montrer g est deux fois différentiable et pour
x ∈ Rn on a
Hg (x) = AT · Hf (Ax + b) · A.
Exercice 11. 1) Si f1 , . . . , fk sont des fonctions convexes définies sur un même ensemble convexe
n
C ⊂ R et si α1 , . . . , αk sont des réels positifs alors α1 f1 + · · ·+ αk fk est une fonction convexe.
De plus, si l’une des fonctions fi est strictement convexe alors α1 f1 +· · ·+αk fk est strictement
convexe.
2) Soient f, g : R → R deux fonctions convexes. On suppose en plus que la fonction g est
croissante (resp. strictement croissante). Démontrer que la fonction g ◦ f est convexe (resp.
strictement convexe).
3) Soit I un intervalle de R et f : I →]0, ∞[. On dit que f est logarithmiquement convexe si
ln(f ) est convexe. Démontrer que si f est logarithmiquement convexe, alors f est convexe. La
réciproque est-elle vraie ? (On pourra par exemple considérer la fonction f (x) = x)
4) Soit I un intervalle de R et f : I →]0, ∞[. On suppose que pour tout α > 0, f α est convexe.
4-1) Pour t ∈ [0, 1], x, y ∈ I et α ≥ 0 on pose
u(α) = exp(α ln(f (tx + (1 − t)y))) et v(α) = t exp(α ln(f (x))) + (1 − t) exp(α ln(f (y))).
Exercice 12. Soit f : Rn → R une fonction à la fois convexe et concave, c’est à dire telle que
Le but de cet exercice est de montrer que f est une fonction affine( i.e., il existe a ∈ Rn et b ∈ R tels
que f (x) = ha, xi + b). On pose g(x) = f (x) − f (0).
1) Montrer que g est impaire : ∀x ∈ Rn , g(−x) = −g(x).
2) Montrer que g est 1-homogène : ∀x ∈ Rn , ∀λ > 0, f (λx) = λf (x).
3) Montrer que g est linéaire et conclure.
Exercice 13. Soit f une fonction convexe, s.c.i et différentiable sur son domaine. Montrer que
B/ Montrer que si l’on suppose f définie et de classe C 2 sur Rn alors f est µ-fortement convexe sur
Rn si et seulement si
hHf (x)h, hi ≥ µkhk2 ∀x ∈ Rn , ∀h ∈ Rn .
II - Optimisation sans contrainte
Exercice 16. Soient les fonctions f , g et h définies sur R2 par f (x, y) = x4 + y 4 , g(x, y) = (x − y)2
et h = f − 2g.
1) Montrer que les fonctions f et g sont convexes sur R2 , mais que h = f − 2g n’est ni convexe
ni concave sur R2 .
2) La fonction h admet-elle un maximum ou un minimum sur R2 ?
3) Déterminer les points critiques de h et préciser leur nature.
Exercice 17. Soit f la fonction définie sur R3 par f (x, y, z) = x4 − 2x2 y + 2y 2 − 2yz + 2z 2 − 4z + 5.
1) Déterminer les points critiques de f sur R3 .
2) Montrer que l’expression de f (x, y, z) peut s’écrire sous forme d’une somme de carrés.
3) En déduire les extréma de f sur R3 .
1) Montrer qu’il existe (α, β) ∈ R2+ (et les déterminer) tels que
hAx, xi
f (x) = ,
kxk2
6) En déduire que tous les points critiques qui ne sont pas solution d’un des problèmes ci-dessus
sont des points-selles.
Exercice 21. Partie A. Soit f : Rn → R une fonction convexe et deux fois différentiable. On
suppose qu’il existe L > 0 tel que
L
f (y) ≤ f (x) + h∇f (x), y − xi + ky − xk2 ∀x, y ∈ Rn .
2
2) Pour x fixé dans Rn on définit une fonction g de Rn dans R par
L
g(y) = f (x) + h∇f (x), y − xi + ky − xk2 (y ∈ Rn ).
2
Montrer que g admet un unique minimum ȳ sur Rn et calculer la valeur minimale de g.
3) On suppose que f admet un minimum global en x̄. Montrer que
1
f (x̄) ≤ f (x) − k∇f (x)k2 ∀x ∈ Rn .
2L
Partie B. Soit f : Rn → R une fonction convexe et deux fois différentiable. On suppose qu’il
existe µ > 0 tel que
∀x, h ∈ Rn , hHf (x)h, hi ≥ µkhk2 .
1) Montrer que f est µ-fortement convexe et coercive, et en déduire que f admet un unique
minimum global x̄.
2) Montrer que pour tout x ∈ Rn
1 2
f (x̄) ≥ f (x) − k∇f (x)k2 et kx − x̄k ≤ k∇f (x)k.
2µ µ
Partie C. Soit f : Rn → R une fonction convexe et deux fois différentiable. On suppose qu’il
existe µ > 0 et L > 0 (avec 0 < µ < L) tels que
1) Montrer que f admet un minimum global x̄ qui satisfait les inégalités suivantes :
2 2
(f (x) − f (x̄)) ≤ kx − x̄k2 ≤ (f (x) − f (x̄)) ∀x ∈ Rn .
µ L
2) On note (xk )k∈N une suite produite par un algorithme de descente. Déduire de ce qui précède
que la suite (f (xk ))k∈N converge vers f (x̄) si et seulement si la suite (xk )k∈N converge vers
x̄.
Exemple 1. Dans le plan (s, t), on cherche la droite d’équation t = α + βs qui passe par les
points (0, 1), (1, 9), (3, 9), (4, 21).
(1-a) Montrer que si cette droite existait, le vecteur x = (α, β)T serait solution d’un système
linéaire Ax = b ; on donnera explicitement la matrice A et le vecteur b.
(1-b) Montrer qu’une telle droite n’existe pas. Dans la suite du problème on va trouver la droite
qui passe le “plus près” possible de ces quatre points, au sens de la norme euclidienne.
Exemple 2. On cherche maintenant à déterminer les coefficients α, β et γ d’une fonction
linéaire T de R3 dans R, dont on ne connait la valeur qu’en deux points : T (1, 1, 1) = 3
et T (0, 1, 1) = 2.
(2-a) Montrer que les coefficients α, β et γ s’ils existent, satisfont un système linéaire Ax = b ;
on donnera explicitement la matrice A et le vecteur b.
(2-b) Montrer qu’il existe une infinité de solutions au système Ax = b. Dans la suite du
problème on va trouver les coefficients α, β et γ qui donnent un vecteur x de norme
euclidienne minimale.
On considère maintenant une matrice A d’ordre n × m et b ∈ Rn , et on veut résoudre dans
un sens aussi “satisfaisant” que possible le système linéaire
Ax = b, x ∈ Rm (1)
lorsque m 6= n ou lorsque m = n mais que A n’est pas inversible. Soit f la fonction définie de
Rn dans R par f (x) = kAx − bk2 . On cherche à minimiser f ; c’est à dire à trouver x̄ ∈ Rn
tel que
f (x̄) = min{f (x), x ∈ Rn }. (2)
3) Soit E un sous espace vectoriel de Rm tel que Rm = E ⊕ KerA.
(3-a) Montrer que f (z) → +∞ lorsque kzk → +∞ avec z ∈ E.
(3-b) Montrer que la fonction f est strictement convexe de E dans R.
(3-c) En déduire qu’il existe un unique z̄ ∈ E tel que
4 Soit Xb = {z̄ + y, y ∈ KerA} où z̄ est défini à la question précédente. Montrer que Xb est
égal à l’ensemble des solutions du problème de minimisation (2).
5 Montrer que x ∈ Xb ⇐⇒ At Ax = At b. On appelle système d’équations normales le système
At Ax = At b.
6 Écrire les équations normales dans le cas de l’exemple 1, et en déduire l’équation de la droite
obtenue par moindres carrés, i.e. par résolution de (2). Tracer les quatre points donnés à la
question 1 et la droite obtenue sur un graphique.
7 Écrire les équations normales dans le cas de l’exemple 2, et vérifier que le système obtenu
n’est pas inversible.
8 Pour y ∈ KerA on pose g(y) = ky + z̄k2 , où z̄ est défini à la question (3-c). Montrer qu’il
existe un unique ȳ ∈ KerA tel que g(ȳ) ≤ g(y) pour tout y ∈ KerA. En déduire qu ’il existe
un unique x̄ ∈ Xb tel que kx̄k2 ≤ kxk pour tout x ∈ Xb . On appelle x̄ pseudo-solution de (2).
9) Calculer x̄ dans le cas des exemples 1 et 2.
Dans la suite du problème, on considère, pour ε > 0 fixé, une version pénalisée du problème
(2). On introduit la fonction fε de Rm dans R, définie par
1
fε (x) = kxk2 + kAt Ax − At bk2 ,
ε
et on cherche à trouver xε solution du problème de minimisation suivant
Exercice 23. Un fabricant de postes de télévision produit q postes par semaine à un coût total de
C = 6q 2 + 80q + 5000. C’est un monopoleur et son prix s’exprime par la relation p = 1080 − 4q.
Montrons que le bénéfice net maximum est atteint lorsque la production est de 50 postes par semaine.
Exercice 24. Une firme aéronautique fabrique des avions qu’elle vend sur deux marchés étrangers.
Soit q1 le nombre d’avions vendus sur le premier marché et q2 le nombre d’avions vendus sur le
deuxième marché. Les fonctions de demande dans les deux marchés respectifs sont :
p1 = 60 − 2q1 et p2 = 80 − 4q2 ,
p1 et p2 sont les deux prix de vente. La fonction de coût total de la firme est C = 50 + 40q. Trouver
le nombre d’avions que la firme doit vendre sur chaque marché pour maximiser son bénéfice.
Exercice 25. A) Soient a et b deux constantes réelles. On considère les fonctions f et g définies
sur R par
f (x) = 8x − 2x2 + b2 , g(y) = 8y − a2 − 2y 2.
1) Déterminer les extrema de chacune de ces fonctions sur R.
2) On considère ensuite la fonction h définie sur R2 par :
2) Dans un deuxième temps, les deux firmes fusionnent. Elle constituent deux divisions d’une
même entreprise. Il n’y a plus qu’un centre de décision qui essaie de maximiser son profit
en agissant sur les variables qu’il contrôle sans modifier les conditions techniques de pro-
duction des deux divisions.
Calculer les quantités optimales qu’il demande à chacune des deux divisions de produire
pour maximiser le profit. La fusion est-elle souhaitable ? Pourquoi ?
Exercice 26. Une firme monopolistique produit un certain bien. Le coût total de sa production est
représenté par la fonction :
C = 2I 2 + 5q 2 − 20q + 400,
où q représente les unités produites et I un indice de qualité du produit (par exemple le degré de
raffinage du produit). Le prix que la firme peut exiger sur le marché est fonction de l’indice de
qualité :
p = 100 − 3q + 4I.
1) Calculer la recette totale de la firme.
2) Trouver q et I tels qu’ils maximisent le bénéfice de la firme.
3) Vérifier les conditions de deuxième ordre.
Exercice 27. Une firme (en situation de monopole) produit un unique bien qui peut être vendu à
deux clients a et b. Si la firme produit la quantité Qa d’unités de bien pour le client a, alors celui-ci
est diposé à payer le prix unitaire de 50 − 5Qa . Si la firme produit la quantité Qb d’unités de bien
pour le client b, alors celui-ci est diposé à payer le prix unitaire de 100 − 10Qb . Le coût pour la firme
de produire Q unités de bien est 90 + 20Q.
1) Que représente la fonction Π définie sur R+ × R+ par
2) Si la firme veut maximiser son profit, quelle quantité de bien doit-elle produire et vendre à
chaque client ? Calculer alors le profit maximal.
Exercice 28. Soit l’ouvert D = {(p, q) ∈ R2 : p > 0, q > 0} de R2 . Soient x et y les quantités
demandées de deux biens X et Y en fonction de leurs prix unitaires p et q. Sur D, on définit les
fonctions de demande f et g par :
1 q−1 p−2 1 q−1 p−2
x = f (p, q) = e e et y = g(p, q) = e e .
pq pq 2
Première partie
1) Montrer que f et g sont de classe C 1 sur D.
2) Calculer les gradients des fonctions f et g en tout point de D.
3) Donner les élasticités relatives des fonctions f et g en tout point de D.
On suppose dans la suite de cette partie que les prix unitaires initiaux valent p0 = 2 et q0 = 1.
4) On suppose que q est fixé à la valeur 1. Quelle variation relative doit-on attribuer à p à partir
de 2 pour que la demande en bien X augmente de 5% ? Quelle sera alors la variation relative
correspondante de la demande en bien Y ? Ce modèle est-il raisonnable ?
5) On suppose que p augmente de 5% à partir de 2 et que q diminue de 3% à partir de 1. Quelles
sont les variations relatives correspondantes des demandes en bien X et Y ?
6) On observe maintenant une augmentation de la demande en bien X de 2%, la demande en
bien Y restant constante. Quelles variations relatives des prix ont provoqué ce changement ?
Deuxième partie On définit le chiffre d’affaires par
Exercice 30. Soit f : R3 → R donnée par f (x, y, z) = xy + yz + zx. Trouver la valeur maximale
et la valeur minimale de f sur K = {(x, y, z) ∈ R3 : x2 + y 2 + z 2 ≤ 1}, après avoir prouvé qu’elles
existent.
Exercice 32.
Exercice 33. 1) Trouver les extrema de la fonction objectif f (x, y) = 5x2 + 6y 2 − xy sous la
contrainte x + 2y = 24.
2) Un consommateur dépense 24 XAF pour l’achat de deux biens : x et y. Les prix de x et de y
sont respectivement de 1 XAF et de 2 XAF. La fonction d’utilité du consommateur est donnée
par U = 5x2 + 6y 2 − xy. Combien d’unités de chaque bien doit-il consommer pour maximiser
son utilité ?
Exercice 34. Déterminer les points les plus proches et les plus éloignés de l’origine (s’ils existent)
de la courbe d’équation x6 + y 6 = 1. Tracer cette courbe pour corroborer vos résultats.
Exercice 35. Une entreprise fabrique deux modèles de petites voitures, les modèles X et Y . Le
modèle X, le plus abordable, se vend à 1 euro pièce. Quant au modèle Y , beaucoup plus sophistiqué,
il se vend à 3 euro. Le coût de fabrication, exprimé en euro, est donné par la fonction suivante :
où x est le nombre de petites voitures du modèle X et y est le nombre de petites voitures du modèle
Y . On suppose que les jouets fabriqués sont tous écoulés sur le marché.
1) Pour tout (x, y) ∈ (R∗+ )2 , donner P (x, y), le profit de l’entreprise lorsqu’elle a vendu x jouets
de modèle X et y jouets de modèle Y .
2) La fonction P est elle convexe sur (R∗+ )2 ? Concave sur (R∗+ )2 ?
3) La capacité de production de l’entreprise est au total 20 jouets par jour. En supposant que
l’entreprise tourne à plein régime, trouver la répartition maximale entre les modèles de type
X et Y permettant de maximiser le profit quotidien. Calculer dans ce cas le profit réalisé.
4) Le conseil d’administration de l’entreprise s’interroge sur la pertinence de vouloir produire à
pleine capacité. Il se demande s’il ne peut pas augmenter le profit en produisant autrement.
Pouvez-vous aider le conseil d’administration ?
Exercice 36. Une entreprise fabrique trois types de machines : x1 , x2 et x3 . La fonction de coût
conjointe C(x1 , x2 , x3 ) est :
C(x1 , x2 , x3 ) = 4x21 + 2x22 + x23 − 2x1 x2 + x2 x3 − 30x2 − 30x3 .
Combien de machines de chaque type l’entreprise doit-elle fabriquer pour minimiser son coût s’il lui
faut un total de 400 machines ?
Exercice 38. Une firme produit des appareils dans deux usines différentes. Les coûts de production
respectifs pour les deux usines sont :
C1 = 200 + 6q1 + 0.03q12 , C2 = 150 + 10q2 + 0.02q22 .
où q1 et q2 représentent le nombre d’appareils produits dans chaque usine. La firme s’est engagée à
livrer 100 appareils à une entreprise de Yaoundé. Les frais de transport par appareil sont de 4 XAF
pour les livraisons à partir de la première usine et de 2 XAF pour les livraisons à partir de la seconde
usine. Les frais de transport sont supportés par la firme productrice. Calculer le nombre d’appareils
que la firme doit produire dans chaque usine afin de minimiser le coût total (coût de transport y
compris).
Exercice 39. Une firme produit un certain bien qu’elle vend sur le marché au prix unitaire de 8
XAF. La quantité produite (et vendue) est donnée par :
3 1
Q = 8K 8 L 8
où K représente les unités de facteur capital employées et L les unités de facteur travail employées.
3 1
Le revenu de la firme s’élève donc à 8Q = 64K 8 L 8 . Le coût de production de cette firme est donné
par C = 12K + 4L.
1) Trouver les quantités de K et L que la firme doit employer afin de maximiser son bénéfice.
2) La firme constate que la politique de maximisation du bénéfice ne lui assure pas une part de
marché suffisante. Elle décide en conséquence d’adopter la politique de maximisation de la
quantité vendue sous réserve d’un bénéfice minimal égal à 48 XAF.
i) Formuler explicitement le problème de maximisation sous contrainte.
ii) Montrer que dans la solution optimale, la combinaison optimale des facteurs (c’est-à-dire
leurs proportions) reste la même que dans le problème de maximisation du bénéfice.
iii) Donner la solution complète pour K, L et Q.
pX = 2, pY = 0.5, pZ = 1.
L’utilité que ces vêtements vous procurent pendant votre voyage est mesurée par la fonction :
U = X 2 Y Z.