Conditions De Kuhn-Tucker


Conditions De Kuhn-Tucker

Conditions de Kuhn-Tucker

Page d'aide sur l'homonymie Pour les articles homonymes, voir condition.

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 : f: \mathbb{R}^n\to \mathbb{R} fonction pseudo-concave de n variables (fonction objective) et g: \mathbb{R}^n\to \mathbb{R}^m fonction quasi-concave (m représente le nombre de contraintes).

On note g(X)=(g_i(X))_{1 \le i \le m} : 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 X^* \in \mathbb{R}^n qui maximise f(X) \, sous contrainte g(X) \ge 0, c'est-à-dire résoudre :

X^*\in \arg \max_{X \in \mathbb{R}^n} f(X)
sous contrainte g(X) \ge 0.

Sommaire

Première étape : multiplicateurs de Lagrange

Soit \lambda = (\lambda_i)_{1 \le i \le m} \in \mathbb{R}_+^m un vecteur de m nombres positifs (au sens large).

On appelle le Lagrangien la fonction :

L(X, \lambda) = f(X) + \sum_{i=1}^m \lambda_i g_i(X).

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 :

\frac{\partial f}{\partial X}(X) + \sum_{i=1}^m \lambda_i \frac{\partial g_i}{\partial X}(X)=0, où l'opérateur \frac{\partial}{\partial X} 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) :

\forall i \in \{1, ..., m\}, \min [\lambda_i, g_i(X)] = 0.

Remarques

  • la troisième étape implique que :  g_i(X)>0 \Rightarrow \lambda_i = 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

X^*\in \arg \max_{X \in \mathbb{R}^n} f(X)

sous contrainte g(X) \ge 0

si et seulement si (X^*, \lambda^*) \, est solution des conditions de Kuhn-Tucker.

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Conditions de Kuhn-Tucker ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Conditions De Kuhn-Tucker de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Conditions de kuhn-tucker — Pour les articles homonymes, voir condition. 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 :… …   Wikipédia en Français

  • Conditions de Kuhn-Tucker — Pour les articles homonymes, voir condition. 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 :… …   Wikipédia en Français

  • Conditions de Karush-Kuhn-Tucker — Conditions de Kuhn Tucker Pour les articles homonymes, voir condition. 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… …   Wikipédia en Français

  • Karush–Kuhn–Tucker conditions — In mathematics, the Karush–Kuhn–Tucker (KKT) conditions (also known as the Kuhn–Tucker conditions) are necessary for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality… …   Wikipedia

  • Kuhn — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Patronyme Kuhn, ou Kühn, est le nom de personnalités (par ordre alphabétique) : Adam Kuhn (1741 1817), un médecin et naturaliste américain, Alvin… …   Wikipédia en Français

  • Conditions d'optimalité (dimension finie) — En optimisation mathématique, les conditions d optimalité sont un ensemble d équations, d inéquations (i.e., des inégalités) et d expressions diverses (e.g., la semi définie positivité de matrices sur des cônes) vérifiées par une solution d un… …   Wikipédia en Français

  • Albert W. Tucker — Infobox Scientist name = Albert W. Tucker image width = 300px caption = Albert William Tucker birth date = birth date|1905|11|28|df=y birth place = Ontario, Canada death date = death date and age|1995|1|25|1905|11|28|df=y death place = Highstown …   Wikipedia

  • Albert William Tucker — Albert W. Tucker Albert William Tucker (28 novembre 1905 25 janvier 1995) était un mathématicien américain d origine canadienne qui a produit d importantes contributions en topologie, théorie des jeux et programmation non… …   Wikipédia en Français

  • Albert W. Tucker — Albert William Tucker (28 novembre 1905 25 janvier 1995) était un mathématicien américain d origine canadienne qui a produit d importantes contributions en topologie, théorie des jeux et optimisation non linéaire. Biographie… …   Wikipédia en Français

  • Albert W. Tucker — Nacimiento 28 de noviembre de 1905 Ontario, Canadá Fallecimiento 25 de enero, 1995 Highstown, N.J., Estados Unidos Residencia …   Wikipedia Español