Conditions de Kuhn-Tucker

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir condition.

En mathématiques, les conditions de Kuhn-Tucker ou conditions de Karush-Kuhn-Tucker permettent de résoudre des problèmes d'optimisation sous contraintes non-linéaires d'inégalité.

Soient : f: \mathbb{R}^n\to \mathbb{R} fonction pseudo-concave de n variables (fonction objectif) et g: \mathbb{R}^n\to \mathbb{R}^m fonction quasi-concave (m représente le nombre de contraintes).

On note g(X)=(g_i(X))_{1 \le i \le m} : la fonction g résume les m contraintes gi.

On suppose que la fonction f et les fonctions gi admettent des dérivées partielles par rapport à chaque variable.

L'objectif est de trouver X^* \in \mathbb{R}^n qui maximise f(X) \, sous contrainte g(X) \ge 0, c'est-à-dire résoudre :

X^*\in \arg \max_{X \in \mathbb{R}^n} f(X)
sous contrainte g(X) \ge 0.

Sommaire

[modifier] Première étape : multiplicateurs de Lagrange

Soit \lambda = (\lambda_i)_{1 \le i \le m} \in \mathbb{R}_+^m un vecteur de m nombres positifs (au sens large).

On appelle le Lagrangien la fonction :

L(X, \lambda) = f(X) + \sum_{i=1}^m \lambda_i g_i(X).

Les λi sont appelés multiplicateurs de Lagrange associés à la i-ième contrainte.

[modifier] Deuxième étape : conditions de premier ordre

On considère L comme fonction objectif d'un problème de maximisation (en fonction de X) sans contrainte. On écrit les conditions de premier ordre (conditions nécessaires) pour maximiser L en fonction de X :

\frac{\partial f}{\partial X}(X) + \sum_{i=1}^m \lambda_i \frac{\partial g_i}{\partial X}(X)=0, où l'opérateur \frac{\partial}{\partial X} est le gradient.

[modifier] Troisième étape : conditions supplémentaires

On écrit les conditions de relâchement supplémentaires ("complementary slackness conditions") et les conditions de positivité (conditions suffisantes) :

\forall i \in \{1, ..., m\}, \min [\lambda_i, g_i(X)] = 0.

[modifier] Remarques

  • la troisième étape implique que : \lambda_i \ge 0\quad \forall i \in \{1, ..., m\} ;
  • la troisième étape implique également que : g_i(X)>0 \Rightarrow \lambda_i = 0 : si la contrainte i n'est pas saturée, le multiplicateur de Lagrange associé à cette contrainte est nul ;
  • les conditions de premier ordre et les conditions de relâchement supplémentaires sont appelées conditions de Kuhn-Tucker.

[modifier] Théorème

X^*\in \arg \max_{X \in \mathbb{R}^n} f(X)

sous contrainte g(X) \ge 0

si et seulement si (X^*, \lambda^*) \, est solution des conditions de Kuhn-Tucker.