- Conditions de Karush-Kuhn-Tucker
-
Conditions de Kuhn-Tucker
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 :
fonction pseudo-concave de n variables (fonction objective) et
fonction quasi-concave (m représente le nombre de contraintes).
On note
: 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
qui maximise
sous contrainte
, c'est-à-dire résoudre :
-
- sous contrainte
.
- sous contrainte
Sommaire
Première étape : multiplicateurs de Lagrange
Soit
un vecteur de m nombres positifs (au sens large).
On appelle le Lagrangien la fonction :
.
Les λi sont appelés multiplicateurs de Lagrange associés à la i-ième contrainte.
Deuxième étape : conditions de premier ordre
On considère L comme fonction objective 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 :
, où l'opérateur
est le gradient.
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) :
.
Remarques
- la troisième étape implique que :
0 \Rightarrow \lambda_i = 0" style="max-width : 98%; height: auto; width: auto;" src="/pictures/frwiki/98/b0b88955be19a18aa8f2553a8391b68d.png" border="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
- sous contrainte
si et seulement si
est solution des conditions de Kuhn-Tucker.
- Portail des mathématiques
Catégorie : Optimisation
Wikimedia Foundation. 2010.