Maîtrisez les conditions KKT

La mairie a révisé son règlement : l’entrepôt n’a plus besoin d’être sur la rocade, il doit simplement se trouver à l’extérieur, côté sud-ouest. Et une seconde règle s’ajoute : pas de construction à l’ouest de la Vilaine, qui coule le long de la droite $x = 1{,}5$. Ce ne sont plus des égalités, mais des inégalités : l’entrepôt peut être n’importe où dans une zone.

Face à une inégalité, une question nouvelle se pose : la contrainte gêne-t-elle vraiment ? Si le meilleur point de la zone est à l’intérieur, la contrainte ne sert à rien ; s’il est sur le bord, elle se comporte comme une égalité. Les conditions de Karush-Kuhn-Tucker (KKT) traitent les deux situations d’un seul coup. Ce sont les conditions d’optimalité les plus générales de ce cours, et celles qu’on retrouve derrière les SVM.

Contrainte active ou inactive ?

On écrit toujours un problème d’optimisation sous contraintes d’inégalité sous la forme standard :

$$\min_x \; f(x) \quad \text{s.c.} \quad g_i(x) \leq 0, \quad i = 1, \dots, m$$

En un point réalisable $x$, une contrainte est active (ou saturée) si $g_i(x) = 0$ : on est sur le bord. Elle est inactive si $g_i(x) \lt 0$ : on a de la marge.

Reprenons l’entrepôt, avec la seule règle de la rocade : $g(p) = x + y - 2 \leq 0$. Le coût est toujours $f(p) = 3\lVert p - G \rVert^2 + 32$, de minimum libre $G = (2, 2)$.

• Le barycentre ne respecte pas la contrainte ($2 + 2 = 4 \gt 2$). Le meilleur point de la zone est donc sur le bord : la contrainte est active, et l’on retrouve exactement le problème du chapitre 8, avec $p^* = (1, 1)$ et un multiplicateur égal à 6.
• Si la règle était $x + y \leq 5$, le barycentre serait dans la zone. La contrainte serait inactive : on l’ignore, $p^* = G$, et tout se passe comme si le multiplicateur valait 0.

Dans les deux cas, on peut écrire $\nabla f(p^*) + \mu \nabla g(p^*) = 0$, avec $\mu = 6$ dans le premier et $\mu = 0$ dans le second. Et dans les deux cas, le produit $\mu \, g(p^*)$ est nul. C’est toute l’idée de KKT.

Le signe du multiplicateur

Pour une égalité, le multiplicateur pouvait être de signe quelconque. Pour une inégalité, non. Écrivez la condition sous la forme $-\nabla f(p^*) = \mu \nabla g(p^*)$ : la direction de plus forte descente de $f$ doit pointer vers l’extérieur de la zone, du côté où $g$ augmente. Sinon, on pourrait encore descendre en restant dans la zone, et $p^*$ ne serait pas optimal. D’où la condition $\mu \geq 0$.

Imaginez une bille qui roule vers le fond d’une cuvette et vient buter contre un mur. À l’arrêt, la pente la pousse contre le mur, et le mur la repousse avec une force de même intensité. Le multiplicateur mesure cette force de réaction : elle ne peut que repousser ($\mu \geq 0$), jamais attirer, et elle est nulle si la bille ne touche pas le mur.

Contrainte active : la bille bute contre le mur, qui la repousse avec une force μ = 6. Contrainte inactive : le fond de la cuvette est dans la zone, le mur ne sert à rien et μ = 0.

Attention

La condition $\mu_i \geq 0$ suppose la forme standard : une minimisation avec des contraintes écrites $g_i(x) \leq 0$. Une contrainte $x \geq 1{,}5$ doit être réécrite $1{,}5 - x \leq 0$, et un problème de maximisation transformé en $\min(-f)$. Avec une autre convention, les signes s’inversent.

Les conditions de Karush-Kuhn-Tucker

Considérons le problème général, avec des inégalités et des égalités :

$$\min_x \; f(x) \quad \text{s.c.} \quad g_i(x) \leq 0 \; (i = 1, \dots, m), \qquad h_j(x) = 0 \; (j = 1, \dots, q)$$

Son lagrangien est $L(x, \mu, \lambda) = f(x) + \sum_i \mu_i g_i(x) + \sum_j \lambda_j h_j(x)$. Si $x^*$ est un minimum local et que le problème est qualifié en $x^*$ (voir plus bas), alors il existe des multiplicateurs $\mu_i$ et $\lambda_j$ tels que :

1. Stationnarité : $\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0$ ;
2. Réalisabilité primale : $g_i(x^*) \leq 0$ et $h_j(x^*) = 0$ ;
3. Réalisabilité duale : $\mu_i \geq 0$ (les $\lambda_j$ sont libres) ;
4. Complémentarité : $\mu_i \, g_i(x^*) = 0$ pour tout $i$.

La complémentarité dit que, pour chaque inégalité, soit la contrainte est active, soit son multiplicateur est nul (ou les deux). Vous l’aviez déjà rencontrée : ce sont les écarts complémentaires du chapitre 4, où une ressource non épuisée avait un prix nul.

À retenir

KKT = stationnarité + réalisabilité + multiplicateurs positifs + complémentarité. À l’optimum, le gradient de l’objectif est équilibré par les gradients des contraintes actives ; les contraintes inactives ont un multiplicateur nul. Pour une minimisation avec $g_i \leq 0$, les $\mu_i$ sont positifs ou nuls.

La méthode : énumérer les contraintes actives

La complémentarité donne une méthode de résolution systématique. Pour chaque inégalité, deux cas : $\mu_i = 0$ ou $g_i(x) = 0$. Avec $m$ inégalités, cela fait $2^m$ combinaisons. Pour chacune, on résout un système d’équations, puis on élimine les solutions qui violent une contrainte ou qui ont un $\mu_i$ négatif.

Exemple

Appliquons la méthode à l’entrepôt avec les deux règles : $g_1(p) = x + y - 2 \leq 0$ (hors de la rocade) et $g_2(p) = 1{,}5 - x \leq 0$ (à l’est de la Vilaine). Les gradients sont $\nabla g_1 = (1, 1)$ et $\nabla g_2 = (-1, 0)$, et la stationnarité s’écrit :

$$6(x - 2) + \mu_1 - \mu_2 = 0, \qquad 6(y - 2) + \mu_1 = 0$$

Cas	Hypothèses	Candidat	Verdict
aucune active	$\mu_1 = \mu_2 = 0$	$(2, 2)$	viole $g_1$ ($4 \gt 2$) : rejeté
$g_1$ seule	$\mu_2 = 0$, $x + y = 2$	$(1, 1)$, $\mu_1 = 6$	viole $g_2$ ($1 \lt 1{,}5$) : rejeté
$g_2$ seule	$\mu_1 = 0$, $x = 1{,}5$	$(1{,}5 ; 2)$, $\mu_2 = -3$	$\mu_2 \lt 0$ (et viole $g_1$) : rejeté
les deux	$x + y = 2$, $x = 1{,}5$	$(1{,}5 ; 0{,}5)$, $\mu_1 = 9$, $\mu_2 = 6$	toutes les conditions sont vérifiées

Le seul point KKT est $p^* = (1{,}5 ; 0{,}5)$, au coin de la zone, pour un coût $f(p^*) = 2{,}5 + 6{,}5 + 30{,}5 = 39{,}5$. Les deux règles coûtent donc $39{,}5 - 32 = 7{,}5$ par rapport à l’emplacement idéal. Les multiplicateurs indiquent laquelle pèse le plus : la rocade ($\mu_1 = 9$) plutôt que la Vilaine ($\mu_2 = 6$).

Les quatre cas de l'énumération sur la carte : trois candidats sont rejetés (hors zone ou multiplicateur négatif), seul le coin (1,5 ; 0,5) vérifie toutes les conditions. Le cercle de niveau 39,5 y touche la zone.

Vérifions la stationnarité au point trouvé : $\nabla f(p^*) = 6\,(p^* - G) = (-3, -9)$, et $(-3, -9) + 9\,(1, 1) + 6\,(-1, 0) = (0, 0)$. Le gradient de l’objectif est bien équilibré par ceux des deux contraintes actives.

La stationnarité au coin, dessinée : −∇f(p*) = (3, 9) est la somme de 9 × ∇g₁ et 6 × ∇g₂, avec des coefficients positifs.

Piège

Dans le troisième cas, on a obtenu un multiplicateur négatif. Ce n’est pas une erreur de calcul, c’est un signal : ce point n’est pas optimal. Oublier de vérifier le signe des $\mu_i$ (ou la réalisabilité des candidats) conduit à retenir de faux optimums.

Qualification et suffisance

Quand les conditions KKT sont-elles nécessaires ?

Comme pour Lagrange, les conditions KKT ne sont garanties qu’en un point qualifié. Les critères les plus utilisés :

• Indépendance linéaire (LICQ) : les gradients des contraintes actives (inégalités actives et égalités) sont linéairement indépendants en $x^*$ ;
• Contraintes affines : si toutes les contraintes sont affines, le problème est automatiquement qualifié ;
• Condition de Slater, pour un problème convexe : il existe un point strictement réalisable, c’est-à-dire avec $g_i(x) \lt 0$ pour toutes les inégalités (et les égalités affines satisfaites).

Sans qualification, KKT peut échouer. Minimisez $f(x) = x$ sous $g(x) = x^2 \leq 0$ : le seul point réalisable est $x = 0$, donc c’est le minimum. Pourtant $f'(0) = 1$ et $g'(0) = 0$ : aucun $\mu$ ne vérifie $1 + \mu \times 0 = 0$. La contrainte est dégénérée (son gradient s’annule), et Slater échoue aussi puisqu’aucun $x$ ne vérifie $x^2 \lt 0$.

Quand sont-elles suffisantes ?

Si le problème est convexe (objectif $f$ convexe, inégalités $g_i$ convexes, égalités $h_j$ affines), tout point KKT est un minimum global. C’est le cas de l’entrepôt : $f$ est une somme de carrés, et les deux contraintes sont affines. Le point $(1{,}5 ; 0{,}5)$ est donc bien le meilleur emplacement possible.

Sans convexité, un point KKT n’est qu’un candidat. On conclut comme au chapitre 8 : si l’ensemble réalisable est compact, on compare les valeurs de $f$ en tous les points KKT (et en les éventuels points non qualifiés) et l’on garde la meilleure.

Exemple

En Python, scipy.optimize.minimize résout ce type de problème (méthode SLSQP). Attention à sa convention : une contrainte de type "ineq" signifie $c(x) \geq 0$, l’inverse de notre forme standard.

import numpy as np
from scipy.optimize import minimize

clients = np.array([[0, 0], [4, 0], [2, 6]])
cout = lambda p: np.sum((clients - p) ** 2)

contraintes = [
    {"type": "ineq", "fun": lambda p: 2 - p[0] - p[1]},   # x + y <= 2, écrit 2 - x - y >= 0
    {"type": "ineq", "fun": lambda p: p[0] - 1.5},        # x >= 1.5
]
res = minimize(cout, x0=[0.0, 0.0], method="SLSQP", constraints=contraintes)
print(res.x.round(4), round(res.fun, 4))   # environ [1.5 0.5] et 39.5

Pour aller plus loin : la dualité lagrangienne

Le lagrangien permet de généraliser la dualité du chapitre 4 à tout problème d’optimisation. On définit la fonction duale $q(\mu, \lambda) = \min_x L(x, \mu, \lambda)$, puis le problème dual $\max_{\mu \geq 0, \lambda} q(\mu, \lambda)$. La dualité faible est toujours vraie ($q \leq$ la valeur optimale du primal), et pour un problème convexe qui vérifie Slater, la dualité forte aussi. Appliquée à un programme linéaire, cette construction redonne exactement le dual du chapitre 4. Appliquée aux SVM, elle donne le problème dual qui fait apparaître les vecteurs de support et l’astuce du noyau : vous le verrez au chapitre suivant.

En entretien

« Les conditions KKT généralisent Lagrange aux inégalités : à l’optimum, le gradient de l’objectif est équilibré par ceux des contraintes actives, avec des multiplicateurs positifs, et une contrainte inactive a un multiplicateur nul. Pour un problème convexe, elles sont suffisantes. »

En résumé

• On écrit les inégalités sous la forme standard $g_i(x) \leq 0$, dans un problème de minimisation.
• Les conditions KKT : stationnarité du lagrangien, réalisabilité, $\mu_i \geq 0$ et complémentarité $\mu_i g_i(x^*) = 0$.
• Une contrainte inactive a un multiplicateur nul ; une contrainte active se comporte comme une égalité, avec un multiplicateur positif.
• On résout en énumérant les ensembles de contraintes actives ($2^m$ cas) et en éliminant les candidats non réalisables ou à multiplicateur négatif.
• Les conditions sont nécessaires sous qualification (indépendance linéaire, contraintes affines ou Slater) et suffisantes si le problème est convexe.
• Le multiplicateur mesure le coût marginal de la contrainte, comme un prix dual.

Exercices

Exercice · Active ou pas ?

facile

Résolvez avec KKT $\min (x - 3)^2$ sous $x \leq 1$, puis sous $x \leq 5$. Interprétez le multiplicateur.

Voir la solution

Forme standard : $g(x) = x - 1 \leq 0$. Stationnarité : $2(x - 3) + \mu = 0$.

• Cas $\mu = 0$ : $x = 3$, qui viole $x \leq 1$. Rejeté.
• Cas contrainte active : $x = 1$, d’où $\mu = -2(1 - 3) = 4 \geq 0$. Accepté.

Le minimum est en $x = 1$ avec $\mu = 4$. Le problème est convexe, c’est le minimum global. Interprétation : avec la contrainte $x \leq b$ (pour $b \lt 3$), la valeur optimale vaut $(b - 3)^2$, de dérivée $2(b - 3) = -4$ en $b = 1$ ; relâcher la contrainte d’une unité fait gagner environ 4.

Sous $x \leq 5$ : le cas $\mu = 0$ donne $x = 3$, réalisable ($3 \leq 5$). La contrainte est inactive, $\mu = 0$, et le minimum est le minimum libre.

En code

Python

from scipy.optimize import minimize

def resoudre(b):                     # min (x - 3)² sous x <= b
    res = minimize(lambda v: (v[0] - 3) ** 2, x0=[0.0], method="SLSQP",
                   constraints=[{"type": "ineq", "fun": lambda v: b - v[0]}])  # b - x >= 0
    x = float(res.x[0])
    mu = -2 * (x - 3)                # tiré de la stationnarité 2(x - 3) + μ = 0
    return round(x, 4), round(float(res.fun), 4), round(mu, 4)

print(resoudre(1))                   # (1.0, 4.0, 4.0) : contrainte active, μ = 4
print(resoudre(5))                   # (3.0, 0.0, 0.0) : contrainte inactive, μ = 0
# Sensibilité : relâcher la contrainte de 0,01 fait gagner environ 4 × 0,01
print(round((resoudre(1)[1] - resoudre(1.01)[1]) / 0.01, 4))   # 3.99

R

resoudre <- function(b) {            # min (x - 3)² sous x <= b
  res <- optimize(function(x) (x - 3)^2, c(-10, b), tol = 1e-10)
  x <- res$minimum
  c(x = x, valeur = res$objective, mu = -2 * (x - 3))   # μ par la stationnarité
}
round(resoudre(1), 4)                # x = 1, valeur 4, μ = 4 : contrainte active
round(resoudre(5), 4)                # x = 3, valeur 0, μ = 0 : contrainte inactive
(resoudre(1)["valeur"] - resoudre(1.01)["valeur"]) / 0.01   # 3.99 : environ μ

Exercice · Optimiser une fonction linéaire sur un disque

moyen

Soit $a = (3, 4)$. Résolvez $\min a^T x$ sous $\lVert x \rVert^2 \leq 1$ (avec $x \in \mathbb{R}^2$). Déduisez-en le maximum de $a^T x$ sur le même disque.

Voir la solution

Forme standard : $g(x) = \lVert x \rVert^2 - 1 \leq 0$, de gradient $2x$. Stationnarité : $a + 2\mu x = 0$.

• Cas $\mu = 0$ : il faudrait $a = 0$, impossible. Rejeté.
• Cas actif : $\lVert x \rVert = 1$ et $x = -a / (2\mu)$. En prenant la norme, $\lVert a \rVert / (2\mu) = 1$, soit $\mu = \lVert a \rVert / 2 = 2{,}5 \geq 0$. D’où $x^* = -a / \lVert a \rVert = (-0{,}6 ; -0{,}8)$.

La valeur optimale est $a^T x^* = -\lVert a \rVert = -5$. Le problème est convexe (objectif linéaire, contrainte convexe) et vérifie Slater (l’origine est strictement réalisable) : c’est le minimum global.

Pour le maximum, on minimise $-a^T x$ : même calcul avec $-a$, d’où $x = a / \lVert a \rVert = (0{,}6 ; 0{,}8)$ et un maximum égal à $\lVert a \rVert = 5$. Géométriquement, on va dans la direction de $a$ (ou son opposée) jusqu’au bord du disque.

En code

Python

import numpy as np
from scipy.optimize import minimize

a = np.array([3.0, 4.0])
disque = [{"type": "ineq", "fun": lambda x: 1 - x @ x}]     # 1 - ||x||² >= 0
res_min = minimize(lambda x: a @ x, x0=[0.0, 0.0], method="SLSQP", constraints=disque)
res_max = minimize(lambda x: -a @ x, x0=[0.0, 0.0], method="SLSQP", constraints=disque)
print(res_min.x.round(4), round(res_min.fun, 4))    # [-0.6 -0.8] -5.0
print(res_max.x.round(4), round(-res_max.fun, 4))   # [0.6 0.8] 5.0
print(-a / (2 * res_min.x))                         # [2.5 2.5] : μ = 2,5 >= 0

R

a <- c(3, 4)
# La contrainte est active : on parcourt le cercle x = (cos t, sin t)
valeur <- function(t) a[1] * cos(t) + a[2] * sin(t)
mini <- optimize(valeur, c(0, 2 * pi))
maxi <- optimize(valeur, c(0, 2 * pi), maximum = TRUE)
x_min <- c(cos(mini$minimum), sin(mini$minimum))
round(x_min, 4); round(mini$objective, 4)        # -0.6 -0.8 ; -5
round(c(cos(maxi$maximum), sin(maxi$maximum)), 4); round(maxi$objective, 4)   # 0.6 0.8 ; 5
round(-a / (2 * x_min), 4)                       # 2.5 2.5 : μ = 2,5 >= 0

Exercice · Un problème mixte

difficile

Résolvez $\min (x - 2)^2 + (y - 1)^2$ sous l’égalité $x + y = 2$ et l’inégalité $y \geq x$. Donnez les multiplicateurs et vérifiez toutes les conditions KKT.

Voir la solution

Forme standard : $h(x, y) = x + y - 2 = 0$ et $g(x, y) = x - y \leq 0$. Le lagrangien est $L = (x - 2)^2 + (y - 1)^2 + \lambda(x + y - 2) + \mu(x - y)$, et la stationnarité s’écrit :

$$2(x - 2) + \lambda + \mu = 0, \qquad 2(y - 1) + \lambda - \mu = 0$$

Cas $\mu = 0$ : $x - 2 = y - 1$, soit $x = y + 1$. Avec $x + y = 2$ : $y = 0{,}5$, $x = 1{,}5$. Mais $x - y = 1 \gt 0$ viole l’inégalité. Rejeté.

Cas actif ($x = y$) : avec $x + y = 2$, on obtient $(1, 1)$. La stationnarité donne $-2 + \lambda + \mu = 0$ et $\lambda - \mu = 0$, d’où $\lambda = \mu = 1$.

Vérification : réalisabilité ($1 + 1 = 2$ et $1 - 1 = 0 \leq 0$), $\mu = 1 \geq 0$, complémentarité ($\mu \times 0 = 0$), $\lambda$ libre. Le problème est convexe (objectif quadratique convexe, contraintes affines) : $(1, 1)$ est le minimum global, de valeur $1 + 0 = 1$. Géométriquement, c’est le point du segment de droite $x + y = 2$, dans la zone $y \geq x$, le plus proche de $(2, 1)$.

En code

Python

import numpy as np
from scipy.optimize import minimize

cout = lambda v: (v[0] - 2) ** 2 + (v[1] - 1) ** 2
contraintes = [{"type": "eq", "fun": lambda v: v[0] + v[1] - 2},     # x + y = 2
               {"type": "ineq", "fun": lambda v: v[1] - v[0]}]       # y - x >= 0
res = minimize(cout, x0=[0.0, 0.0], method="SLSQP", constraints=contraintes)
x, y = res.x
print(res.x.round(4), round(res.fun, 4))         # [1. 1.] 1.0

# Stationnarité : 2(x - 2) + λ + μ = 0 et 2(y - 1) + λ - μ = 0
lam, mu = np.linalg.solve([[1, 1], [1, -1]], [-2 * (x - 2), -2 * (y - 1)])
print(round(lam, 4), round(mu, 4))               # 1.0 1.0 : μ >= 0, et g = x - y = 0

R

# On élimine l'égalité (y = 2 - x) ; y >= x devient x <= 1
cout <- function(x) (x - 2)^2 + (2 - x - 1)^2
res <- optimize(cout, c(-10, 1), tol = 1e-10)
x <- res$minimum; y <- 2 - x
round(c(x, y, res$objective), 4)                 # 1 1 1

# Stationnarité : 2(x - 2) + λ + μ = 0 et 2(y - 1) + λ - μ = 0
mult <- solve(rbind(c(1, 1), c(1, -1)), c(-2 * (x - 2), -2 * (y - 1)))
round(mult, 4)                                   # 1 1 : λ = 1, μ = 1 >= 0