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 [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 contrainte , 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[modifier | modifier le code]

  1. (en) H. W. Kuhn et A. W. Tucker (1951). « Nonlinear programming » University of California Press Proceedings of 2nd Berkeley Symposium: 481–492, Berkeley: University of California Press.  lien Math Reviews
  2. Pour plus de détails sur les condtions de régularité imposées, voir Conditions d'optimalité (dimension finie).