Leçon 1 sur 5
Conditions de Karush-Kuhn-Tucker
Je sais écrire les conditions de Karush-Kuhn-Tucker d'un problème avec contraintes d'égalité et d'inégalité, vérifier une condition de qualification, résoudre le système par l'étude des contraintes actives et interpréter les multiplicateurs comme des prix de sensibilité.
- 1 h 30
- 6 exercices corrigés
- QCM de 6 questions
À la fin de la leçon, vous saurez :
- Écrire le lagrangien et les quatre familles de conditions KKT d'un problème général
- Vérifier une condition de qualification (LICQ, Slater, contraintes affines) et reconnaître un cas où elle échoue
- Utiliser la convexité pour affirmer qu'un point KKT est un minimum global
- Résoudre un problème en énumérant les ensembles de contraintes actives
- Interpréter un multiplicateur comme la sensibilité de la valeur optimale
Avant de commencer : Optimisation 1 (convexité, conditions d'optimalité, multiplicateurs de Lagrange, première approche des conditions KKT).
1Je découvre
Une PME de transformation de fruits de Kindia, que nous appellerons « Kindia Jus », reçoit chaque jour des commandes : environ 3 milliers de litres de jus de mangue et 2 milliers de litres de jus d'ananas. Mais sa presse ne peut traiter que 4 milliers de litres par jour. Impossible de tout livrer.
La gérante, Mme Bangoura, veut une production (x, y) aussi proche que possible des commandes. Son conseiller, étudiant en Mathématiques appliquées, propose de minimiser l'écart quadratique (x-3)2 + (y-2)2 sous les contraintes x + y ≤ 4, x ≥ 0, y ≥ 0.
En Optimisation 1, vous avez traité des contraintes d'égalité avec Lagrange. Ici, les contraintes sont des inégalités : certaines « serrent » à l'optimum, d'autres non, et on ne sait pas d'avance lesquelles. Kindia Jus nous accompagnera pendant tout ce cours.
Comment caractériser rigoureusement l'optimum d'un problème avec contraintes d'inégalité, et quand ces conditions sont-elles nécessaires ou suffisantes ?
2Je comprends
1. Le problème général et le lagrangien
On considère le problème (P), avec f, gi, hj de classe C1 sur ℝn :
minx ∈ ℝn f(x) s.c. gi(x) ≤ 0 (i = 1, …, m), hj(x) = 0 (j = 1, …, p).
L'ensemble admissible est X = {x : gi(x) ≤ 0, hj(x) = 0}. Une contrainte d'inégalité est active en x si gi(x) = 0 ; on note I(x) l'ensemble des indices actifs.
Le lagrangien associe un multiplicateur λi ≥ 0 à chaque inégalité et µj ∈ ℝ à chaque égalité :
L(x, λ, µ) = f(x) + Σi=1m λi gi(x) + Σj=1p µj hj(x).
| Convention | Forme imposée | Signe du multiplicateur |
|---|---|---|
| inégalité | gi(x) ≤ 0 | λi ≥ 0 |
| égalité | hj(x) = 0 | µj de signe quelconque |
| problème de maximisation | on minimise -f | inchangé |
Une contrainte x + 2y ≥ 2 se réécrit donc 2 - x - 2y ≤ 0 avant d'écrire le lagrangien.
2. Les conditions de Karush-Kuhn-Tucker
Un point x^* vérifie les conditions KKT s'il existe λ^* ∈ ℝm et µ^* ∈ ℝp tels que :
| Nom | Condition |
|---|---|
| Stationnarité | ∇ f(x^*) + Σi λi^* ∇ gi(x^*) + Σj µj^* ∇ hj(x^*) = 0 |
| Admissibilité primale | gi(x^*) ≤ 0 et hj(x^*) = 0 |
| Admissibilité duale | λi^* ≥ 0 pour tout i |
| Complémentarité | λi^* gi(x^*) = 0 pour tout i |
La complémentarité dit qu'une contrainte inactive (gi < 0) a un multiplicateur nul : elle ne « pèse » pas sur l'optimum. Si λi^* > 0, la contrainte est forcément active.
Lecture géométrique : à l'optimum, -∇ f(x^*) est une combinaison à coefficients positifs des gradients des contraintes actives (plus une combinaison quelconque des ∇ hj). Autrement dit, la direction de plus forte descente « pointe vers l'extérieur » de X : toute direction qui ferait baisser f ferait sortir de l'ensemble admissible.
∇g (contrainte active, vers l'extérieur)
↑
| zone interdite g > 0
========x*==================== frontière g = 0
| zone admissible g < 0
↓
∇f (f diminue vers le haut, donc vers l'extérieur)3. Qualification des contraintes
Les conditions KKT ne sont nécessaires que si les contraintes sont « bien posées » en x^*. On dit qu'une condition de qualification est satisfaite. Les plus utilisées :
| Condition | Énoncé | Quand l'utiliser |
|---|---|---|
| Contraintes affines | tous les gi et hj sont affines | programmation linéaire, quadratique |
| LICQ | les gradients ∇ gi(x^*), i ∈ I(x^*), et ∇ hj(x^*) sont linéairement indépendants | cas général, se vérifie en x^* |
| Slater | problème convexe (f, gi convexes, hj affines) et il existe x avec gi(x) < 0 pour tout i et hj(x) = 0 | problèmes convexes, se vérifie une fois pour toutes |
Théorème (Karush 1939, Kuhn et Tucker 1951). Si x^* est un minimum local de (P) et si une condition de qualification est satisfaite en x^*, alors il existe des multiplicateurs (λ^, µ^) tels que (x^, λ^, µ^*) vérifie les conditions KKT. Sous LICQ, ces multiplicateurs sont de plus uniques.
Sans qualification, le théorème peut tomber en défaut :
Exemple
Problème : minimiser f(x) = x sous la contrainte g(x) = x² ≤ 0.
Étape 1 : l'ensemble admissible est réduit à {0}, donc x* = 0 est le minimum.
Étape 2 : en x* = 0, g'(0) = 0 : le gradient de la seule contrainte active est nul, LICQ échoue.
Étape 3 : stationnarité : f'(0) + λ g'(0) = 1 + λ × 0 = 1 ≠ 0, quel que soit λ.
Conclusion : x* est un minimum mais n'est pas un point KKT. Il faut toujours vérifier la qualification avant d'éliminer un candidat.
4. Convexité et conditions du second ordre
Théorème (suffisance). Si f et les gi sont convexes et les hj affines, tout point KKT est un minimum global de (P).
Preuve en une ligne : pour x admissible, f(x) ≥ L(x, λ^, µ^) ≥ L(x^, λ^, µ^) = f(x^). La première inégalité vient de λi^* gi(x) ≤ 0 et hj(x) = 0 ; la deuxième de la convexité de x ↦ L(x, λ^, µ^), minimisée en x^* par la stationnarité ; l'égalité finale vient de la complémentarité.
Dans un problème convexe avec Slater, on a donc l'équivalence : x^* minimum global ⇔ x^* point KKT.
Sans convexité, on utilise les conditions du second ordre. Notons C(x^*) le cône critique : les directions d telles que ∇ hj(x^*)T d = 0, ∇ gi(x^*)T d = 0 pour les contraintes actives avec λi^* > 0, et ∇ gi(x^*)T d ≤ 0 pour les actives avec λi^* = 0.
- Condition nécessaire (sous LICQ) : dT ∇2xx L(x^, λ^, µ^*) d ≥ 0 pour tout d ∈ C(x^*).
- Condition suffisante : si dT ∇2xx L d > 0 pour tout d ∈ C(x^*), d ≠ 0, alors x^* est un minimum local strict.
5. Résoudre en pratique : les ensembles actifs
Méthode
- Mettre le problème sous forme standard : minimisation, contraintes g_i(x) ≤ 0 et h_j(x) = 0.
- Écrire le lagrangien et les quatre familles de conditions KKT.
- Vérifier une condition de qualification (Slater si le problème est convexe, sinon LICQ point par point).
- Faire une hypothèse sur les contraintes actives ; mettre λ_i = 0 pour les inactives.
- Résoudre le système obtenu, puis contrôler : admissibilité primale (g_i ≤ 0) et signes (λ_i ≥ 0).
- Rejeter les hypothèses incohérentes et recommencer ; si le problème est convexe, s'arrêter au premier point KKT trouvé.
- Conclure : nature du point (convexité ou second ordre) et valeur optimale.
Exemple
Kindia Jus : minimiser f(x, y) = (x − 3)² + (y − 2)² s.c. g1 = x + y − 4 ≤ 0, g2 = −x ≤ 0, g3 = −y ≤ 0.
Étape 1 (qualification) : f est convexe, les contraintes sont affines ; de plus (1, 1) vérifie strictement les trois contraintes (Slater).
Étape 2 (aucune contrainte active) : ∇f = 0 donne (3, 2) ; mais 3 + 2 = 5 > 4 : non admissible. On rejette.
Étape 3 (g1 seule active) : 2(x − 3) + λ1 = 0 et 2(y − 2) + λ1 = 0, donc x − 3 = y − 2.
Avec x + y = 4 : x = 2,5 et y = 1,5 ; puis λ1 = −2(2,5 − 3) = 1 ≥ 0.
Étape 4 (contrôle) : x > 0 et y > 0, donc g2 et g3 inactives, λ2 = λ3 = 0. Toutes les conditions KKT sont vérifiées.
Conclusion : le problème étant convexe, (2,5 ; 1,5) est le minimum global, avec f* = 0,25 + 0,25 = 0,5.
Kindia Jus produit 2 500 litres de jus de mangue et 1 500 litres de jus d'ananas par jour.
Interprétation du multiplicateur. Remplaçons la capacité 4 par b. Pour b proche de 4, la même contrainte reste active et on trouve f^*(b) = (5-b)22, donc df^*db(4) = -(5-4) = -1 = -λ1^*.
En général, pour une contrainte gi(x) ≤ bi, sous des hypothèses de régularité :
∂ f^*∂ bi = -λi^*.
Un millier de litres de capacité supplémentaire ferait baisser l'écart d'environ λ1^* = 1 unité. Le multiplicateur mesure la valeur marginale de la ressource : c'est le « prix » qu'on serait prêt à payer pour relâcher la contrainte. Cette idée sera au centre de la leçon 2.
3Je retiens
Je retiens
Forme standard : min f(x) s.c. g_i(x) ≤ 0 et h_j(x) = 0 ; lagrangien L = f + Σ λ_i g_i + Σ μ_j h_j.
KKT : stationnarité, admissibilité primale, λ_i ≥ 0, complémentarité λ_i g_i(x*) = 0.
Une contrainte inactive a un multiplicateur nul ; λ_i > 0 impose que la contrainte soit active.
KKT est nécessaire seulement sous qualification : contraintes affines, LICQ ou Slater.
Problème convexe : tout point KKT est un minimum global.
Sans convexité : conditions du second ordre sur le cône critique.
Résolution : on teste les ensembles de contraintes actives, puis on contrôle admissibilité et signes.
Le multiplicateur est la sensibilité de la valeur optimale : ∂f*/∂b_i = −λ_i.
4Erreurs fréquentes
- Oublier de mettre une contrainte « ≥ » sous la forme g(x) ≤ 0 : le signe du multiplicateur devient faux.
- Accepter un point avec λ_i < 0 : il viole l'admissibilité duale, ce n'est pas un point KKT.
- Oublier de vérifier g_i(x) ≤ 0 pour les contraintes supposées inactives.
- Conclure « minimum global » sans convexité : un point KKT peut être un maximum ou un point selle.
- Rejeter un candidat parce qu'il n'est pas KKT sans avoir vérifié la qualification.
5Je m’exerce
1Exercice 1
(Questions de cours)
a) Écrivez les quatre familles de conditions KKT pour min f(x) s.c. gi(x) ≤ 0, hj(x) = 0.
b) Énoncez la condition de Slater. Pour quels problèmes s'applique-t-elle ?
c) Que dit la complémentarité d'une contrainte inactive ?
Voir le corrigéCacher le corrigé
a) Stationnarité ∇ f + Σ λi ∇ gi + Σ µj ∇ hj = 0 ; admissibilité primale gi ≤ 0, hj = 0 ; admissibilité duale λi ≥ 0 ; complémentarité λi gi = 0.
b) Si f et les gi sont convexes et les hj affines, et s'il existe un point qui vérifie toutes les inégalités strictement et toutes les égalités, alors les contraintes sont qualifiées en tout point. Elle s'applique aux problèmes convexes.
c) Si gi(x^*) < 0, alors λi^* = 0.
2Exercice 2
Résolvez par les conditions KKT : minimiser x2 + y2 sous la contrainte x + 2y ≥ 2. Justifiez que le point trouvé est un minimum global.
Voir le corrigéCacher le corrigé
Forme standard : g(x, y) = 2 - x - 2y ≤ 0. Le problème est convexe (fonction quadratique convexe, contrainte affine), donc les contraintes sont qualifiées.
Sans contrainte active : (0, 0), mais 0 + 0 < 2, non admissible.
Contrainte active : 2x - λ = 0 et 2y - 2λ = 0, donc x = λ/2 et y = λ. Avec x + 2y = 2 : λ2 + 2λ = 2, d'où λ = 45 ≥ 0, x = 25, y = 45.
Le problème étant convexe, (25, 45) est le minimum global, avec f^* = 425 + 1625 = 45. C'est la projection de l'origine sur la droite x + 2y = 2.
3Exercice 3
On considère : minimiser -x s.c. y - (1-x)3 ≤ 0 et y ≥ 0.
a) Montrez que l'ensemble admissible est contenu dans {x ≤ 1} et que le minimum est atteint en (1, 0).
b) Montrez que LICQ n'est pas vérifiée en (1, 0).
c) Montrez que (1, 0) n'est pas un point KKT. Quelle leçon en tirez-vous ?
Voir le corrigéCacher le corrigé
a) y ≥ 0 et y ≤ (1-x)3 imposent (1-x)3 ≥ 0, donc x ≤ 1. Minimiser -x revient à maximiser x ; le point (1, 0) est admissible (0 ≤ 0), donc il est optimal.
b) En (1, 0), les deux contraintes sont actives. ∇ g1 = (3(1-x)2, 1) = (0, 1) et ∇ g2 = (0, -1) pour g2 = -y. Ces vecteurs sont opposés, donc liés : LICQ échoue. Les contraintes ne sont pas affines et g1 n'est pas convexe, on ne peut pas invoquer Slater.
c) Stationnarité : (-1, 0) + λ1 (0, 1) + λ2 (0, -1) = (0, 0). La première composante donne -1 = 0 : impossible. L'optimum n'est pas un point KKT. Leçon : sans qualification, chercher seulement les points KKT peut faire manquer l'optimum.
4Exercice 4
Minimiser (x-2)2 + (y-1)2 s.c. x2 - y ≤ 0 et x + y ≤ 2.
a) Vérifiez que le problème est convexe et que la condition de Slater est satisfaite.
b) Montrez que (1, 1) est un point KKT et calculez les multiplicateurs.
c) Concluez.
Voir le corrigéCacher le corrigé
a) f est convexe (hessienne 2I), g1 = x2 - y est convexe (hessienne de valeurs propres 2 et 0), g2 est affine. Le point (0, 1) donne g1 = -1 < 0 et g2 = -1 < 0 : Slater est satisfaite.
b) En (1, 1) : g1 = 0 et g2 = 0, les deux sont actives. ∇ f = (2(1-2), 2(1-1)) = (-2, 0), ∇ g1 = (2, -1), ∇ g2 = (1, 1).
Stationnarité : -2 + 2λ1 + λ2 = 0 et -λ1 + λ2 = 0. Donc λ1 = λ2 et 3λ1 = 2 : λ1 = λ2 = 23 ≥ 0. La complémentarité est vérifiée puisque les deux contraintes sont actives.
c) Le problème est convexe : (1, 1) est le minimum global, avec f^* = 1 + 0 = 1.
5Exercice 5
Reprenez l'exercice 2 avec la contrainte x + 2y ≥ b.
a) Exprimez la valeur optimale f^*(b) pour b > 0.
b) Vérifiez que df^*db(2) est égal au multiplicateur trouvé à l'exercice 2.
c) Estimez f^*(2,1) avec le multiplicateur, puis comparez à la valeur exacte.
Voir le corrigéCacher le corrigé
a) Même calcul avec x + 2y = b : λ = 2b5, x = b5, y = 2b5, donc f^*(b) = b225 + 4b225 = b25.
b) df^*db = 2b5, qui vaut 45 en b = 2 : c'est bien λ. Ici la contrainte b - x - 2y ≤ 0 se durcit quand b augmente, d'où le signe +.
c) Estimation : f^*(2,1) ≈ 45 + 0,8 × 0,1 = 0,88. Valeur exacte : 2,125 = 4,415 = 0,882. L'écart, 0,002, est du second ordre.
6Exercice 6
(Type examen) Kindia Jus dispose d'un budget publicitaire b (en centaines de millions de GNF) à répartir entre Conakry (x) et Kindia (y). Supposons que le gain de ventes, en milliards de GNF, soit 2ln(1+x) + ln(1+y).
a) Écrivez le problème sous forme standard de minimisation et ses conditions KKT.
b) Résolvez pour b = 3 et donnez le multiplicateur de la contrainte de budget.
c) Estimez le gain supplémentaire apporté par 0,5 de budget en plus, puis calculez la valeur exacte.
d) Résolvez pour b = 0,5. Pour quelles valeurs de b la ville de Kindia reçoit-elle un budget strictement positif ?
Voir le corrigéCacher le corrigé
a) Minimiser f = -2ln(1+x) - ln(1+y) s.c. g1 = x + y - b ≤ 0, g2 = -x ≤ 0, g3 = -y ≤ 0. KKT : -21+x + λ - µx = 0 ; -11+y + λ - µy = 0 ; λ, µx, µy ≥ 0 ; λ(x + y - b) = 0, µx x = 0, µy y = 0. Le problème est convexe, les contraintes affines : KKT est nécessaire et suffisant.
b) Le gain est strictement croissant en x et y : tout le budget est dépensé, λ > 0. Supposons x, y > 0 : 21+x = 11+y = λ, donc 1 + x = 2(1+y), soit x = 1 + 2y. Avec x + y = 3 : y = 23, x = 73, λ = 11 + 2/3 = 35. Gain : 2ln103 + ln53 ≈ 2,919 milliards de GNF.
c) Estimation : 0,5 × 35 = 0,3, soit un gain d'environ 3,219. Valeur exacte pour b = 3,5 : y = 56, x = 83, gain 2ln113 + ln116 ≈ 3,205. L'estimation est bonne, légèrement par excès car la valeur optimale est concave en b.
d) La formule y = b-13 donnerait y < 0. Essayons y = 0, x = 0,5 : λ = 21,5 = 43, µx = 0, puis µy = λ - 1 = 13 ≥ 0. Toutes les conditions sont vérifiées : tout le budget va à Conakry. Kindia reçoit un budget positif dès que b-13 > 0, c'est-à-dire b > 1.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.