Conditions de Karush-Kuhn-Tucker

En mathématiques, les conditions de Karush-Kuhn-Tucker ou anciennement conditions de Kuhn-Tucker sont une généralisation des multiplicateurs de Lagrange qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités. Soit , une fonction appelée fonction objectif, et des fonctions , , appelées contraintes. On suppose que et les sont de classe C. Le problème à résoudre est le suivant : Si admet un minimum 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. Le point est un point critique de , le lagrangien du problème. Autrement dit, le gradient du lagrangien s'annule en ce point : , où est le gradient, ou encore, en écrivant les dérivées partielles, On peut également écrire, de façon plus compacte, que pour tout , . 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. En pratique, la résolution des conditions de Kuhn et Tucker est compliquée par le fait qu’il faut envisager successivement toutes les configurations possibles : toutes les contraintes sont saturées à l’équilibre, toutes sauf une, deux, ..., aucune (tous les λ sont nuls à l’équilibre). Pour trouver la bonne solution, il faut procéder par élimination, en montrant que parmi l’ensemble de ces possibilités, certaines aboutissent à des contradictions. On utilise fréquemment les conditions de Karush-Kuhn Tucker pour résoudre des programmes d’optimisation convexe de type: où est un élément de , est une contraine de type et est une fonction de dans de telle sorte que : La fonction y est appelée fonction objectif. Le programme consiste à chercher les valeurs ) pour laquelle la valeur de cette fonction est minimale (ou maximale) sous les contraintes.