|
|
(16 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) |
Zeile 10: |
Zeile 10: |
| | | |
| | | |
− | KKT conditions for the minimization problem | + | '''KKT conditions for the minimization problem''' |
| | | |
| corresponding Lagrangian function: [[Datei:Lagrangemin.gif]] | | corresponding Lagrangian function: [[Datei:Lagrangemin.gif]] |
Zeile 26: |
Zeile 26: |
| (6) [[Datei:(6).gif]] | | (6) [[Datei:(6).gif]] |
| | | |
| + | j=1,...,n;i=1,...,m |
| | | |
− | KKT conditions for the maximization problem | + | |
| + | '''KKT conditions for the maximization problem''' |
| | | |
| corresponding Lagrangian function: [[Datei:Lagrangemax.gif]] | | corresponding Lagrangian function: [[Datei:Lagrangemax.gif]] |
Zeile 43: |
Zeile 45: |
| (6) [[Datei:(6).gif]] | | (6) [[Datei:(6).gif]] |
| | | |
| + | j=1,...,n;i=1,...,m |
| | | |
| | | |
| | | |
| 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 56: |
Zeile 61: |
| ->[[Datei:Max.gif]] is global maximum of [[Datei:Max2.gif]] for a fixed [[Datei:CodeCogsEqn.gif]] | | ->[[Datei:Max.gif]] is global maximum of [[Datei:Max2.gif]] for a fixed [[Datei:CodeCogsEqn.gif]] |
| | | |
| + | == Example == |
| | | |
| + | The following example will make the structure of the theorem more clear. |
| | | |
− | == Example ==
| + | This is an example for the minimization. |
| + | |
| + | |
| + | The problem which should be solved: |
| + | |
| + | [[Datei:Example1.1.gif]] |
| + | |
| + | s.t. |
| + | |
| + | [[Datei:Example1.2.gif]] |
| + | |
| + | [[Datei:Example1.3.gif]] |
| + | |
| + | |
| + | First you have to build the Langrangian function: |
| + | |
| + | [[Datei:BSP1.gif]] |
| + | |
| + | |
| + | Then form the KKT conditions 1-6 of the minimization: |
| + | |
| + | (1) [[Datei:1.1.gif]] |
| + | |
| + | (1) [[Datei:1.2.gif]] |
| + | |
| + | (1) [[Datei:BSP2.3.gif]] |
| + | |
| + | |
| + | (2) [[Datei:BSP2.4.gif]] |
| + | |
| + | (2) [[Datei:BSP2.5.gif]] |
| + | |
| + | (2) [[Datei:BSP2.6.gif]] |
| + | |
| + | |
| + | (3) [[Datei:BSP2.7.gif]] |
| + | |
| + | (3) [[Datei:BSP2.8.gif]] |
| + | |
| + | |
| + | (4) [[Datei:BSP2.9.gif]] |
| + | |
| + | (4) [[Datei:BSP2.10.gif]] |
| + | |
| + | |
| + | (5) [[Datei:BSP2.11.gif]] |
| + | |
| + | |
| + | (6) [[Datei:BSP2.12.gif]] |
| + | |
| + | |
| + | Solve the conditions 1-4 |
| | | |
| + | solution: |
| | | |
| + | [[Datei:Solution.gif]] |
| | | |
| == Sources == | | == Sources == |
Zeile 66: |
Zeile 126: |
| -Domschke; Drexl – Einführung in Operations research(2005); 4.Auflage; Springer-Verlag | | -Domschke; Drexl – Einführung in Operations research(2005); 4.Auflage; Springer-Verlag |
| | | |
− | -APMonitorCom - YouTube | + | -APMonitorCom - YouTube http://www.youtube.com/watch?v=eaKPzb11qFw |
− | http://www.youtube.com/watch?v=eaKPzb11qFw
| + | |
| | | |
| -http://de.wikipedia.org/wiki/Konvexe_Optimierung#Karush-Kuhn-Tucker-Bedingungen | | -http://de.wikipedia.org/wiki/Konvexe_Optimierung#Karush-Kuhn-Tucker-Bedingungen |
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