Conditions de Kuhn-Tucker

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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és[1].

Soit , une fonction appelée fonction objectif, et des fonctions , , appelées contraintes. On suppose que et les sont de classe C1[2].

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

Trouver qui maximise sous les contraintes pour tout .

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

Si admet un maximum en sous les contraintes pour tout , alors il existe vérifiant les conditions suivantes, dites conditions de Kuhn-Tucker. On dit alors que est le multiplicateur de Lagrange associé à la -ème contrainte.

Conditions du premier ordre[modifier | modifier le code]

est un point critique de , le Lagrangien du problème. Autrement dit, , où est le gradient, ou encore, en écrivant les dérivées partielles,

,

Conditions de relâchement supplémentaires[modifier | modifier le code]

Pour tout ,
  • ou .

On peut également écrire, de façon plus compacte, que pour tout , .

Remarque[modifier | modifier le code]

Les conditions de relâchement supplémentaires impliquent que si , alors . Autrement dit : si la -ème contrainte n'est pas saturée, alors le multiplicateur de Lagrange associé est nul.

Réciproque[modifier | modifier le code]

Ce théorème ne fournit a priori que des conditions nécessaires. Cependant, sous certaines conditions, ce sont également des conditions suffisantes. C'est notamment le cas si et les fonctions sont convexes.

Notes et références[modifier | modifier le code]

  1. (en) H. W. Kuhn et A. W. Tucker, « Nonlinear programming », dans Proceedings of 2nd Berkeley Symposium, Berkeley, University of California Press, (Math Reviews 47303, lire en ligne), p. 481-492.
  2. Pour plus de détails sur les conditions de régularité imposées, voir « Conditions d'optimalité (dimension finie) ».

Lien externe[modifier | modifier le code]