Conditions de Karush-Kuhn-Tucker

En mathématiques, les conditions de Karush-Kuhn-Tucker^[1], parfois appelées conditions de Kuhn-Tucker^[2] ou Théorème KKT sont des critères d'optimalité qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités et d'égalité ^[3].

Soit ${\displaystyle f:E\to \mathbb {R} }$ une fonction appelée fonction objectif, d'un ouvert ${\displaystyle E\subseteq \mathbb {R} ^{d}}$ dans ${\displaystyle \mathbb {R} }$, ${\displaystyle (g_{j}:E\to \mathbb {R} )_{j\in J}}$ une famille de contraintes d'inégalité, et ${\displaystyle (h_{i}:E\to \mathbb {R} )_{i\in I}}$ une famille de contraintes d'égalité. On suppose que ${\displaystyle f}$, ${\displaystyle (g_{j})_{j\in J}}$ et ${\displaystyle (h_{i})_{i\in I}}$ sont dérivables sur leurs domaines^[4].

Le problème à résoudre est le suivant :

Trouver ${\displaystyle x^{*}\in \mathbb {R} ^{n}}$ qui minimise ${\displaystyle f}$ sous les contraintes d'inégalité ${\displaystyle g_{j}(x^{*})\leq 0\quad \forall j\in J}$, et les contraintes d'égalité ${\displaystyle h_{i}(x^{*})=0\quad \forall i\in I}$.

Maximiser ${\displaystyle f}$ revient à minimiser ${\displaystyle (-f)}$, aussi, sans perte de généralité et par convention, on se placera systématiquement dans un cadre de minimisation. Par ailleurs, si ${\displaystyle f}$ est convexe, ${\displaystyle (-f)}$ est concave, aussi tout problème de minimisation convexe est équivalent à un problème de maximisation concave.

Si ${\displaystyle f}$ et les familles de fonction ${\displaystyle (g_{j})_{j\in J},(h_{i})_{i\in I}}$ sont différentiables, si ${\displaystyle f}$ admet un minimum local en ${\displaystyle x^{*}}$sous les contraintes ${\displaystyle g_{j}(x^{*})\leq 0}$ pour tout ${\displaystyle j\in J}$ et ${\displaystyle h_{i}(x^{*})=0}$ pour tout ${\displaystyle i\in I}$, alors il existe ${\displaystyle (\lambda _{j})_{1\leq j\leq m}\in (\mathbb {R} ^{+})^{m},(\mu _{i})_{1\leq i\leq n}\in \mathbb {R} ^{n}}$ vérifiant les conditions suivantes, dites conditions de Karush-Kuhn-Tucker :

${\displaystyle {\begin{cases}\nabla \left[f(x^{*})+\sum _{j\in J}\lambda _{j}g_{j}(x^{*})+\sum _{i\in I}\mu _{i}h_{i}(x^{*})\right]=0\\\forall j\in J,g_{j}(x^{*})\leq 0,\quad \lambda _{j}\geq 0,\quad et\quad \lambda _{j}g_{j}(x^{*})=0\\\forall i\in I,h_{i}(x^{*})=0\end{cases}}}$

Ces contraintes sont généralement appelées "conditions KKT du premier ordre" ou "condition d'optimalité de premier ordre"

On appelle le Lagrangien du problème l'expression suivante, dont la première ligne des conditions KKT est le gradient au point ${\displaystyle x^{*}}$:

$${\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {\mu } ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )}$$

On dit que ${\displaystyle (\lambda _{j}}$) est le multiplicateur de Lagrange associé à la ${\displaystyle j}$-ème contrainte d'inégalité.

La deuxième ligne implique que si ${\displaystyle g_{j}(x^{*})<0}$, alors ${\displaystyle \lambda _{j}=0}$. Autrement dit : si la ${\displaystyle j}$-ème contrainte n'est pas saturée, alors le multiplicateur de Lagrange associé est nul.

On peut également écrire, de façon plus compacte, que pour tout ${\displaystyle j}$, ${\displaystyle \min[\lambda _{j},\ |g_{j}(x^{*})|\ ]=0}$.

La première ligne de l'expression est parfois écrite ${\displaystyle x^{*}}$ est un point critique du Lagrangien, ou ${\displaystyle x^{*}}$ est un point selle du Lagrangien.

La démonstration de ce résultat repose essentiellement sur le lemme de Farkas.

Le théorème de Karush Kuhn et Tucker est rarement utile en tant que tel : il nous dit que si ${\displaystyle x^{*}}$ est une solution locale du problème d'optimisation, alors il existe deux vecteurs ${\displaystyle (\lambda ^{*},\mu ^{*})}$, avec ${\displaystyle \lambda ^{*}}$ un vecteur à coefficients positifs, tels que le gradient du lagrangien s'annule. Cependant, cela ne nous permet pas de déterminer l'optimum du problème d'optimisation. Afin de ce faire, on utilise la réciproque - ou condition suffisante - du théorème KKT (laquelle requiert des hypothèses plus fortes) :

Supposons que ${\displaystyle f}$ soit convexe sur ${\displaystyle E}$, que les fonctions ${\displaystyle (g_{j})_{j\in J}}$ soient convexes sur ${\displaystyle E}$, et que les fonctions ${\displaystyle (h_{i})_{i\in I}}$ soient affines sur ${\displaystyle E}$. Toutes ces fonctions sont toujours supposées dérivables sur ${\displaystyle E}$. Si le problème est qualifié, ou, plus simplement, si la condition de Slater est vérifiée, i.e. s'il existe ${\displaystyle \alpha \in E}$ tel que ${\displaystyle \forall j\in J,g_{j}(\alpha )<0}$, alors les propositions suivantes sont équivalentes:

• ${\displaystyle x^{*}}$ est un minimum local du problème d'optimisation

• ${\displaystyle x^{*}}$ est un minimum global du problème d'optimisation

• ${\displaystyle x^{*}}$ vérifie les conditions KKT

Ainsi, sous les conditions suffisantes susmentionnées, tout point vérifiant les conditions KKT est un minimum global, ce qui nous donne une méthodologie pour trouver le minimum global ${\displaystyle x^{*}}$: chercher les points où les conditions KKT sont vérifiées.

Ces résultats peuvent être appréhendés dans le cadre de l'optimisation duale.

Sans détailler, la base de la dualité en optimisation est de reformuler un problème de minimisation, le problème primal, sous la forme d'un problème de maximisation formulé dans un autre espace, le problème dual, que l'on espère plus simple à résoudre.

Dans le cas général, une solution du problème primal de minimisation donne une borne supérieur à toute solution du problème dual, et une solution du problème dual (de maximisation) donne une borne inférieure au problème primal - la dualité est dite faible : il y a une différence entre la solution du problème primal et celle du problème dual, différence que l'on appelle un saut de dualité. Dans le cadre spécifique d'un problème d'optimisation convexe, on peut prouver que, sous certaines conditions dites conditions de qualification, le saut de dualité est nul, aussi la solution du problème dual est la même que celle du problème primal.

Ainsi, la condition nécessaire du théorème KKT implique que tout point ${\displaystyle x^{*}}$ solution du primal est solution du dual lagrangien au point ${\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}$ (le gradient du Lagrangien est une fonction localement affine pour ${\displaystyle x^{*}}$ fixé, le lagrangien est donc concave sous la condition de positivité des ${\displaystyle \lambda _{i}}$).

La condition suffisante du théorème KKT, elle, indique que, si le problème d'optimisation est convexe et qualifié, alors le saut de dualité est nul, et la solution du problème dual lagrangien est solution du problème primal (la qualification est une condition suffisante de dualité forte d'un problème convexe).

La condition de Slater est une des conditions suffisantes de qualification les plus fortes, mais aussi l'une des plus faciles à vérifier, aussi c'est généralement celle qui est la plus étudiée.

Une autre condition de qualification plus générale (probablement la plus générale) mais plus difficile à utiliser est la condition LICQ (Linear independence constraint qualification, qualification par indépendance linéaire des contraintes), qui stipule que le problème est qualifié si les gradients des contraintes d'inégalité actives et des contraintes d'égalité sont linéairement indépendants en ${\displaystyle x^{*}}$.

L'une des sources francophones les plus exhaustives sur le sujet est le Fragments d'optimisation différentiable - Théorie et algorithmes de Jean Charles Gilbert, disponible en ligne^[5].

Afin d'illustrer, résolvons un exercice d'optimisation KKT^[6] :

Soit ${\displaystyle f:x,y\in \mathbb {R} ^{2}\longmapsto x^{2}+y^{2}}$. On définit le problème d'optimisation suivant :

${\displaystyle (P){\begin{cases}\min f(x)\\x\geq 0\\y\geq 0\\x+2y=4\end{cases}}}$

Que l'on réécrira sous la forme du problème convexe ${\displaystyle (P){\begin{cases}\min f(x)\\-x\leq 0\\-y\leq 0\\x+2y-4=0\end{cases}}}$.

${\displaystyle f}$ est continue sur ${\displaystyle K=\{(x,y)\in (\mathbb {R^{+}} )^{2}|x+2y-4=0\}}$.

${\displaystyle K}$ est :

• Fermé comme l'intersection de deux ensembles fermés :
  • L'image réciproque du fermé ${\displaystyle \{0\}}$ par l'application continue ${\displaystyle (x,y)\to x+2y-4}$
  • Le fermé ${\displaystyle (\mathbb {R} ^{+})^{2}}$, lui même fermé comme produit cartésien de deux fermés (${\displaystyle \mathbb {R} ^{+}}$étant un fermé)

• Borné : ${\displaystyle \forall (x,y)\in K,||(x,y)||\leq 4}$
• En dimension finie

${\displaystyle K}$ est donc compact (via le Lemme de Riesz), et ${\displaystyle f}$ atteint ses bornes sur ${\displaystyle K}$, ce qui nous permet d'obtenir l'existence et l'unicité du minimum. Il faut noter que l'unicité du minimum réfère l'unicité de la valeur du minimum : le minimum n'est pas forcément atteint qu'en un seul point (à titre d'exemple, une fonction constante est convexe et admet un unique minimum, qu'elle atteint en chaque point où elle est définie).

Dans un premier temps, sachant que ${\displaystyle f}$ est une fonction ${\displaystyle {\mathcal {C}}^{2}}$ (ce qui nous permet d'utiliser le Théorème de Schwarz) comme polynôme de deux variables, on peut vérifier sa convexité:

${\displaystyle {\begin{cases}{\frac {\partial ^{2}f}{\partial x^{2}}}=2\\{\frac {\partial ^{2}f}{\partial x\partial y}}={\frac {\partial ^{2}f}{\partial y\partial x}}=0\quad {\text{(Theoreme de Schwarz)}}\\{\frac {\partial ^{2}f}{\partial y^{2}}}=2\end{cases}}}$

La matrice hessienne de ${\displaystyle f}$ est définie positive (il s'agit de ${\displaystyle {\begin{bmatrix}2&0\\0&2\end{bmatrix}}}$, dont les valeurs propres (2, dont le sous espace propre est de dimension 2) sont strictement positives), donc ${\displaystyle f}$ est convexe.

Les contraintes d'inégalité sont affines (${\displaystyle g_{1}(x,y)=-x,\quad g_{2}(x,y)=-y}$), donc convexes, et la contrainte d'égalité est également affine (${\displaystyle h_{1}(x,y)=x+2y-4}$).

On peut choisir un point vérifiant strictement les contraintes d'inégalité, par exemple ${\displaystyle (2,1)}$ : la condition de Slater est donc vérifiée, le problème est qualifié.

On peut donc écrire le Lagrangien :

${\displaystyle {\mathcal {L}}(x,y,\lambda ,\mu _{1},\mu _{2})=f(x,y)+\lambda h_{1}(x,y)+\mu _{1}g_{1}(x,y)+\mu _{2}g_{2}(x,y)=x^{2}+y^{2}+\lambda (x+2y-4)-\mu _{1}x-\mu _{2}y}$

Ce qui, par application du théorème KKT, nous permet d'écrire le système suivant:

${\displaystyle {\begin{cases}{\frac {\partial {\mathcal {L}}}{\partial x}}=2x+\lambda -\mu _{1}=0\\{\frac {\partial {\mathcal {L}}}{\partial y}}=2y+2\lambda -\mu _{2}=0\\x+2y-4=0\\\mu _{1}x=0\\\mu _{2}y=0\\\mu _{1}\geq 0\\\mu _{2}\geq 0\end{cases}}}$

À partir de ce point, il faut procéder à une analyse systématique afin de trouver la solution du problème :

• Commençons par supposer ${\displaystyle \mu _{1}>0}$. Alors ${\displaystyle x=0}$ (car ${\displaystyle \mu _{1}x=0}$), donc ${\displaystyle y=2}$ (car ${\displaystyle x+2y-4=0}$), donc ${\displaystyle \mu _{2}=0}$ (car ${\displaystyle \mu _{2}y=0}$). Par conséquent, en reprenant la deuxième équation du système, on a ${\displaystyle 2\lambda +2y=0}$, soit ${\displaystyle \lambda =-y=-2}$. En reprenant la première équation du système, on obtient alors ${\displaystyle \mu _{1}=\lambda =-2}$, ce qui contredit l'hypothèse initiale. Donc ${\displaystyle \mu _{1}=0}$.

• Supposons à présent ${\displaystyle \mu _{2}>0}$. Cela nous donne ${\displaystyle y=0}$ (car ${\displaystyle \mu _{2}y=0)}$, donc ${\displaystyle x=4}$ (car ${\displaystyle x+2y-4=0}$), soit en reprenant la première équation ${\displaystyle \lambda =-2x=-8}$, ce qui, en reprenant la deuxième équation, donne ${\displaystyle \mu _{2}=2y+2\lambda =-16}$, ce qui contredit l'hypothèse.

• On suppose donc enfin que ${\displaystyle \mu _{2}=0}$. Le système se réécrit alors

${\displaystyle {\begin{cases}2x+\lambda =0\\2y+2\lambda =0\\x+2y-4=0\end{cases}}\iff {\begin{cases}\lambda =-2x\\y=2x\\x+2y=5x=4\end{cases}}\iff {\begin{cases}x={\frac {4}{5}}\\y={\frac {8}{5}}\\\lambda =-{\frac {8}{5}}\end{cases}}}$

Ainsi, le système KKT possède une unique solution au point ${\displaystyle ({\frac {4}{5}},{\frac {8}{5}})}$ valant ${\displaystyle {\frac {16}{5}}}$.

Comme vu ci-dessus, la résolution des conditions de Kuhn et Tucker est compliquée par le fait qu’il faut envisager successivement toutes les configurations possibles : toutes les contraintes sont saturées à l’équilibre, toutes sauf une, deux, ..., aucune (tous les λ_j sont nuls à l’équilibre). Pour trouver la bonne solution, il faut procéder par élimination, en montrant que parmi l’ensemble de ces possibilités, certaines aboutissent à des contradictions^[7].

On peut dégager la proposition suivante : supposons que le problème ${\displaystyle (\mathrm {P} )}$ possède une solution globale, et supposons qu'il existe des candidats fournis par les conditions de Kuhn et Tucker, alors parmi ces candidats ceux qui donnent à ${\displaystyle f}$ la plus grande valeur sont solutions globales du problème^[8].

Dans les faits, on utilise généralement un solveur algorithmique pour procéder à l'analyse des conditions KKT dans les problèmes d'optimisation convexes.

Dans certains cas (relativement rares), il est possible d'avoir une infinité de solutions du problème KKT. Par exemple, l'application convexe ${\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ,f:(x,y)\to (x-y)^{2}}$ peut être minimisée sous la contrainte ${\displaystyle x^{2}+y^{2}\leq 1}$, cela donnera comme minimum ${\displaystyle 0}$, atteint en tout point de la droite d'équation ${\displaystyle y=-x}$ interne à la boule fermée unité selon la norme euclidienne.

• Jeremy Kun, « Duality for the SVM », 12 juin 2017 (utilisation du théorème en apprentissage statistique)

• Portail de l'analyse