Conditions de Karush-Kuhn-Tucker

Si ${\displaystyle f}$ admet un minimum en ${\displaystyle x^{*}}$sous les contraintes ${\displaystyle g_{j}(x^{*})\leq 0}$ pour tout ${\displaystyle j}$, alors il existe ${\displaystyle (\lambda _{j})_{1\leq j\leq m}\in \mathbb {R} ^{m}}$ vérifiant les conditions suivantes, dites conditions de Kuhn-Tucker. On dit alors que ${\displaystyle \lambda _{j}}$ est le multiplicateur de Lagrange associé à la ${\displaystyle j}$-ème contrainte.

Conditions du premier ordre

Le point ${\displaystyle x^{*}}$ est un point critique de ${\displaystyle L_{\lambda }:x\longmapsto f(x)+\sum _{j=1}^{m}\lambda _{j}g_{j}(x)}$, le lagrangien du problème. Autrement dit, le gradient du lagrangien s'annule en ce point : ${\displaystyle \nabla L_{\lambda }(x^{*})=0}$, où ${\displaystyle \nabla }$ est le gradient, ou encore, en écrivant les dérivées partielles,

${\displaystyle {\frac {\partial f}{\partial x_{k}}}(x^{*})+\sum _{j=1}^{m}\lambda _{j}{\frac {\partial g_{j}}{\partial x_{k}}}(x^{*})=0,\ 1\leq k\leq n}$

Conditions de relâchement supplémentaires

Pour tout ${\displaystyle j}$, ${\displaystyle 1\leq j\leq m}$

• ${\displaystyle \lambda _{j}\geq 0}$
• ${\displaystyle \lambda _{j}=0}$ ou ${\displaystyle g_{j}(x^{*})=0}$.

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

En pratique, 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[5].

On utilise fréquemment les conditions de Karush-Kuhn Tucker pour résoudre des programmes d’optimisation convexe de type[6]:

${\displaystyle P{\begin{cases}\min f(x)\\g(x)\leq b\\x\geq 0\end{cases}}}$

où ${\displaystyle x=(x_{1},...,x_{n})}$ est un élément de ${\displaystyle R^{n}}$, ${\displaystyle b}$ est une contraine de type ${\displaystyle c_{j}}$ et ${\displaystyle g}$ est une fonction de ${\displaystyle R^{n}}$ dans ${\displaystyle R^{m}}$ de telle sorte que :

${\displaystyle g(x)=(g_{1}(x),...,g_{m}(x))}$

La fonction ${\displaystyle f}$ y est appelée fonction objectif. Le programme consiste à chercher les valeurs ${\displaystyle (x_{1},x_{2},...,x_{n})}$ ) pour laquelle la valeur de cette fonction est minimale (ou maximale) sous les contraintes. On appelle optimum la solution d’un programme d’optimisation : il s’agit soit d’un minimum, soit d’un maximum[6].

Les contraintes peuvent prendre plusieurs formes distinctes[6]:

• contraintes en équations : ${\displaystyle g_{j}(x_{1},...,x_{n})=c_{j},\forall j=1,...,m}$
• contraintes en inéquation : ${\displaystyle g_{j}(x_{1},...,x_{n})\leq c_{j},\forall j=1,...,m}$
• contraintes de non-négativité : ${\displaystyle x_{i}\geq 0,\forall i=1,...,n}$

Deux situations sont envisageables pour ces contraintes ${\displaystyle j}$. Avec ${\displaystyle x^{*}}$ la solution de ce programme, on dit que pour ${\displaystyle g_{j}(x^{*})=c_{j}}$ la contrainte ${\displaystyle j}$ est saturée à l'optimum et pour ${\displaystyle g_{j}(x*)<c_{j}}$ la contrainte ${\displaystyle j}$ est non saturée à l'optimum.

En supposant que les fonctions ${\displaystyle f}$ et ${\displaystyle g}$ sont continûment différentiables, le lagrangien associé à ce programme est la fonction

${\displaystyle {\begin{aligned}L(x,\lambda )&=f(x)-\lambda \cdot (g(x)-b)\\&=f(x)-\lambda _{1}\times (g_{1}(x)-b_{1})-\ldots -\lambda _{m}\times (g_{m}(x)-b_{m})\\\end{aligned}}}$

Les coefficients ${\displaystyle \lambda }$ s'appellent les coefficients de Kuhn-Tucker ou multiplicateurs de Lagrange associés aux ${\displaystyle j}$ contraintes. Il y en a autant que de contraintes. Le coefficient ${\displaystyle \lambda _{j}}$ est associé à la contrainte ${\displaystyle g_{j}(x)\ll b_{j}}$.

Pour résoudre un tel programme, il faudra poser les conditions de Kuhn-Tucker, qui sont des conditions nécessaires réalisées à l'optimum du problème. Elles s'écrivent vectoriellement ainsi :

${\displaystyle \nabla _{x}L\leq 0,x\geq 0,x\cdot \nabla _{x}L=0}$

${\displaystyle \nabla _{\lambda }L\geq 0,\lambda \geq 0,\lambda \cdot \nabla _{\lambda }L=0}$.

En pratique, il s'agira de reprendre le lagrangien associé au programme

${\displaystyle {\begin{aligned}L(x,\lambda )&=f(x)-\lambda \cdot (g(x)-b)\\&=f(x)-\lambda _{1}(g_{1}(x)-b_{1})-\ldots -\lambda _{m}(g_{m}(x)-b_{m})\end{aligned}}}$

d'exprimer les variables ${\displaystyle x}$ en fonction des ${\displaystyle \lambda }$ et les ${\displaystyle \lambda }$ en fonction des ${\displaystyle x}$ et de résoudre chacune de ces expressions ${\displaystyle E}$ pour ${\displaystyle E=0}$, les relations d'exclusion.

Les valeurs qui s'en dégagent pour les variables ${\displaystyle x}$ et ${\displaystyle \lambda }$ sont solutions du problème de minimisation ${\displaystyle (\mathrm {P} )}$.

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[7].

À noter que qu'en toute généralité, les conditions de Kuhn-Tucker sont des conditions nécessaires, autrement dit, si on est en un point optimum, elles sont toujours réalisées. Mais elles ne sont pas forcément suffisantes : autrement dit, ce n’est pas parce qu’elles sont réalisées en un point ${\displaystyle (x,\lambda )}$ que ce point est obligatoirement un optimum. Néanmoins, il existe des situations où on peut affirmer qu’elles sont effectivement suffisantes. C’est le cas en particulier lorsque la fonction ${\displaystyle f}$ et les fonctions ${\displaystyle g_{j}}$ sont convexes. C’est pourquoi on s’intéresse à l'optimisation convexe[6].

À noter également qu'il y a la plupart du temps des conditions de signe sur les variables, c'est-à-dire que les variables doivent être positives, typiquement ${\displaystyle x_{1}\geq 0,x_{2}\geq 0...\ \mathrm {et} \ x_{j}\geq 0}$. et ${\displaystyle \lambda _{1}\geq 0,\lambda _{2}\geq 0\ \mathrm {et} \ \lambda _{j}\geq 0}$[6].

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