Conditions de Karush-Kuhn-Tucker

(Redirigé depuis Conditions de Kuhn-Tucker)

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

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

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

Trouver qui maximise sous les contraintes pour tout .

ThéorèmeModifier

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 ordreModifier

  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émentairesModifier

Pour tout  ,  
  •  
  •   ou  .

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

RemarquesModifier

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.

La démonstration de ce résultat repose essentiellement sur le lemme de Farkas.

RéciproqueModifier

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 concaves.

Notes et référencesModifier

  1. (en) W. Karush, Minima of Functions of Several Variables with Inequalities as Side Constraints, Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois,
  2. William Karush fut le premier à énoncer ce résultat en 1939. Mais son travail fut redécouvert longtemps après la publication de Kuhn et Tucker.
  3. (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.
  4. Pour plus de détails sur les conditions de régularité imposées, voir « Conditions d'optimalité (dimension finie) ».

Lien externeModifier