L'essentiel à connaître
Pour minimiser $f(x)$ sous des contraintes $g_i(x) \le 0$ et $h_j(x) = 0$, tu cherches un point $x^*$ et des multiplicateurs $\lambda_i$, $\mu_j$ (un nombre par contrainte) qui vérifient les quatre conditions de Karush-Kuhn-Tucker (KKT) ci-dessous. Exemple : pour minimiser $x^2$ sous $x \ge 1$, écris la contrainte $g(x) = 1 - x \le 0$. La stationnarité $2x - \lambda = 0$ et la complémentarité $\lambda(1 - x) = 0$ laissent deux cas : $\lambda = 0$ donne $x = 0$, qui viole la contrainte, et $x = 1$ donne $\lambda = 2 \ge 0$. Le minimum est $x^* = 1$.
Formule : lagrangien $L(x, \lambda, \mu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \mu_j h_j(x)$, et conditions KKT en $x^*$ :
admissibilité : $g_i(x^*) \le 0$ et $h_j(x^*) = 0$ ;
signe : $\lambda_i \ge 0$ ;
complémentarité : $\lambda_i \, g_i(x^*) = 0$ ;
stationnarité : $\nabla f(x^*) + \sum_i \lambda_i \nabla g_i(x^*) + \sum_j \mu_j \nabla h_j(x^*) = 0$.
Une contrainte est active en $x^*$ si $g_i(x^*) = 0$ : le point est sur son bord. La complémentarité impose un multiplicateur nul à toute contrainte inactive.
Un ensemble $C$ est convexe s'il contient le segment entre deux quelconques de ses points : $tx + (1-t)y \in C$ pour tous $x, y \in C$ et $t \in [0\,;\,1]$. Une fonction deux fois dérivable sur un intervalle y est convexe si et seulement si $f'' \ge 0$. Le problème est convexe quand $f$ et les $g_i$ sont convexes et les $h_j$ affines : alors tout minimum local est global, et il est unique si $f$ est strictement convexe.
Règle : dans un problème convexe différentiable, tout point qui vérifie les conditions KKT est un minimum global, sans autre hypothèse. L'autre sens demande une hypothèse dite de qualification, comme la condition de Slater : un point admissible vérifie toutes les inégalités au sens strict ($g_i(x) \lt 0$). Avec Slater, les KKT sont nécessaires et suffisantes (Boyd et Vandenberghe, § 5.5.3).
Pour $\lambda \ge 0$, la fonction duale $\theta(\lambda, \mu) = \inf_x L(x, \lambda, \mu)$ minore la valeur optimale $p^*$ ; le problème dual cherche la meilleure de ces bornes, $d^*$. On a toujours $d^* \le p^*$ (dualité faible) ; l'égalité (dualité forte) est fréquente pour un problème convexe, et garantie s'il vérifie Slater.
Piège classique : $\lambda_i \ge 0$ suppose une minimisation avec des contraintes écrites $g_i(x) \le 0$ ; réécris d'abord $\varphi(x) \ge c$ en $c - \varphi(x) \le 0$. Et sans qualification, un vrai minimum peut ne vérifier aucune condition KKT.
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Quelle propriété définit un ensemble convexe $C$ ?
Réponse : B. Ce point décrit le segment entre $x$ et $y$ quand $t$ parcourt $[0\,;\,1]$. Le piège A ne suffit pas : une couronne (un disque troué) est d'un seul tenant, mais le segment entre deux points opposés traverse le trou.
Question 2 : Laquelle de ces fonctions est convexe sur tout $\mathbb{R}$ ?
Réponse : D. Sa dérivée seconde vaut $e^{-x} > 0$ pour tout réel $x$. Le piège A : la dérivée seconde de $x^3$ est $6x$, négative pour $x \lt 0$, donc $x^3$ n'est convexe que sur $[0\,;\,+\infty[$.
Question 3 : Quand dit-on qu'une contrainte $g_i(x) \le 0$ est active en un point admissible $x^*$ ?
Réponse : A. Le point est alors sur le bord défini par la contrainte. Le piège C dit seulement que $x^*$ respecte la contrainte, comme tout point admissible.
Question 4 : On minimise $f$ sous des contraintes $g_i(x) \le 0$. Laquelle de ces conditions ne fait pas partie des conditions KKT en $x^*$ ?
Réponse : D. C'est le gradient du lagrangien qui s'annule (proposition C), pas celui de $f$ : dans l'exemple de l'essentiel, $f'(1) = 2 \neq 0$, et pourtant $x^* = 1$ est le minimum.
Question 5 : En un point KKT $x^*$, on a $g_1(x^*) = -2$. Que vaut le multiplicateur $\lambda_1$ ?
Réponse : C. La complémentarité impose $\lambda_1 g_1(x^*) = -2\lambda_1 = 0$ : une contrainte inactive a un multiplicateur nul. Le piège D garde la condition de signe et oublie la complémentarité.
Question 6 : Lequel de ces problèmes est un problème d'optimisation convexe ?
Réponse : B. L'objectif est convexe et la contrainte s'écrit $1 - x_1 - x_2 \le 0$, avec une fonction affine. Le piège A : une égalité doit être affine ; ici, l'ensemble admissible est un cercle, qui n'est pas convexe.
Question 7 : Dans un problème convexe, $x^*$ est un minimum local. Que peux-tu en conclure ?
Réponse : A. Tout minimum local d'un problème convexe est global. Le piège B : l'unicité demande $f$ strictement convexe ; pour $f(x_1, x_2) = x_1^2$, tous les points $(0\,;\,t)$ sont des minimums.
Question 8 : On minimise $f(x) = (x-3)^2$ sous la contrainte $g(x) = x - 1 \le 0$. Quel couple vérifie les conditions KKT ?
Réponse : C. La stationnarité donne $2(x-3) + \lambda = 0$. Avec $\lambda = 0$, on aurait $x = 3$, qui viole la contrainte ; elle est donc active : $x^* = 1$ et $\lambda = -2(1-3) = 4 \ge 0$. Le piège A oublie la contrainte : $x = 3$ minimise $f$ sans elle.
Question 9 : On minimise $(x_1-1)^2 + (x_2-2)^2$ sous $x_1 + x_2 \le 1$. Le minimum est atteint en $x^* = (0\,;\,1)$. Que vaut le multiplicateur $\lambda$ ?
Réponse : D. Avec $g(x) = x_1 + x_2 - 1$, la stationnarité donne $2(x_1-1) + \lambda = 0$ et $2(x_2-2) + \lambda = 0$ ; en $(0\,;\,1)$, les deux deviennent $-2 + \lambda = 0$, donc $\lambda = 2$. Le piège A suppose la contrainte inactive, alors que $0 + 1 = 1$ : elle est active.
Question 10 : Un problème de minimisation a pour valeur optimale $p^*$, et son dual $d^*$. Que peux-tu affirmer sans aucune hypothèse ?
Réponse : A. C'est la dualité faible, vraie même pour un problème non convexe. Le piège B est la dualité forte, qui demande des hypothèses, comme un problème convexe qui vérifie Slater.
Question 11 : Que demande la condition de Slater ?
Réponse : B. Il suffit d'un point admissible où toutes les inégalités sont strictes. Le piège A l'exige du minimum, qui se trouve souvent sur le bord, là où une contrainte est active.
Question 12 : Pour un problème convexe, qu'est-ce qui garantit la dualité forte $d^* = p^*$ ?
Réponse : C. C'est le théorème de Slater : convexité et condition de Slater donnent la dualité forte. Le piège A : pour un problème convexe, elle est fréquente, mais pas automatique.
Question 13 : Un problème convexe différentiable ne vérifie pas Slater, mais $\bar{x}$ vérifie les conditions KKT avec des multiplicateurs. Que peux-tu dire de $\bar{x}$ ?
Réponse : A. Dans un problème convexe, les KKT suffisent sans aucune qualification ; Slater ne sert qu'à l'autre sens, pour que tout minimum les vérifie. Le piège B confond les deux sens.
Question 14 : Pour minimiser $(x+1)^2$ sous $x \ge 0$, un étudiant pose $L(x, \lambda) = (x+1)^2 + \lambda x$ avec $\lambda \ge 0$, trouve $\lambda = -2$ en $x = 0$ et rejette ce point. Où est l'erreur ?
Réponse : D. Avec $\lambda \ge 0$, la contrainte doit s'écrire $g(x) = -x \le 0$ ; la stationnarité $2(x+1) - \lambda = 0$ donne alors $\lambda = 2$ en $x = 0$, qui est bien le minimum. Le piège A : avec $+\lambda x$, l'étudiant a traité la contrainte $x \le 0$.
Question 15 : On minimise $f(x) = x$ sous $x^2 \le 0$. Le seul point admissible, $x^* = 0$, est donc le minimum. Que donnent les conditions KKT en $x^* = 0$ ?
Réponse : B. En $x^* = 0$, la stationnarité $1 + 2\lambda x^* = 0$ devient $1 = 0$, quel que soit $\lambda$. Aucun point ne vérifie $x^2 \lt 0$, donc Slater tombe. Le piège D renverse la logique : sans qualification, un vrai minimum peut échapper aux KKT.
Sources
Stephen Boyd et Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, en libre accès : chapitres 4 (problèmes convexes) et 5 (dualité, conditions KKT).