# 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$^1$ sur leur domaine.
Le problème à résoudre est le suivant :
$x^{*}\in \mathbb {R} ^{n}$
$f$
$g_{j}(x^{*})\leq 0$
$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

$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 $\mathbb {R} ^{n}$, $b$ est une contraine de type $c_{j}$ et $g$ est une fonction de $\mathbb {R} ^{n}$ dans $\mathbb {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$.