Conditions de Kuhn-Tucker

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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, en anglais objective function) 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 g_i.

On suppose que la fonction f et les fonctions g_i 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.

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

Soit \lambda = (\lambda_i)_{1 \le i \le m} \in \mathbb{R}_+^m un vecteur de m réels positifs ou nuls.

On appelle le Lagrangien la fonction :

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

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

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

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.

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

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.

Remarques[modifier | modifier le code]

  • la troisième étape implique 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.

Théorème[modifier | modifier le code]

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.

Article connexe[modifier | modifier le code]