|
|
Zeile 79: |
Zeile 79: |
| then form the KKT conditions 1-6 of the minimization | | then form the KKT conditions 1-6 of the minimization |
| | | |
− | [[Datei:BSP20.gif]] | + | (1) [[Datei:BSP20.gif]] |
| | | |
− | [[Datei:BSP21.gif]] | + | (1) [[Datei:BSP21.gif]] |
| | | |
− | [[Datei:BSP2.3.gif]] | + | (1) [[Datei:BSP2.3.gif]] |
| | | |
− | [[Datei:BSP2.4.gif]] | + | (2) [[Datei:BSP2.4.gif]] |
| | | |
− | [[Datei:BSP2.5.gif]] | + | (2) [[Datei:BSP2.5.gif]] |
| | | |
− | [[Datei:BSP2.6.gif]] | + | (2) [[Datei:BSP2.6.gif]] |
| | | |
− | [[Datei:BSP2.7.gif]] | + | (3) [[Datei:BSP2.7.gif]] |
| | | |
− | [[Datei:BSP2.8.gif]] | + | (3) [[Datei:BSP2.8.gif]] |
| | | |
− | [[Datei:BSP2.9.gif]] | + | (4) [[Datei:BSP2.9.gif]] |
| | | |
− | [[Datei:BSP2.10.gif]] | + | (4) [[Datei:BSP2.10.gif]] |
| | | |
− | [[Datei:BSP2.11.gif]] | + | (5) [[Datei:BSP2.11.gif]] |
| | | |
− | [[Datei:BSP2.12.gif]] | + | (6) [[Datei:BSP2.12.gif]] |
| | | |
| | | |
Version vom 26. Juni 2013, 12:34 Uhr
Introduction
The Karush-Kuhn-Tucker theorem (short: KKT-Theorem) is a way of nonlinear optimization. It´s named after Harold W. Kuhn, who mentioned it in his master thesis in 1939 and Albert W. Tucker published the conditions in 1951 for the first time.
The KKT-Theorem is a generalization of the Lagrangian condition and takes the inequality constraints in consideration. It´s a necessary (even sufficient under certain preconditions) condition which shall be satisfied by an extremizer of the Lagrangian function.
KKT-Conditions
KKT conditions for the minimization problem
corresponding Lagrangian function:
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(1)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(2)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(3)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(4)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(5)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(6)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
j=1,...,n;i=1,...,m
KKT conditions for the maximization problem
corresponding Lagrangian function:
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(1)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(2)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(3)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(4)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(5)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(6)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
j=1,...,n;i=1,...,m
In general a vector
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
qualifies as saddle point for
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
To make it more clearly an optical presentation:
->Bild<-
->
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
is global minimum of
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
for a fixed
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
->
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
is global maximum of
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
for a fixed
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Example
The following example will make the structure of the theorem more clear.
This is an example for the minimization:
The problem which should be solved:
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
First you have to build the Langrangian function
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
then form the KKT conditions 1-6 of the minimization
(1)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(1)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(1)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(2)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(2)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(2)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(3)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(3)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(4)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(4)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(5)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
(6)
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
solution:
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Sources
-Domschke; Drexl – Einführung in Operations research(2005); 4.Auflage; Springer-Verlag
-APMonitorCom - YouTube http://www.youtube.com/watch?v=eaKPzb11qFw
-http://de.wikipedia.org/wiki/Konvexe_Optimierung#Karush-Kuhn-Tucker-Bedingungen