|
|
(6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) |
Zeile 50: |
Zeile 50: |
| | | |
| In general a vector [[Datei:Vektor.gif]] qualifies as saddle point for [[Datei:Sattel.gif]] | | In general a vector [[Datei:Vektor.gif]] qualifies as saddle point for [[Datei:Sattel.gif]] |
| + | |
| | | |
| To make it more clearly an optical presentation: | | To make it more clearly an optical presentation: |
| | | |
− | ->Bild<-
| + | [[Datei:IMG 0002.jpg]] |
| + | |
| | | |
| ->[[Datei:Min.gif]] is global minimum of [[Datei:Min2.gif]] for a fixed [[Datei:Lamdadach.gif ]] | | ->[[Datei:Min.gif]] is global minimum of [[Datei:Min2.gif]] for a fixed [[Datei:Lamdadach.gif ]] |
Zeile 64: |
Zeile 66: |
| | | |
| This is an example for the minimization. | | This is an example for the minimization. |
| + | |
| | | |
| The problem which should be solved: | | The problem which should be solved: |
| | | |
| [[Datei:Example1.1.gif]] | | [[Datei:Example1.1.gif]] |
| + | |
| + | s.t. |
| | | |
| [[Datei:Example1.2.gif]] | | [[Datei:Example1.2.gif]] |
Zeile 73: |
Zeile 78: |
| [[Datei:Example1.3.gif]] | | [[Datei:Example1.3.gif]] |
| | | |
− | First you have to build the Langrangian function | + | |
| + | First you have to build the Langrangian function: |
| | | |
| [[Datei:BSP1.gif]] | | [[Datei:BSP1.gif]] |
| | | |
− | then form the KKT conditions 1-6 of the minimization
| |
| | | |
− | (1) [[Datei:BSP20.gif]]
| + | Then form the KKT conditions 1-6 of the minimization: |
| | | |
− | (1) [[Datei:BSP21.gif]] | + | (1) [[Datei:1.1.gif]] |
| + | |
| + | (1) [[Datei:1.2.gif]] |
| | | |
| (1) [[Datei:BSP2.3.gif]] | | (1) [[Datei:BSP2.3.gif]] |
| + | |
| | | |
| (2) [[Datei:BSP2.4.gif]] | | (2) [[Datei:BSP2.4.gif]] |
Zeile 90: |
Zeile 98: |
| | | |
| (2) [[Datei:BSP2.6.gif]] | | (2) [[Datei:BSP2.6.gif]] |
| + | |
| | | |
| (3) [[Datei:BSP2.7.gif]] | | (3) [[Datei:BSP2.7.gif]] |
| | | |
| (3) [[Datei:BSP2.8.gif]] | | (3) [[Datei:BSP2.8.gif]] |
| + | |
| | | |
| (4) [[Datei:BSP2.9.gif]] | | (4) [[Datei:BSP2.9.gif]] |
| | | |
| (4) [[Datei:BSP2.10.gif]] | | (4) [[Datei:BSP2.10.gif]] |
| + | |
| | | |
| (5) [[Datei:BSP2.11.gif]] | | (5) [[Datei:BSP2.11.gif]] |
| + | |
| | | |
| (6) [[Datei:BSP2.12.gif]] | | (6) [[Datei:BSP2.12.gif]] |
| | | |
| | | |
| + | Solve the conditions 1-4 |
| + | |
| + | solution: |
| | | |
− | solution: [[Datei:Solution.gif]]
| + | [[Datei:Solution.gif]] |
| | | |
| == Sources == | | == Sources == |
Aktuelle Version vom 30. Juni 2013, 10:54 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:
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 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
s.t.
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
Solve the conditions 1-4
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