Nonlinear Opt.: KKT- theorem 2: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Example)
(→‎Example)
Zeile 64: Zeile 64:
  
 
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:
Zeile 73: Zeile 74:
 
[[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
+
 
 +
then form the KKT conditions 1-6 of the minimization:
  
 
(1) [[Datei:BSP20.gif]]
 
(1) [[Datei:BSP20.gif]]
Zeile 84: Zeile 87:
  
 
(1) [[Datei:BSP2.3.gif]]
 
(1) [[Datei:BSP2.3.gif]]
 +
  
 
(2) [[Datei:BSP2.4.gif]]
 
(2) [[Datei:BSP2.4.gif]]
Zeile 90: Zeile 94:
  
 
(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 ==

Version vom 26. Juni 2013, 13: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: 

                                    ->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


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

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Nonlinear_Opt.:_KKT-_theorem_2&oldid=4420“