Aller au contenu
Optimisation 2 · L3

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).

ConventionForme imposéeSigne du multiplicateur
inégalitégi(x) ≤ 0λi ≥ 0
égalitéhj(x) = 0µj de signe quelconque
problème de maximisationon minimise -finchangé

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 :

NomCondition
Stationnarité∇ f(x^*) + Σi λi^* ∇ gi(x^*) + Σj µj^* ∇ hj(x^*) = 0
Admissibilité primalegi(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 affinestous les gi et hj sont affinesprogrammation linéaire, quadratique
LICQles gradients ∇ gi(x^*), i ∈ I(x^*), et ∇ hj(x^*) sont linéairement indépendantscas général, se vérifie en x^*
Slaterproblème convexe (f, gi convexes, hj affines) et il existe x avec gi(x) < 0 pour tout i et hj(x) = 0problè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

  1. Mettre le problème sous forme standard : minimisation, contraintes g_i(x) ≤ 0 et h_j(x) = 0.
  2. Écrire le lagrangien et les quatre familles de conditions KKT.
  3. Vérifier une condition de qualification (Slater si le problème est convexe, sinon LICQ point par point).
  4. Faire une hypothèse sur les contraintes actives ; mettre λ_i = 0 pour les inactives.
  5. Résoudre le système obtenu, puis contrôler : admissibilité primale (g_i ≤ 0) et signes (λ_i ≥ 0).
  6. Rejeter les hypothèses incohérentes et recommencer ; si le problème est convexe, s'arrêter au premier point KKT trouvé.
  7. 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.

1Dans les conditions KKT, une contrainte d'inégalité inactive à l'optimum a :
Voir la réponse

Réponse B : un multiplicateur nul. Complémentarité : λi gi(x^*) = 0 et gi(x^*) < 0 imposent λi = 0.

2Pour une contrainte gi(x) ≤ 0, le multiplicateur associé doit être :
Voir la réponse

Réponse A : positif ou nul. C'est l'admissibilité duale ; seules les égalités ont un multiplicateur de signe libre.

3La condition de Slater exige notamment :
Voir la réponse

Réponse B : un problème convexe et un point vérifiant strictement les inégalités. Slater porte sur l'existence d'un point strictement admissible dans un problème convexe.

4Dans un problème convexe, un point KKT est :
Voir la réponse

Réponse B : un minimum global. La convexité rend les conditions KKT suffisantes pour l'optimalité globale.

5Le minimum de x sous la contrainte x2 ≤ 0 :
Voir la réponse

Réponse B : n'est pas un point KKT car la qualification échoue. L'unique point admissible est 0, où le gradient de la contrainte est nul.

6Si la contrainte de capacité x + y ≤ b a un multiplicateur λ^* = 1 dans un problème de minimisation, augmenter b de 0,1 fait varier la valeur optimale d'environ :
Voir la réponse

Réponse B : -0,1. ∂ f^* / ∂ b = -λ^* : relâcher la contrainte fait baisser le coût de 0,1 λ^*.

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ö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Optimisation 2

Pose ta question à Karamö