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 : $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 $g i$ .

On suppose que la fonction f et les fonctions $g i$ 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

1 Première étape : multiplicateurs de Lagrange
2 Deuxième étape : conditions de premier ordre
3 Troisième étape : conditions supplémentaires
- 3.1 Remarques
4 Théorème
5 Article connexe

Première étape : multiplicateurs de Lagrange

Soit $\lambda = (\lambda_i)_{1 \le i \le m} \in \mathbb{R}_+^m$ un vecteur de m réels positifs ou nuls.

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.

Article connexe

L'article Conditions d'optimalité (dimension finie) explore de manière systématique et consistante les conditions d'optimalité des problèmes d'optimisation sans contrainte, avec contraintes d'égalité ou avec contraintes d'égalité et d'inégalité, non nécessairement convexes.

v · Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyédrique • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Optimisation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Articles principaux : Ensemble convexe • Fonction convexe Outils et résultats fondamentaux : Conditions de Kuhn-Tucker • Inégalité de Jensen Algorithmique : Méthodes de points intérieurs
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail de l'analyse

Catégorie :

Optimisation

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

Dictionnaires et Encyclopédies sur 'Academic'

Conditions de Kuhn-Tucker

Sommaire

Première étape : multiplicateurs de Lagrange

Deuxième étape : conditions de premier ordre

Troisième étape : conditions supplémentaires

Remarques

Théorème

Article connexe

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Conditions de Kuhn-Tucker

Sommaire

Première étape : multiplicateurs de Lagrange

Deuxième étape : conditions de premier ordre

Troisième étape : conditions supplémentaires

Remarques

Théorème

Article connexe

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link