Conditions de Karush-Kuhn-Tucker

Si ${\displaystyle f}$ admet un maximum en ${\displaystyle x^{*}}$sous les contraintes ${\displaystyle g_{i}(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

${\displaystyle x^{*}}$ est un point critique de ${\displaystyle L_{\lambda }:x\longmapsto f(x)+\sum _{j=1}^{m}\lambda _{j}g_{j}\mathrm {\textvisiblespace} (x)}$, le lagrangien du problème. Autrement dit, ${\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}Maxf(x)\\g(x)<b\\x>0\end{cases}}}$

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

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

Les contraintes peuvent prendre plusieurs formes distinctes[6]:

• contraintes en équations: ${\displaystyle gj(x1,x2,...,xn)=c_{j},\forall j=1,...,m}$
• contraintes en inéquation: ${\displaystyle gj(x1,x2,...,xn)\leq c_{j},\forall j=1,...,m}$
• contraintes de non-négativité: ${\displaystyle xi\gg 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 \times (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 coefficents 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 gj(x)\ll bj}$.

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 \bigtriangledown xL\leq 0,x\geq 0,x\times \bigtriangledown xL=0}$

et:

${\displaystyle \bigtriangledown \lambda L\geq 0,\lambda \geq 0,\lambda \times \bigtriangledown \lambda L=0}$.

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

${\displaystyle {\begin{aligned}L(x,\lambda )&=f(x)-\lambda \times (g(x)-b)\\&=f(x)-\lambda 1\times (g_{1}(x)-b_{1})-\ldots -\lambda m\times (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 maximisation ${\displaystyle (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éement 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}$ est concave 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}\gg 0,x_{2}\gg 0...et\mathrm {\textvisiblespace} x_{j}\geq 0}$. et ${\displaystyle \lambda _{1}\geqslant 0,\lambda _{2}\geqslant 0\mathrm {\textvisiblespace} et\mathrm {\textvisiblespace} \lambda _{j}\geq 0}$[6].

Ce théorème ne fournit a priori que des conditions nécessaires. Cependant, sous certaines conditions, ce sont également des conditions suffisantes. C'est notamment le cas si ${\displaystyle f}$ et les fonctions ${\displaystyle g_{i}}$ sont concaves.

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

• Portail de l'analyse