Conditions de Karush-Kuhn-Tucker

En mathématiques, les conditions de Karush-Kuhn-Tucker ou anciennement conditions de Kuhn-Tucker sont une généralisation des multiplicateurs de Lagrange qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités.

Soit $f:\mathbb {R} ^{n}\to \mathbb {R}$, une fonction appelée fonction objectif, et des fonctions $g_{j}:\mathbb {R} ^{n}\to \mathbb {R}$, $1\leq j\leq m$, appelées contraintes. On suppose que $f$ et les $g_{j}$ sont de classe C¹.

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

Trouver $x^{*}\in \mathbb {R} ^{n}$ qui minimise $f$ sous les contraintes $g_{j}(x^{*})\leq 0$ pour tout $j$.

Théorème

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

Conditions du premier ordre

Le point $x^{*}$ est un point critique de $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 : $\nabla L_{\lambda }(x^{*})=0$, où $\nabla$ est le gradient, ou encore, en écrivant les dérivées partielles,

${\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 $j$, $1\leq j\leq m$

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

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

Remarques

Les conditions de relâchement supplémentaires impliquent que si $g_{j}(x^{*})<0$, alors $\lambda _{j}=0$. Autrement dit : si la $j$-ème contrainte n'est pas saturée, alors le multiplicateur de Lagrange associé est nul.

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

Application

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.

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

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

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

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

La fonction $f$ y est appelée fonction objectif. Le programme consiste à chercher les valeurs $(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.

Les contraintes peuvent prendre plusieurs formes distinctes:

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

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

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

${\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 $\lambda$ s'appellent les coefficients de Kuhn-Tucker ou multiplicateurs de Lagrange associés aux $j$ contraintes. Il y en a autant que de contraintes. Le coefficient $\lambda _{j}$ est associé à la contrainte $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 :

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

$\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

${\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 $x$ en fonction des $\lambda$ et les $\lambda$ en fonction des $x$ et de résoudre chacune de ces expressions $E$ pour $E=0$, les relations d'exclusion.

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

On peut dégager la proposition suivante : supposons que le problème $(\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 à $f$ la plus grande valeur sont solutions globales du problème.

À 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 $(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 $f$ et les fonctions $g_{j}$ sont convexes. C’est pourquoi on s’intéresse à l'optimisation convexe.

À 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 $x_{1}\geq 0,x_{2}\geq 0...\ \mathrm {et} \ x_{j}\geq 0$. et $\lambda _{1}\geq 0,\lambda _{2}\geq 0\ \mathrm {et} \ \lambda _{j}\geq 0$.

Lien externe

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