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

Version vom 11. Juni 2013, 22:34 Uhr (Quelltext anzeigen) Ridder (Diskussion | Beiträge) ← Zum vorherigen Versionsunterschied		Aktuelle Version vom 13. Juni 2013, 10:31 Uhr (Quelltext anzeigen) Schaffra (Diskussion | Beiträge)
Zeile 126:		Zeile 126:
	--[[Benutzer:Ridder|ridder]] ([[Benutzer Diskussion:Ridder|Diskussion]]) 21:51, 11. Jun. 2013 (CEST)		--[[Benutzer:Ridder|ridder]] ([[Benutzer Diskussion:Ridder|Diskussion]]) 21:51, 11. Jun. 2013 (CEST)
		+	--[[Benutzer:Schaffra|schaffra]] ([[Benutzer Diskussion:Schaffra|Diskussion]]) 10:31, 13. Jun. 2013 (CEST)

---

Aktuelle Version vom 13. Juni 2013, 10:31 Uhr

Introduction

The Karush-Kuhn-Tucker theorem (short: KKT-Theorem) is a way of nonlinear optimization. It is based on Lagrangian optimization. Beside the additional conditions of the Lagrangian attempt there are some other extra conditions which are called KKT-conditions. The aim of this theory is to solve a problem with additional conditions in form of inequaliities.

The first mention of the KKT-conditions was in the master thesis of William Karush in 1939. But it became more famous in 1951 where Harold W. Kuhn and Albert W. Tucker presented it in a conference paper.

KKT-Conditions

In the following chapter the conditions will be demonstrated in a mathematical form:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \frac{\delta L}{\delta x_{j}}= \frac{\delta f}{\delta x_{j}}\left ( \widehat{x} \right )+ \sum_{i=1}^{m} \widehat{\lambda_{i}}\cdot \frac{\delta g_{i}}{\delta x_{j}}\left ( \widehat{x} \right )\geq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \widehat{x}\cdot \frac{\delta L}{\delta x_{j}}= \widehat{x}\cdot \left ( \frac{\delta f\left ( x \right )}{\delta x_{j}}+ \sum_{i=1}^{m}\widehat{\lambda _{i}}\cdot \frac{\delta g_{i}}{\delta x_{j}}\cdot \left ( \widehat{x} \right ) \right )=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \frac{\delta L}{\delta \lambda _{i}}=g_{i}\left ( \widehat{x} \right )\leq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4)\widehat{\lambda _{i} }\cdot\frac{\delta L }{\delta \lambda _{i}}=\widehat{\lambda _{i}}\cdot g_{i}\left ( \widehat{x} \right )=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (5)\widehat{x}\geq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (6)\widehat{\lambda }\geq 0

Langrangian function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\delta L}{\delta x_{j}}= \frac{\delta f}{\delta x_{j}}\left ( x \right )-\sum_{i=1}^{m}\lambda _{i}\frac{\delta g_{i}}{\delta x_{j}}\left ( x \right )

It exist a saddle point in ${\displaystyle \left({\widehat {x}},{\widehat {\lambda }}\right)}$ if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L\left ( \widehat{x},\lambda \right )\leq L\left ( \widehat{x},\widehat{\lambda } \right )\leq L\left ( x,\widehat{\lambda } \right ) .

In general it holds that ${\displaystyle {\widehat {x}}}$ minimizes ${\displaystyle L\left(x,{\widehat {\lambda }}\right)}$ and ${\displaystyle {\widehat {\lambda }}}$ maximizes ${\displaystyle L\left({\widehat {x}},\lambda \right)}$

If the known Langrangian function is convex in x and concave in ${\displaystyle \lambda }$ , so the KKT conditions are necessary and sufficient conditions for a saddle point of ${\displaystyle L\left(x,\lambda \right)}$

It doesn´t mean that every possible calculated candidate is an optimal solution for this problem. One has to consider the Slater constraint qualification to test, if the candidate is an optimum. It includes that at least one point x is in the solution space. This point has to be between the restrictions.

Slater constraint qualification: ${\displaystyle g_{i}\left(x\right)<0}$ for Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x\in \mathbb{R}_{+_{}}

and for Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i\in I=(1,...,m)

(I = number of additional conditions).

If the KKT conditions as well as the Slater constraint qualification are satisfied then the calculated candidate is an optimal solution.

Example

The following example will explain the theorem in a clearer way.

The objective function f(x,y) should be maximized.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max f\left ( x,y \right )= x+3y-4e^{-x-y}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_{1}( x )=x+2y\leq 2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_{2}(x)=x+y\leq 1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L\left ( x,y \right )=x+3y-4e^{-x-y}-\lambda _{1} \left ( x+2y-2 \right )-\lambda _{2}\left ( x+y-1 \right )

KKT conditions for ${\displaystyle \left({\widehat {x}},{\widehat {y}}\right)}$ :

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (i)L_{1}^{'}=1+4e^{-\widehat{x}-\widehat{y}}-\lambda _{1}-\lambda _{2}=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (ii)L_{2}^{'}=3+4e^{-\widehat{x}-\widehat{y}}-2\lambda _{1}-\lambda _{2}=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (iii)\lambda _{1}\geq 0

and ${\displaystyle \lambda _{1}=0}$, if ${\displaystyle {\widehat {x}}+2{\widehat {y}}<2}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (iv)\lambda _{2}\geq 0

and ${\displaystyle \lambda _{2}=0}$, if ${\displaystyle {\widehat {x}}+{\widehat {y}}<1}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (ii)-(i): -2+\lambda _{1}=0\Leftrightarrow \lambda _{1}= 2

${\displaystyle (iii)}$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \widehat{x}+2\widehat{y}\leq 2\Rightarrow \widehat{x}+2\widehat{y}=2

  ${\displaystyle (v)}$

assumption: ${\displaystyle \lambda _{2}=0}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \left ( i \right )\rightarrow 1+4e^{-\widehat{x}-\widehat{y}}-2=0\Leftrightarrow 4e^{-\widehat{x}-\widehat{y}}=1\Leftrightarrow -\widehat{x}-\widehat{y}=ln\left ( \frac{1}{4} \right )= -ln4\Leftrightarrow \widehat{x} +\widehat{y}=ln4> 1

In contradiction to Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (iv)\rightarrow \lambda _{2}> 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (i)L_{1}^{'}=1+4e^{-\widehat{x}-\widehat{y}}-\lambda _{1}-\lambda _{2}=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (ii)L_{2}^{'}=3+4e^{-\widehat{x}-\widehat{y}}-2\lambda _{1}-\lambda _{2}=0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (iii)\lambda _{1}\geq 0

and ${\displaystyle \lambda _{1}=0}$, if ${\displaystyle {\widehat {x}}+2{\widehat {y}}<2}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (iv)\lambda _{2}\geq 0

and ${\displaystyle \lambda _{2}=0}$, if ${\displaystyle {\widehat {x}}+{\widehat {y}}<1}$

${\displaystyle \left(v\right){\widehat {x}}+2{\widehat {y}}=2}$

${\displaystyle \lambda _{2}>0}$

From ${\displaystyle (iv)}$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \widehat{x}+\widehat{y}\leq 1\rightarrow \widehat{x}+\widehat{y}= 1

With ${\displaystyle (v)}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow \widehat{x}=0

and ${\displaystyle {\widehat {y}}=1}$

Then insert the values for ${\displaystyle {\widehat {x}}}$ and ${\displaystyle {\widehat {y}}}$ into ${\displaystyle (i)}$ and ${\displaystyle (ii)}$ :Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{2}= e^{-1}\left ( 4-e \right )> 0

solution:Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \widehat{x}= 0,\widehat{y}= 1,\lambda _{1}= 2,\lambda _{2}= e^{-1}\left ( 4-e \right )

Sources

-http://www.uni-graz.at/sor/Downloads/SS2010/MathematischeMethoden/kuhntucker%20%5BKompatibilit%E4tsmodus%5D.pdf

-http://de.wikipedia.org/wiki/Konvexe_Optimierung#Karush-Kuhn-Tucker-Bedingungen

-Domschke; Drexl – Einführung in Operations research(2005); 6.Auflage; Springer-Verlag

-Zimmermann, Hans-Jürgen – Operations Research Methoden und Modelle(1987); 1.Auflage; Vieweg-Verlag (Braunschweig)

--ridder (Diskussion) 21:51, 11. Jun. 2013 (CEST) --schaffra (Diskussion) 10:31, 13. Jun. 2013 (CEST)